Georgian Mathematical Journal Volume 8 (2001), Number 2, 415–426

TRACTABILITY OF TENSOR PRODUCT LINEAR OPERATORS IN WEIGHTED HILBERT SPACES

HENRYK WOŹNIAKOWSKI

Dedicated to N. Vakhania

on the occasion of his 70th birthday

Abstract. We study tractability in the worst case setting of tensor product linear operators defined over weighted tensor product Hilbert spaces. Tractability means that the minimal number of evaluations needed to reduce the initial error by a factor of ε in the d-dimensional case has a polynomial bound in both ε^{−1} and d. By one evaluation we mean the computation of an arbitrary continuous linear functional, and the initial error is the norm of the linear operator S_{d} specifying the d-dimensional problem.

We prove that nontrivial problems are tractable iff the dimension of the image under S_{1} (the one-dimensional version of S_{d}) of the unweighted part of the Hilbert space is one, and the weights of the Hilbert spaces, as well as the singular values of the linear operator S_{1}, go to zero polynomially fast with their indices.

2000 Mathematics Subject Classification: 41A05.

Key words and phrases: Tractability, operator approximation, multivariate approximation, worst case complexity.

1. Introduction

I am pleased to dedicate this paper to Professor Nicholas N. Vakhania on the occasion of his 70th birthday. I enjoyed many meetings with Professor Vakhania in Dagstuhl, Tbilisi, Warsaw, and New York. I have learned a lot from his books “Probability Distributions on Linear Spaces” [10], and “Probability Distributions on Banach Spaces” [11] (the second book written jointly with V. I. Tarieladze and S. A. Chobanyan). These books have been very helpful in my work and in the work of many colleagues working in the average case setting of information-based complexity, and are always cited in papers dealing with this subject.

I also wish to add that Professor Vakhania solved an important problem in the average case complexity. His paper [12] and the paper [3] prove that every ill-posed problem specified by a measurable unbounded linear operator is wellposed on the average for any Gaussian measure, and its average case complexity is finite for any positive error demand.

ISSN 1072-947X / $8.00 / \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag www.heldermann.de

In recent years, my research interests has shifted to multivariate problems and tractability issues. That is why I have decided to send a paper on this subject in token of my appreciation of Professor N. N. Vakhania.

Tractability of multivariate problems has recently become a popular research subject. The reader is referred to [1, 2, 4, 6, 7, 13, 14, 15, 16, 17], and to the surveys [5, 9]. Tractability means that a minimal number of evaluations needed to reduce the initial error by a factor of ε in the d-dimensional case has a polynomial bound in both ε^{−1} and d. Strong tractability means that this bound is independent of d, and is polynomially dependent only on ε^{−1}. Tractability is studied in various settings. Here, we only consider the worst case setting, in which an approximation error is defined as a maximal error over the unit ball of a Hilbert space.

In this paper, we study tractability of linear operators between tensor product Hilbert spaces. In the d-dimensional case, a linear operator is defined as a tensor product of d copies of the same linear operator. The domain of a linear operator is assumed to be a weighted tensor product Hilbert space with weights γ_{1} ≥ γ_{2} ≥ … > 0, where γ_{j} corresponds to the jth component of the tensor product.

We comment on the role of the weights γ_{j}. For the jth component, we consider a Hilbert space that is a direct sum of two Hilbert spaces H_{1} and H_{2}, where H_{1} ∩ H_{2} = {0}. The space H_{1} corresponds to the unweighted part, whereas the space H_{2} corresponds to the weighted part with the weight γ_{j}. That is, for f = f_{1} + f_{2} with f_{i} ∈ H_{i} we have

∥f∥^{2} = ∥f_{1}∥_{H_{1}}^{2} + γ_{j}^{−1}∥f_{2}∥_{H_{2}}^{2}.

Hence, if ∥f∥ ≤ 1 and γ_{j} is small, then f_{2} must be small too. In this way, the weight γ_{j} controls the size of the weighted components.

We approximate linear operators evaluating finitely many arbitrary (continuous) linear functionals. The case of a restricted choice of such functionals is studied, e.g., in [14], and leads to different results. For example, we shall prove that there is no difference between strong tractability and tractability. This is not the case if we use only function evaluations instead of arbitrary linear functionals.

We want to reduce the initial error which is defined as the norm of the linear operator S_{d} defining the d-dimensional problem. The initial error is the error, which can be obtained without any evaluation and which formally corresponds to the error of the zero approximation.

The main result of this paper is a full characterization of tractable linear operators. Obviously, some linear operators are trivially tractable. This certainly holds for linear functionals, which can be recovered exactly by just one evaluation. It turns out that the class of tractable linear operators is exactly equal to the class of linear functionals iff the weights γ_{j} of the Hilbert spaces have the sum-exponent equal to infinity. Here, the sum-exponent p_{γ} is defined as the infimum of nonnegative β for which

∑_{j=1}^{∞} γ_{j}^{β} < ∞.

Thus, p_{γ} = ∞ means that the last series is always divergent. This holds, in particular, for the unweighted case γ_{j} = 1, for which there is no difference between the components from H_{1} and H_{2}.

It is easy to see that p_{γ} < ∞ iff the weights γ_{j} go to zero polynomially fast with j^{−1}. If p_{γ} < ∞, then there are non-trivial strongly tractable linear operators. They are fully characterized by two conditions. The first condition is that the dimension of the image of S_{1} (the one-dimensional version of S_{d}) of the unweighted part is one. The second condition is that the sum-exponent p_{λ} of the singular values \sqrt{λ_{i}} of S_{1} is finite. We stress that the requirement p_{λ} < ∞ is a stronger condition than mere compactness of S_{1}.

For strongly tractable problems, the strong exponent is defined as the infimum of p for which a minimal number of evaluations needed to reduce the initial error by a factor ε is of order ε^{−p} for all d. We find that the strong exponent is 2 max(p_{λ}, p_{γ}). We stress that the strong exponent is large if either p_{λ} or p_{γ} is large.

As mentioned before, we use arbitrary linear functionals as tools for approximating linear operators in this paper. We plan to analyze the natural restriction of arbitrary linear functionals to function evaluations in the near future. Preliminary results indicate that a full characterization of strongly tractable and tractable linear operators is more complex, depending on the specific Hilbert space used when d = 1.

2. Tractability and Strong Tractability

Let H_{1} and H_{2} be two Hilbert spaces such that H_{1} ∩ H_{2} = {0}. Their inner products are denoted by ⟨·, ·⟩_{H_{i}}. For γ ∈ (0, 1], consider the Hilbert space F_{1,γ} = H_{1} ⊕ H_{2} with the inner product

⟨f, g⟩_{F_{1,γ}} = ⟨f_{1}, g_{1}⟩_{H_{1}} + γ^{−1} ⟨f_{2}, g_{2}⟩_{H_{2}} ,

where f, g ∈ F_{1,γ} have the unique representation f = f_{1} + f_{2}, g = g_{1} + g_{2} with f_{1}, g_{1} ∈ H_{1} and f_{2}, g_{2} ∈ H_{2}. Observe that the components in H_{1} are unweighted, whereas the components in H_{2} are weighted with the parameter γ. If ∥f∥_{F_{1,γ}} ≤ 1 for small γ, then the component f_{2} is negligible. For γ = 1, we let F_{1} = F_{1,1}.

Let G_{1} be a Hilbert space, and let S_{1} : F_{1} → G_{1} be a (continuous) linear operator. Note that S_{1} is also well defined on F_{1,γ} for all γ ∈ (0, 1].

For d ≥ 2, define F_{d} = F_{1} ⊗ ⋯ ⊗ F_{1} (d times) as the tensor product of d copies of the space F_{1}. That is, F_{d} is the completion of linear combinations of tensor products f_{1} ⊗ ⋯ ⊗ f_{d}, with f_{i} ∈ F_{1}, which we write, for simplicity, as f_{1}f_{2} ⋯ f_{d}. Recall that if f_{i} are numbers, then their tensor product is just the product of these numbers, and if f_{i} are univariate functions, then their tensor product is the d-variate function f(t_{1}, …, t_{d}) = ∏_{j=1}^{d} f_{j}(t_{j}).

The space F_{d} is a Hilbert space with the tensor product inner product defined as

⟨f, g⟩_{F_{d}} = ∏_{j=1}^{d} ⟨f_{j}, g_{j}⟩_{F_{1}} .

for f = f_{1} … f_{d} ∈ F_{d} and g = g_{1} ⋯ g_{d} ∈ F_{d} with f_{j}, g_{j} ∈ F_{1}. We define the Hilbert space G_{d} = G_{1} ⊗ ⋯ ⊗ G_{1} (d times) with the inner product ⟨·, ·⟩_{G_{d}} similarly.

For d ≥ 2, let S_{d} = S_{1} ⊗ ⋯ ⊗ S_{1} : F_{d} → G_{d} denote the tensor product linear operator consisting of d copies of S_{1}. Thus, for f = f_{1} ⋯ f_{d} with f_{j} ∈ F_{1}, we have

S_{d}f = S_{1}f_{1} ⋯ S_{1}f_{d} ∈ G_{d}.

Take now a sequence of weights

γ_{1} ≥ γ_{2} ≥ ⋯ ≥ γ_{d} ≥ ⋯ > 0,

and consider the tensor product

F_{d,γ} = F_{1,γ_{1}} ⊗ F_{1,γ_{2}} ⊗ ⋯ ⊗ F_{1,γ_{d}}.

The space F_{d,γ} is a Hilbert space with the inner product ⟨·, ·⟩_{F_{d,γ}}. To see how the weights γ_{j} affect the norm, take f = f_{1} ⋯ f_{d} with f_{j} = f_{j,1} + f_{j,2}, where f_{j,1} ∈ H_{1}, f_{j,2} ∈ H_{2}. Then

∥f∥_{F_{d,γ}}^{2} = ∏_{j=1}^{d} (∥f_{j,1}∥_{H_{1}}^{2} + γ_{j}^{−1}∥f_{j,2}∥_{H_{2}}^{2}) .

Again, if ∥f∥_{F_{d,γ}} ≤ 1 and the weights γ_{j} go to zero, then the components f_{j,2} must approach zero.

Observe that the linear operator S_{d} is well defined on F_{d,γ} independently of the weights γ_{j}. Although the values of S_{d}f do not depend on γ_{j}, its adjoint S_{d}^{∗} and its norm ∥S_{d}∥_{F_{d,γ}} do depend on γ_{j}. Indeed, for d = 1, it is easy to check that S_{1}^{∗} : G_{1} → F_{1,γ} is given by

S_{1}^{∗} = S_{1}|_{H_{1}}^{∗} + γ S_{1}|_{H_{2}}^{∗},

where S_{1}|_{H_{i}} denotes the operator S_{1} restricted to H_{i} and S_{1}|_{H_{i}}^{∗} : G_{1} → H_{i} is the

adjoint operator of S_{1}|_{H_{i}}. For d ≥ 2, we have

S_{d}^{∗} = (S_{1}|_{H_{1}}^{∗} + γ_{1}S_{1}|_{H_{2}}^{∗}) ⊗ ⋯ ⊗ (S_{1}|_{H_{1}}^{∗} + γ_{d}S_{1}|_{H_{2}}^{∗}) .

To obtain the norm of S_{d}, define the non-negative self-adjoint operator W_{d,γ} = S_{d}^{∗}S_{d} : F_{d,γ} → F_{d,γ} and observe that

∥S_{d}f∥_{G_{d}}^{2} = ⟨S_{d}f, S_{d}f⟩_{G_{d}} = ⟨W_{d,γ}f, f⟩_{F_{d,γ}} .

This implies that the norm ∥S_{d}∥_{F_{d,γ}} is equal to the square root of the largest eigenvalue of W_{d,γ}.

We want to approximate S_{d}f for f from the unit ball of F_{d,γ}. Our approximations will be of the form^{1}

U_{n,d}(f) = ∑_{i=1}^{n} L_{i}(f) g_{i}

for certain continuous linear functionals L_{i} ∈ F_{d,γ}^{∗}, and for certain g_{i} ∈ G_{d}.

We define the error of U_{n,d} in the worst case sense as the maximal distance between S_{d}(f) and U_{n,d}(f) over the unit ball of F_{d,γ},

e(U_{n,d}, F_{d,γ}) = sup_{f∈F_{d,γ},∥f∥_{F_{d,γ}} ≤1} ∥S_{d}(f) − U(f)∥_{G_{d}}.

For n = 0, we formally set U_{0,d}(f) = 0. Then e(0, F_{d,γ}) = ∥S_{d}∥_{F_{d,γ}} is the initial error, which is the a priori error without sampling the element f. Our goal is to reduce the initial error by a factor ε ∈ (0, 1). That is, we want to find U_{n,d}, or equivalently we want to find L_{i} ∈ F_{d,γ}^{∗} and g_{i} ∈ G_{d} for i = 1, …, n, such that

e(U_{n,d}, F_{d,γ}) ≤ ε ∥S_{d}∥_{F_{d,γ}}.

We are ready to recall the concepts of tractability and strong tractability, see [1, 2, 4, 5, 6, 13, 14, 15, 16, 17]. In some of these papers, tractability is defined for absolute errors. In this paper we define tractability for normalized errors. Let

n(ε, S_{d}) = min{ n : ∃ U_{n,d} with e(U_{n,d}, F_{d,γ}) ≤ ε ∥S_{d}∥_{F_{d,γ}} }

be a minimal number of evaluations needed to reduce the initial error by a factor ε. Obviously, the minimal number n(ε, S_{d}) also depends on the spaces F_{d,γ} and G_{d} and therefore it depends on the weight sequence γ_{j}. In fact, as we shall see, the dependence on {γ_{j}} will be crucial.

We say that the problem {S_{d}} is tractable iff there exist nonnegative numbers C, q and p such that

n(ε, S_{d}) ≤ C d^{q} ε^{−p} ∀ ε ∈ (0, 1), ∀ d = 1, 2, ….  (1)

The problem {S_{d}} is strongly tractable if q = 0 in estimate (1) of n(ε, S_{d}).

The essence of tractability is that the minimal number of evaluations is bounded by a polynomial in both d and ε^{−1}, and the essence of strong tractability is that this number has a bound independent of d and polynomial in ε^{−1}. The exponent of strong tractability is defined as the infimum of p satisfying (1).

Obviously, some linear operators S_{d} are trivially strongly tractable independently of the weights γ_{j}. This holds for dim(S_{1}(F_{1})) = 0, i.e., S_{1} = 0, since then S_{d} = 0 and n(ε, S_{d}) = 0 for all ε ∈ (0, 1) and d ≥ 1. Furthermore, if dim(S_{1}(F_{1})) = 1 then S_{1} is a continuous linear operator of rank 1, S(f) = ⟨f, h⟩_{F_{1}} g for a nonzero h ∈ F_{1} and a nonzero g ∈ G_{1}. Then

1It is known that neither nonadaptive information nor nonlinear approximations help in approximating linear operators over Hilbert spaces, see e.g., [8]. Hence, it is enough to study linear U_{n,d}.

S_{d}(f) = ⟨f, h_{d}⟩_{F_{d}} g_{d}

with h_{d} = h^{d} and g_{d} = g^{d}. This means that setting L_{1}(f) = ⟨f, h_{d}⟩_{F_{d}} and g_{1} = g^{d} we get e(U_{1,d}, F_{d,γ}) = 0 for all d, and n(ε, S_{d}) ≤ 1.

We define the set of such trivial strongly tractable operators as

triv(F_{1}) = { S_{1} : dim(S_{1}(F_{1})) ≤ 1 }.

Let

trac(F_{1}, γ) = { S_{1} : {S_{d}} is tractable }
strong-trac(F_{1}, γ) = { S_{1} : {S_{d}} is strongly tractable }

denote the sets of tractable and strongly tractable operators. Clearly,

triv(F_{1}) ⊂ strong-trac(F_{1}, γ) ⊂ trac(F_{1}, γ) ∀ γ = {γ_{j}}.

The main purpose of this paper is to find the sets strong-trac(F_{1}, γ) and trac(F_{1}, γ) and to check whether, or when, they differ from the set triv(F_{1}). As we shall see the answer will depend on the weight sequence γ.

As we shall see in the next section, the exponent of strong tractability depends, in particular, on the sum-exponent of the weight sequence γ, see [14]. By the sum-exponent of any nonnegative non-increasing sequence {a_{j}}, we mean

p_{a} = inf {β ≥ 0 : ∑_{j=1}^{∞} a_{j}^{β} ≤ ∞ }

with the convention that inf ∅ = ∞. In particular, for a_{j} = j^{−k} we have p_{a} = 1/k for k > 0, and p_{a} = ∞ for k ≤ 0.

It is easy to check that p_{a} is finite iff a_{j} goes to zero polynomially fast in j^{−1}. Indeed, if ∑_{j=1}^{∞} a_{j}^{β} = M < ∞, then a_{j}^{β} ≤ M/j and a_{j} = O(j^{−1/β}) goes polynomially to zero. The other implication is trivial.

3. Tractability Results

We are ready to prove the main result of this paper.

Theorem 3.1. (1) If p_{γ} = ∞, then

trac(F_{1}, γ) = strong-trac(F_{1}, γ) = triv(F_{1}).

(2) If p_{γ} < ∞, then

trac(F_{1}, γ) = strong-trac(F_{1}, γ) = triv(F_{1}) ∪ A(F_{1}, γ),

where

A(F_{1}, γ) = { S_{1} : dim(S_{1}(H_{1})) = 1 and p_{λ} < ∞ },

where p_{λ} is the sum-exponent^{2} of the ordered eigenvalues λ_{i} of the selfadjoint operator S_{1}|_{H_{2}}^{∗}S_{1}|_{H_{2}}. Furthermore, if S_{1} ∈ A(F_{1}, γ), then the strong exponent is zero if λ_{2} = 0, and 2 max(p_{γ}, p_{λ}) if λ_{2} > 0.

Before we prove Theorem 3.1, we comment on its statements. The first part assumes that the sum-exponent of the weights is infinity. This covers the unweighted case γ_{j} = 1, for which there is no difference in treating the components from the spaces H_{1} and H_{2}. In this case the result is negative. The only tractable problems are trivial and given by linear operators of rank at most one. As already noticed, such problems can be solved exactly with at most one evaluation, and therefore the strong exponent is zero.

The second case assumes that the sum-exponent of the weights is finite. This means that γ_{j} goes to zero polynomially fast as j goes to infinity. Then trivial problems are not only strongly tractable problems since strong tractability also holds for problems from A(F_{1}, γ). For such problems we must have that S_{1} reduced to H_{1} has rank one, and S_{1} reduced to H_{2} has singular values^{3} that go to zero polynomially fast. This, of course, implies that S_{1} is a compact operator. However, the converse is, in general, not true. That is, a compact S_{1} with dim(S_{1}(H_{1})) = 1 does not necessarily have finite p_{λ}.

We stress that although we have strong tractability, the strong exponent can be very large. Indeed, if the singular values of S_{1}|_{H_{2}} or if the weights γ_{j} go slowly to zero, then at least one of the sum-exponents is large, which implies a large strong exponent. For example, assume that λ_{j} = j^{−k_{1}}, and γ_{j} = j^{−k_{2}} with positive k_{i}. Then p = 2 max(1/k_{1}, 1/k_{2}) so that if either k_{1} or k_{2} is small, then p is large.

We stress that for both cases in Theorem 3.1, there is no difference between strong tractability and tractability. That is, the minimal number of evaluations needed to reduce the initial error by a factor of ε has either a bound independent of d or more than polynomially dependent on d. This is a consequence of two assumptions that we have made. The first assumption is that we use arbitrary continuous linear functionals. However, if we restrict ourselves to only function evaluations, then there is a difference between tractability and strong tractability, as proven in [1, 2, 6, 7]. The second assumption is that the weights are non-increasing and nested. That is, for the (d + 1)-dimensional case we use the same weights as for the d-dimensional case plus γ_{d+1}. For more general weights, as shown in [14], there is a difference between tractability and strong tractability even if arbitrary continuous linear functionals are used.

We now turn to the proof of Theorem 3.1. It will consist of two parts. The first part will be to prove that dim(S_{1}(H_{1})) ≥ 2 implies intractability of {S_{d}} independently of the weights γ_{j}. That is, if S_{1} has rank at least two in the unweighted part of the space F_{1}, then the behavior of S_{1} in H_{2}, as well as the weights γ_{j}, are irrelevant, and we have intractability. This shows that the unweighted part of the space F_{1} allows only at most rank one operators to get tractability. The second part of the proof assumes that dim(S_{1}(H_{1})) ≤ 1. This case easily reduces to the problem studied in [14], and a slight modification of the proof from [14] allows us to complete the proof of Theorem 3.1.

2If dim(H_{2}) < ∞, then we extend the finite sequence λ_{j} of eigenvalues by setting λ_{j} = 0 for j > dim(H_{2}). Then, obviously, p_{λ} = 0.

3A singular value of a linear operator S is the square root of an eigenvalue of S^{∗}S.

Lemma 3.1. If dim(S_{1}(H_{1})) ≥ 2, then {S_{d}} is intractable.

Proof. For d = 1, consider the operator W_{1,γ} = S_{1}^{∗}S_{1} : F_{1,γ} → F_{1,γ}. Let λ_{i,γ} denote the ordered eigenvalues of W_{1,γ}, λ_{1,γ} ≥ λ_{2,γ} ≥ ⋯ ≥ 0. The largest λ_{1,γ} is also equal to the square of the norm ∥S_{1}∥_{F_{1,γ}}. For f = f_{1} + f_{2}, f_{i} ∈ H_{i}, we have ∥f∥_{F_{1,γ}}^{2} = ∥f_{1}∥_{H_{1}}^{2} + γ^{−1}∥f_{2}∥_{H_{2}}^{2} and

∥S_{1}f∥_{G_{1}} ≤ ∥S_{1}|_{H_{1}} ∥_{H_{1}} ∥f_{1}∥_{H_{1}} + γ^{1/2} ∥S_{1}|_{H_{2}} ∥_{H_{2}} γ^{−1/2}∥f_{2}∥_{H_{2}}

≤ (∥S_{1}|_{H_{1}} ∥_{H_{1}}^{2} + γ ∥S_{1}|_{H_{2}} ∥_{H_{2}}^{2})^{1/2} ∥f∥_{F_{1,γ}}.

This proves that

λ_{1,γ} ≤ (∥S_{1}|_{H_{1}} ∥_{H_{1}}^{2} + γ ∥S_{1}|_{H_{2}} ∥_{H_{2}}^{2})^{1/2} ≤ (∥S_{1}|_{H_{1}} ∥_{H_{1}}^{2} + ∥S_{1}|_{H_{2}} ∥_{H_{2}}^{2})^{1/2}

since γ ∈ (0, 1].

We need a lower bound estimate of λ_{2,γ}. Recall that

λ_{2,γ} = inf_{h∈F_{1,γ}} sup_{f∈F_{1,γ}, ⟨f,h⟩_{F_{1,γ}} =0} \begin{matrix}⟨W_{1,γ}f, f⟩ & F_{1,γ} \\ ⟨f, f⟩ & F_{1,γ} \end{matrix} .

If we replace F_{1,γ} in the supremum by H_{1} then we obtain a lower bound on λ_{2,γ}. For f ∈ H_{1}, we have

⟨W_{1,γ}f, f⟩_{F_{1,γ}} = ∥S_{1}f∥_{G_{1}}^{2} = ⟨V f, f⟩_{H_{1}} ,

where V = S_{1}|_{H_{1}}^{∗}S_{1}|_{H_{1}} : H_{1} → H_{1}. Since ⟨f, h⟩_{F_{1,γ}} = ⟨f, h_{1}⟩_{H_{1}}, the last infimum over h ∈ F_{1,γ} is the same as the infimum over h ∈ H_{1}. Therefore we have

λ_{2,γ} ≥ inf_{h∈H_{1}} sup_{f∈H_{1}, ⟨f,h⟩_{H_{1}}=0} \begin{matrix}⟨V f, f⟩ & H_{1} \\ ⟨f, f⟩ & H_{1} \end{matrix} = λ_{2}(V),

where λ_{2}(V) is the second largest eigenvalue of V. Since dim(V (H_{1})) = dim(S_{1}(H_{1})) is at least 2 by hypothesis, we conclude that λ_{2}(V) is positive. Hence,

0 < λ_{2}(V) ≤ λ_{1}(V) = ∥S_{1}|_{H_{1}} ∥_{H_{1}}^{2} .

We now turn to d ≥ 2. Let λ_{i,d,γ} denote the ordered eigenvalues of W_{d,γ} = S_{d}^{∗}S_{d} : F_{d,γ} → F_{d,γ}. From the tensor product construction, we have

{ λ_{i,d,γ} } = { ∏_{j=1}^{d} λ_{i_{j},γ_{j}} : i_{j} = 1, 2, … }.

The square of the norm of S_{d} is the largest eigenvalue λ_{1,d,γ}, and so

∥S_{d}∥_{F_{d,γ}}^{2} = λ_{1,d,γ} = ∏_{j=1}^{d} λ_{1,γ_{j}} ≤ ∏_{j=1}^{d} (∥S_{1}|_{H_{1}} ∥_{H_{1}}^{2} + ∥S_{1}|_{H_{2}} ∥_{H_{2}}^{2}) .

It is known, see e.g., [8], that

n(ε, S_{d}) = min{ n : λ_{n+1,d,γ} ≤ ε^{2}λ_{1,d,γ} }.

Take an arbitrary integer k, and fix ε as

ε = \frac{1}{2} (\frac{λ_{2}(V)}{∥S_{1}|_{H_{1}} ∥_{H_{1}}^{2} + ∥S_{1}|_{H_{2}} ∥_{H_{2}}^{2}} )^{k/2} ∈ (0, 1).

For d > k, consider the vectors i⃗ = [i_{1}, i_{2}, …, i_{d}] with i_{j} ∈ {1, 2}. Take k

indices i_{j} equal to 2 and d − k indices i_{j} equal to 1. We have ( \begin{matrix}d \\ k \end{matrix} ) vectors

such that the eigenvalues satisfy

∏_{j=1}^{d} λ_{i_{j},γ_{j}} = ∏_{j: i_{j}=1} λ_{1,γ_{j}} ∏_{j: i_{j}=2} λ_{2,γ_{j}} = ∏_{j: i_{j}=2} \frac{λ_{2,γ_{j}}}{λ_{1,γ_{j}}} ∏_{j=1}^{d} λ_{1,γ_{j}}.

Since

\frac{λ_{2,γ_{j}}}{λ_{1,γ_{j}}} ≥ \frac{λ_{2}(V)}{∥S_{1}|_{H_{1}}∥_{H_{1}}^{2} + ∥S_{1}|_{H_{2}}∥_{H_{2}}^{2}} ,

we conclude that

∏_{j=1}^{d} λ_{i_{j},γ_{j}} ≥ 4 ε^{2} λ_{1,d,γ}.

This proves that

n(ε, S_{d}) ≥ ( \begin{matrix}d \\ k \end{matrix} ) = Θ(d^{k}) as d → ∞.

Since k can be arbitrarily large, this means that {S_{d}} is intractable, as claimed.

We now turn to

Proof of Theorem 3.1. We can assume that dim(S_{1}(H_{1})) ≤ 1 from Lemma 3.1. Consider first the case dim(S_{1}(H_{1})) = 0, i.e., S_{1}|_{H_{1}} = 0 and ∥S_{1}∥_{F_{1,γ}} = γ^{1/2}∥S_{1}∥_{H_{2}}. Similarly, ∥S_{d}∥_{F_{d,γ}} = (∏_{j=1}^{d} γ_{j}^{1/2}) ∥S_{d}∥_{H_{2}^{d}}, where H_{2}^{d} = H_{2}⊗⋯⊗H_{2} (d times). It is also easy to see that

e(U_{n,d}, F_{d,γ}) = ( ∏_{j=1}^{d} γ_{j}^{1/2}) e(U_{n,d}, H_{2}^{d})

for any optimal linear U_{n,d}. Hence, the weights γ_{j} do not play any role and the problem reduces to the space H_{2}^{d}. It is proven in [14] that {S_{d}} is tractable iff dim(S_{1}(H_{2})) ≤ 1. Since S_{1}(F_{1}) = S_{1}(H_{2}), we have tractability iff S_{1} ∈ triv(F_{1}).

Assume now that dim(S_{1}(H_{1})) = 1. That is, S_{1} has the form

S_{1}f = ⟨f_{1}, h_{1}⟩_{H_{1}} g_{1} + Sf_{2}

for f_{i} ∈ H_{i} and nonzero h_{1} ∈ H_{1} and g_{1} ∈ G_{1}.

Operators having a similar form were considered in [14]. The only difference is that instead of the inner product ⟨f, h_{1}⟩_{H_{1}} a more specific linear functional was considered. This is not important and we can modify U_{n,d} considered in [14] by taking for n = d = 1,

U_{1,1}(f) = ⟨f, h_{1}⟩_{H_{1}} g_{1},

and for n ≥ 2,

U_{n,1}(f) = U_{1,1}(f) + B_{n−1,1}(f_{2}),

where B_{n−1,1} is a sequence of approximation of S_{1}|_{H_{2}} in the space H_{2} defined as in [14]. The rest of Theorem 3.1 follows from Theorem 1 in [14].

4. Examples

We illustrate Theorem 3.1 by two examples of Sobolev spaces of d-variate functions defined over [0, 1]^{d}. This will be done for the approximation problem S_{d}f = f ∈ G_{d} = L_{2}([0, 1]^{d}).

Example 4.1. Let H_{1} = span(1, x, …, x^{r−1}) be the r-dimensional space of polynomials of degree at most r − 1 reduced to the interval [0, 1] with the inner product

⟨f, g⟩_{H_{1}} = ∑_{j=0}^{r−1} f^{(j)}(0)g^{(j)}(0).

Let H_{2} be the space of functions f defined over [0, 1] for which f^{(r−1)} is absolutely continuous, f^{(r)} belongs to L_{2}([0, 1]), and f^{(j)}(0) = 0 for j = 0, 1, …, r −1. The inner product in H_{2} is

⟨f, g⟩_{H_{2}} = ∫_{0}^{1} f^{(r)}(t)g^{(r)}(t) dt.

Obviously, H_{1} ∩ H_{2} = {0}, as required in our analysis. We thus have

F_{1,γ} = { f : [0, 1] → ℝ : f^{(r−1)} abs. cont., f^{(r)} ∈ L_{2}([0, 1]) }

with the inner product

⟨f, g⟩_{F_{1,γ}} = ∑_{j=0}^{r−1} f^{(j)}(0)g^{(j)}(0) + γ^{−1} ∫_{0}^{1} f^{(r)}(t)g^{(r)}(t) dt.

It is well known that the Hilbert space F_{1,γ} has a reproducing kernel of the form

K_{1,γ}(x, t) = ∑_{j=0}^{r−1} \frac{x^{j}}{j!} \frac{t^{j}}{j!} + γ ∫_{0}^{1} \frac{(x − u)_{+}^{r−1}}{(r − 1)!} \frac{(t − u)_{+}^{r−1}}{(r − 1)!} dt,

where u_{+} = max(u, 0), see, e.g., [5].

For the approximation problem, we have dim(S_{1}(H_{1})) = r. For r ≥ 2, Lemma 3.1 states that the approximation problem is intractable.

For r ≥ 1, it it known that the eigenvalues λ_{j} of the operator S_{1}|_{H_{2}}^{∗}S_{1}|_{H_{2}} are proportional to j^{−2r}. Hence, for r = 1, the approximation problem is strongly tractable iff p_{γ} < ∞, and the strong exponent is max(2p_{γ}, 1).

Example 4.2. We consider spaces similar to those in Example 1, but with a different split between the unweighted and weighted parts. We take H̄_{1} = span(1), the space of constant functions, and

H̄_{2} = span(x, x^{2}, …, x^{r−1}) ⊕ H_{2},

with H_{2} as in Example 1. Then we have F̄_{1,γ} with the kernel

K̄_{1,γ}(x, t) = 1 + γ (∑_{j=1}^{r−1} \frac{x^{j}}{j!} \frac{t^{j}}{j!} + ∫_{0}^{1} \frac{(x − u)_{+}^{r−1}}{(r − 1)!} \frac{(t − u)_{+}^{r−1}}{(r − 1)!} dt) .

This corresponds to the inner product

⟨f, g⟩F̄_{1,γ} = f(0)g(0) + γ^{−1} (∑_{j=1}^{r−1} f^{(j)}(0)g^{(j)}(0) + ∫_{0}^{1} f^{(r)}(t)g^{(r)}(t) dt) .

For this problem, we have dim(S_{1}(H_{1})) = 1. It is known that the eigenvalues λ_{j} of S_{1}|_{H_{2}}^{∗}S_{1}|_{H_{2}} are still of order j^{−2r}. Hence, the approximation problem is strongly tractable iff p_{γ} < ∞, with the strong exponent max(2p_{γ}, r^{−1}).

Acknowledgment

I am grateful for useful comments to P. Gajda, E. Novak, A. G. Werschulz, and G. W. Wasilkowski.

The author was supported in part by the National Science Foundation under Grant CCR-9731858.

References

1. F. J. Hickernell and H. Woźniakowski, Integration and approximation in arbitrary dimensions. Adv. in Comput. Math. 12(2000), 25–58.

2. F. J. Hickernell and H. Woźniakowski, Tractability of multivariate integration for periodic functions. J. Complexity 17(2001), No. 4 (to appear).

3. M. A. Kon, K. Ritter, and A. G. Werschulz, On the average case solvability of ill-posed problems. J. Complexity 7(1991), 220–224.

4. E. Novak and H. Woźniakowski, Intractability results for integration and discrepancy. J. Complexity 17(2001), No. 3 (to appear).

5. E. Novak and H. Woźniakowski, When are integration and discrepancy tractable? Foundations of Computational Mathematics, Oxford, 1999, L. A. DeVore, A. Iserlis and E. Sűli eds. Cambridge University Press, Cambridge, 2001 (to appear).

6. I. H. Sloan and H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complexity 14(1998), 1–33.

7. I. H. Sloan and H. Woźniakowski, Tractability of multivariate integration for weighted Korobov classes. J. Complexity 17(2001), No. 4 (to appear).

8. J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity. Academic Press, New York, 1988.

9. J. F. Traub and A. G. Werschulz, Complexity and information. Cambridge University Press, Cambridge, 1998.

10. N. N. Vakhania, Probability distributions on linear spaces. North-Holland, New York/Oxford, 1981.

11. N. N. Vakhania, V. I. Tarieladze, and S. A. Chobanyan, Probability distributions on Banach spaces. Kluwer, Dordrecht, 1987.

12. N. N. Vakhania, Gaussian mean boundedness of densely defined linear operators. J. Complexity 7(1991), 225–231.

13. G. W. Wasilkowski and H. Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems. J. Complexity 11(1995), 1–56.

14. G. W. Wasilkowski and H. Woźniakowski, Weighted tensor-product algorithms for linear multivariate problem. J. Complexity 15(1999), 402–447.

15. H. Woźniakowski, Tractability and strong tractability of linear multivariate problems. J. Complexity 10(1994), 96–128.

16. H. Woźniakowski, Tractability and strong tractability of multivariate tensor product problems. J. Comput. Inform. 4(1994), 1–19.

17. H. Woźniakowski, Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals. Monte Carlo and Quasi-Monte Carlo Methods, 1998, eds. H. Niederreiter and J. Spanier, Springer Verlag, Berlin, 114–136, 1999.

(Received 1.09.2000)

Author’s addresses:

Department of Computer Science Columbia University New York, NY 10027, U.S.A. E-mail: henryk@cs.columbia.edu Institute of Applied Mathematics University of Warsaw ul. Banacha 2, 02-097 Warsaw, Poland