Available online at www.sciencedirect.com

ScienceDirect
Journal of Approximation Theory 207 (2016) 207–231
www.elsevier.com/locate/jat

Full length article

Sampling on energy-norm based sparse grids for the
optimal recovery of Sobolev type functions in H γ
Glenn Byrenheid a , Dinh D˜ung b,∗ , Winfried Sickel c , Tino Ullrich a
a Hausdorff-Center for Mathematics, 53115 Bonn, Germany
b Information Technology Institute, Vietnam National University, 144, Xuan Thuy, Hanoi, Viet Nam
c Friedrich-Schiller-University Jena, Ernst-Abbe-Platz 2, 07737 Jena, Germany

Received 13 November 2014; received in revised form 8 January 2016; accepted 11 February 2016
Available online 2 March 2016
Communicated by Hans G. Feichtinger

Abstract
We investigate the rate of convergence of linear sampling numbers of the embedding H α,β (Td ) ↩→
H γ (Td ). Here α governs the mixed smoothness and β the isotropic smoothness in the space H α,β (Td )
of hybrid smoothness, whereas H γ (Td ) denotes the isotropic Sobolev space. If γ > β we obtain sharp
polynomial decay rates for the first embedding realized by sampling operators based on “energy-norm
based sparse grids” for the classical trigonometric interpolation. This complements earlier work by Griebel,
Knapek and D˜ung, Ullrich, where general linear approximations have been considered. In addition, we
α (Td ) ↩→ H γ (Td ) and achieve optimality for Smolyak’s algorithm applied
study the embedding Hmix
mix
to the classical trigonometric interpolation. This can be applied to investigate the sampling numbers for
α (Td ) ↩→ L (Td ) for 2 < q ≤ ∞ where again Smolyak’s algorithm yields the

This is motivated by the use of Galerkin methods for the H 1 (Td )-approximation of the solution
of general elliptic variational problems see, e.g., [1,2,17,15,18,25]. The present paper can be
seen as a continuation of [12], where finite-rank approximations in the sense of approximation
numbers were studied. The latter are defined as
am (T : X → Y ) :=

inf

A:X →Y
rank A≤m

sup

∥T f − A f ∥Y ,

m ∈ N,

∥ f ∥ X ≤1

where X, Y are Banach spaces and T ∈ L(X, Y ), where L(X, Y ) denotes the space of all
bounded linear operators T : X → Y . In contrast to that, we restrict the class of admissible
algorithms even further in this paper and deal with the problem of the optimal recovery of H α,β functions from only a finite number of function values, where the optimality in the worst-case
setting is commonly measured in terms of linear sampling numbers
m





gm (T : X → Y ) :=


such that we can ask for the asymptotic decay of the sampling numbers
gm (I1 : H α,β (Td ) → H γ (Td ))
in m. By investing more isotropic smoothness γ ≥ 0 in the target space H γ (Td ) than β ∈ R in
the source space H α,β we encounter two surprising effects for the sampling numbers gm (I1 ) if
γ > β. The main result of the present paper is the following asymptotic order
gm (I1 ) ≍ am (I1 ) ≍ m −(α+β−γ ) ,

m ∈ N,

which shows, on the one hand, the asymptotic equivalence to the approximation numbers and,
on the other hand, the purely polynomial decay rate, i.e., no logarithmic perturbation (see


G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

209

Theorem 6.7). The asymptotic behavior of the approximation numbers am (I1 : H α,β (Td ) →
H γ (Td )) (including the dependence of all constants on d) has been determined in [12], see
also [5,20]. The present paper is intended as a continuation of [12] for the sampling recovery
problem. For the non-periodic situation and more general spaces we refer to the recent paper [10].
See also [11] for a survey on results and bibliography on sampling recovery on sparse grids of
functions having a mixed and more generally, an anisotropic mixed smoothness.
In the critical cases, i.e., γ = β ≥ 0, we are currently not able to give the precise decay rate
of
gm (I2 : H α,β (Td ) → H β (Td ))

(1.2)



m→∞

Due to a telescoping series argument we may also write
f = J1 f +

∞

(J2k − J2k−1 ) f.
k=1

We put for k ∈ N0

J k − J2k−1
ηk := 2
J1

if k > 0,
if k = 0.

We define
qk := ηk1 ⊗ · · · ⊗ ηkd ,

k ∈ Nd0 ,

(1.4)

via the usual tensorization procedure. This construction allows for proving
 the useful tool of a
sampling representation of functions f ∈ H α,β (Td ) by the series f = k∈Nd qk ( f ) with the


or by an ε-modification of it given by
∆ε (ξ ) = ∆(ε, α, β, γ ; ξ )
:= {k ∈ Nd0 : (α − ε) |k|1 − (γ − β − ε)|k|∞ ≤ ξ },

ξ > 0,

(1.7)

and ε > 0 chosen smaller than min{α, γ − β}. These index sets will be used in connection with
the embedding (1.1). The set of sampling points used by (1.5) will be called “energy-norm based
sparse grid” (see Figs. 1 and 2).

Fig. 1. d = 2, α = 2, β = 0, γ = 1, ξ = 20.

Fig. 2. d = 2, α = 1, ξ = 20.

This phrase stems from the works of Bungartz, Griebel and Knapek [1,2,15,17,18] and refers
to the special case where the error is measured in the “energy space” H 1 (Td ). These authors were
the first observing the potential of this modification of the classical Smolyak sparse grid [32]. The
index set (1.6) has been considered for approximation numbers in [12], and the index sets (1.6)
and (1.7) for sampling numbers in the recent paper [10]. Note, that the approximation scheme
in this paper is build upon the classical trigonometric interpolation, see (1.3), using the Dirichlet
kernel itself. Hence, the sets of equidistant interpolation nodes in (1.3) are in general not nested.
For more comments in this direction and how to modify the setting to guarantee a nestedness
property we refer to Remark 4.4.
α (Td )
The paper is organized as follows. In Section 2 we define and discuss the spaces Hmix
α,β
d

if an bn and bn an holds.
2. Sobolev-type spaces
In this section we recall the definition of the function spaces under consideration here. They
α (Td )
are all of Sobolev-type. In a first subsection we consider the periodic Sobolev spaces Hmix
of dominating mixed fractional order α > 0. In the second subsection the more general classes
H α,β (Td ) are discussed.
2.1. Periodic Sobolev spaces of mixed and isotropic smoothness
All results in this paper are stated for function spaces on the d-torus Td , which is represented
in the Euclidean space Rd by the cube Td = [0, 2π ]d , where opposite faces are identified. The
space L 2 (Td ) consists of all (equivalence classes of) measurable functions f on Td such that the
norm

1/2
∥ f ∥2 :=
| f (x)|2 d x
Td

is finite. All information on a function f ∈ L 2 (Td ) is encoded in the sequence (ck ( f ))k of its
Fourier coefficients, given by

1
f (x) e−ikx d x, k ∈ Zd .
ck ( f ) :=
(2π )d Td
Indeed, we have Parseval’s identity

∥ f ∥22 = (2π )d
|ck ( f )|2
k∈Zd

212

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

We also need the (isotropic) Sobolev spaces H γ (Td ).
Definition 2.2. Let γ ≥ 0. The periodic Sobolev space H γ (Td ) of smoothness γ is the collection
of all f ∈ L 2 (Td ) such that


γ 1/2
|ck ( f )|2 1 + |k|22
< ∞.
∥ f ∥#H γ (Td ) :=
k∈Zd

Remark 2.3. It is elementary to check
α
(Td ) ↩→ H α (Td ).
H αd (Td ) ↩→ Hmix

In addition it is known that H γ (Td ) ↩→ C(Td ) if and only if H γ (Td ) ↩→ L ∞ (Td ) if and only if
γ > d/2, see [29].
2.2. Hybrid type Sobolev spaces
α (Td ) obtained by adding isotropic
To define the scale H α,β (Td ) we look for subspaces of Hmix
smoothness. This motivates the following definition.

Definition 2.4. Let α ≥ 0 and β ∈ R such that α + β ≥ 0. The generalized periodic Sobolev
space H α,β (Td ) is the collection of all f ∈ L 2 (Td ) such that
∥ f ∥#H α,β (Td ) :=

More important for us will be the embedding
0,β

H α,β (Td ) ↩→ H γ (Td )

if 0 ≤ γ ≤ α + β.

(ii) Spaces of such a type have been first considered by Griebel and Knapek [17]. Also in the
non-periodic context they play a role in the description of the fine regularity properties of
certain eigenfunctions of Hamilton operators in quantum chemistry, see [37]. The periodic
α,β
spaces Hmix (Td ) also occur in the recent works [12,16].
A first step towards the sampling representation in Theorem 3.6 will be the following
equivalent characterization of Littlewood–Paley type. We will work with the dyadic blocks on the
Fourier side. As usual, δℓ ( f ), ℓ ∈ Nd0 , represents that part of the Fourier series of f supported
in a dyadic block
Pℓ := Pℓ1 × · · · × Pℓd ,
where P j := {ℓ ∈ Z :
≤ |ℓ|

T ℓ :=
|ki |≤2ℓi
i=1,...,d

Of course, δℓ ( f ) ∈ T ℓ for all f ∈ L 2 (Td ).
Lemma 2.7 (Nikol’skij’s Inequality). Let 0 < p ≤ q ≤ ∞. Then there is a constant C =
C( p, q) > 0 (independent of g and ℓ) such that
|ℓ|1 ( 1p − q1 )

∥g∥q ≤ C2

∥g∥ p

holds for every g ∈ T ℓ and every ℓ ∈ Nd0 .
Proof. A proof can be found in [23, Theorem 3.3.2].
To give a meaning to point evaluations of functions it is essential that the spaces under
consideration contain only continuous functions. To be more precise, they contain equivalence
classes of functions having one continuous representative.
Theorem 2.8. Let α > 0, β ∈ R such that min{α + β, α + βd } > 21 . Then
H α,β (Td ) ↩→ C(Td ).
Proof. Applying Lemma 2.7 yields


∥δk ( f )∥∞ =
2α|k|1 +β|k|∞ 2−(α|k|1 +β|k|∞ ) ∥δk ( f )∥∞
k∈Nd0

k∈Nd0




2−2(α|k|1 +β|k|∞ ) 2|k|1

1

2

∥ f ∥ H α,β (Td ) .


214

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

Using |k|∞ ≤ |k|1 ≤ d|k|∞ gives in case β ≥ 0


β 1
2−2(α|k|1 +β|k|∞ ) 2|k|1 ≤
2−2(α+ d − 2 )|k|1 < ∞,
k∈Nd0

k∈Nd0

whenever α + βd > 12 . For the case β < 0 observe that


1
2−2(α|k|1 +β|k|∞ ) 2|k|1 ≤
2−2(α+β− 2 )|k|1 < ∞

α+β
Hmix (Td ) : β < 0.
This embedding immediately implies Theorem 2.8.
(ii) The restrictions in Theorem 2.8 are almost optimal. Indeed, let g ∈ H α+β (T), then the
function
f (x1 , . . . , xd ) := g(x1 ),

x ∈ Rd ,

belongs to H α,β (Td ). Hence, from H α,β (Td ) ↩→ C(Td ) we derive H α+β (T) ↩→ C(T)
which is known to be true if and only if α + β > 1/2. In case α = 0 we know
H α,β (Td ) = H β (Td ). Hence, H 0,β ↩→ C(Td ) if and only if β/d > 1/2.
We will need the following Bernstein type inequality.
Lemma 2.10. Let min{α, α + β − γ } > 0 and ℓ ∈ Nd0 . Then
∥ f ∥ H α,β (Td ) ≤ 2α|ℓ|1 +(β−γ )|ℓ|∞ ∥ f ∥ H γ
holds for all f ∈ T ℓ .
Proof. Indeed, for f ∈ T ℓ , we have

∥ f ∥2H α,β (Td ) =
22(α|k|1 +β|k|∞ ) ∥δk ( f )∥22
ki ≤ℓi
i=1,...,d

≤ max 22(α|k|1 +(β−γ )|k|∞ )
ki ≤ℓi
i=1,...,d


ki ≤ℓi
i=1,...,d

Case 2. Let β < 0. From (3.1) and
|k ′ |∞ − |k|∞ ≤ |k ′ − k|∞ ≤ |k ′ − k|1
we obtain
ψ(k) ≤ ψ(k ′ ) − (α + β)|k ′ − k|1 .
Recall the linear operator qk has been defined in (1.4). Let us settle the following cancellation
property.
Lemma 3.2. Let ℓ, k ∈ Nd0 with kn < ℓn for some n ∈ {1, . . . , d}. Let further f ∈ T k and qℓ be
the operator defined in (1.4). Then qℓ ( f ) = 0.
Proof. Since f ∈ T k we have

f =
am eimx
k
|m j |≤2 j
j=1,...,d

and
qℓ ( f )(x) =



am qℓ (eim· )(x) =

kj

|m j |≤2
j=1,...,d




k∈Nd0

converging unconditionally in H α,β (Td ), and satisfying the condition

22(α|k|1 +β|k|∞ ) ∥qk ( f )∥22 ≤ C∥ f ∥2H α,β (Td )

(3.3)

k∈Nd0

with a constant C = C(α, β, d) > 0.
Proof. Step 1. We first prove (3.3) for f ∈ H α,β (Td ). We choose α˜ such that
1
< α˜ < min{α, α + β}.
2

(3.4)

For any ℓ ∈ Nd0 we have that

f =
δℓ+k ( f )

(3.5)

k∈Zd

with the convention δm ( f ) := 0 if m ∈ Zd \ Nd0 . Linearity of qℓ and the triangle inequality
implies


˜ 1
∥qℓ ( f )∥2
2α|k|
∥δℓ+k ( f )∥2 .

(3.6)

k∈Nd0

This together with Lemma 3.1 leads to

˜
1 2α|ℓ+k|1 +β|ℓ+k|∞ ∥δ
2α|ℓ|1 +β|ℓ|∞ ∥qℓ ( f )∥2
2(α−min{α,α+β})|k|
ℓ+k ( f )∥2 .
k∈Nd0

(3.7)


G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

217

We proceed taking the ℓ2 (Nd0 )-norm with respect to the index ℓ on the left-hand side of (3.7).
The triangle inequality in ℓ2 (Nd0 ) yields

 α|ℓ| +β|ℓ|
∞ ∥q ( f ) ∥ 

ℓ
2 ℓ (Nd )
2 ℓ
2

0

0


d
2 (N0 )

˜
1.
2(α−min{α,α+β})|k|

k∈Nd0

Due to the choice of α˜ in (3.4) the sum is converging and we obtain

 α|ℓ| +β|ℓ|

 α|ℓ| +β|ℓ|
∞ ∥δ ( f ) ∥ 
∞ ∥q ( f ) ∥ 
2 1
2 1
ℓ
ℓ

∥ f ∥2H α,β (Td ) ≤ C
22(α|k|1 +β|k|∞ ) ∥ f k ∥22 .
k∈Nd0

Proof. Similar to (3.5) for ℓ ∈ Nd0 we write f as the series

f =
f ℓ+k
k∈Zd

with f ℓ+k := 0 for k + ℓ ∈ Zd \ Nd0 . Clearly, δℓ : L 2 (Td ) → L 2 (Td ) is an orthogonal projection.
The projection properties of the operator δℓ together with f k ∈ T k yields

∥δℓ ( f )∥2 ≤
∥δℓ ( f ℓ+k )∥2 .
k∈Nd0

Thanks to ∥ δℓ ∥ L 2 (Td )→L 2 (Td ) = 1 we conclude

∥δℓ ( f )∥2 ≤
∥ f ℓ+k ∥2 .
k∈Nd0

This together with Lemma 3.1 yields

2α|ℓ|1 +β|ℓ|∞ ∥δℓ ( f )∥2
2− min{α,α+β}|k|1 2α|ℓ+k|1 +β|ℓ+k|∞ ∥ f ℓ+k ∥2 .
k∈Nd0

(3.8)

:=
H α,β (Td )



22(α|k|1 +β|k|∞ ) ∥qk ( f )∥22

1
2

k∈Nd0

for all f ∈ H α,β (Td ).
Theorem 3.6. Let min{α, α + β} > 12 . Then a function f on Td belongs to the space H α,β (Td ),
if and only if f can be represented by the series (3.2) converging in H α,β (Td ) and satisfying the
.
condition (3.3). Moreover, the norm ∥ f ∥ H α,β (Td ) is equivalent to the norm ∥ f ∥+
H α,β (Td )
Proof. This result is an easy consequence of Propositions 3.3 and 3.4, applied with f k =
qk ( f ).
Remark 3.7. (i) The restriction min{α, α + β} >

1
2

is essentially optimal, see Remark 2.9.

(ii) The potential of sampling representations was first recognized for H¨older–Nikol’skij type
spaces of mixed smoothness by D˜ung [7,8]. Sampling representations for non-periodic
functions in connection with tensor product B-spline series have been treated in [9,10].

k̸∈∆ε (ξ )



≤

γ |k|∞

2

k̸∈∆ε (ξ )

∥qk ( f )∥2

k̸∈∆ε (ξ )



=

2α|k|1 +β|k|∞ 2−(α|k|1 +β|k|∞ ) 2γ |k|∞ ∥qk ( f )∥2

k̸∈∆ε (ξ )

≤

 

2−2α|k|1 +2(γ −β)|k|∞


2−2α|k|1 +2(γ −β)|k|∞

k̸∈∆ε (ξ )

1
2

∥ f ∥ H α,β (Td ) .

(4.1)

Step 2. Now we consider the sum


2−2α|k|1 +2(γ −β)|k|∞ ≤

k̸∈∆ε (ξ )

d


i=1

2−2α|k|1 +2(γ −β)|k|∞ ,

k̸∈∆ε (ξ )
k∈K i

where
K i := {k ∈ Nd0 : ki = |k|∞ } i = 1, . . . , d.



220

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

Using this equivalence we can proceed with


˜
2−2α|k|1
2−2α|k|1 +2(γ −β)|k|∞ =
k̸∈∆ε (ξ )
k∈K 1



˜ d−1
k∈N
0

=



˜ ∞ −1,
k1 >max |k|
˜





2−2α|k|1

2−2αk1 +2(γ −β)k1 ,

˜
ξ −(α−ε)|k|
k1 > α−(γ −β) 1

k̸˜ ∈ I1

where



˜1
ξ − (α − ε)|k|
d−1
˜
˜
I 1 = k ∈ N0 :
< |k|∞ .
α − (γ − β)
First we compute an upper bound for the sum in (4.4). Because of
˜

˜

22((γ −β)−α)|k|∞ ≤ 2−2(ξ −[α−ε])|k|1

2−2ξ



˜

2−2ε|k|1

˜ 1
k∈I
−2ξ

2

.

Here the constant behind does not depend on ξ .
Step 2. Next, we estimate the sum in (4.5). Similarly as above we find



˜
˜
˜
2−2αk1 +2(γ −β)k1
2−2α|k|1 2−2(ξ −(α−ε)|k|1 )
2−2α|k|1
k̸˜ ∈ I1

k1 >

221

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

Remark 4.3. Estimates of sampling operators of Smolyak-type with respect to the non-periodic
α ([0, 1]d ) → H γ ([0, 1]d ) may be found also in the papers [1,2,15,25]. The
embeddings I : Hmix
authors have used energy-norm based sparse grids in case α = 2 and γ = 1. The smoothness
restriction α ≤ 2 in the source space is caused by the use of the hierarchical Faber system (hat
function). Using trigonometric interpolation we do not encounter any smoothness restrictions
here and so the algorithm is able to exploit arbitrarily high smoothness. However, the above
mentioned authors cared for the dependence of all constants on the dimension d, an important
issue in high-dimensional approximation, which we have ignored here. Let us also mention [12]
in this respect.
Remark 4.4. We have already mentioned in the introduction that the interpolation nodes in
(1.3) are not nested in general. For the theoretical purposes in this paper it does not play a
role. However, for practical issues nestedness properties might decrease the computational effort
significantly. This can be fixed by using a small modification of Jm , which we call J˜m , defined by

1 2m−1
f (π ℓ/m) D˜ m (t − π ℓ/m),
J˜m f (t) :=
2m ℓ=0
where D˜ m (x) := Dm (x) − e−imx = e−i(m−1)x (ei2mx − 1)(ei x − 1)−1 . A similar operator has
been studied recently in [16].

5. Sampling on Smolyak grids

In this section we intend to apply our new method to situations where the classical Smolyak
algorithm is used. On the one hand we give shorter proofs for existing results and extend some

0


q (f)
fk = k
0

: k ̸∈ ∆(ξ ),
: k ∈ ∆(ξ ).


222

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

Note, that the only restriction for Proposition 3.4 is γ > 0. Clearly, f − Q ∆(ξ ) f =
and hence

∥ f − Q ∆(ξ ) f ∥2H γ (Td )
22γ |k|1 ∥ f k ∥22
mix



k∈Nd0

fk

k∈Nd0


and 0 < γ < α. Then there is a constant C = C(α, γ , d) > 0 such

∥ f − Q ∆(ξ ) f ∥ H γ (Td ) ≤ C2−ξ ∥ f ∥ H α

mix (T

d)

α (Td ) and ξ > 0.
holds for all f ∈ Hmix

Remark 5.3. Sampling with Smolyak operators has some history. Closest to us are
Temlyakov [33,35,34] and D˜ung [7–10], see also [13,27,28,30]. In almost all contributions
preference was given to situations where the target space was L q (Td ). Let us also refer to a
recent publication of Griebel and Hamaekers [16].
5.2. The case α > γ − β = 0
Now we are interested in the embedding
I : H α,β (Td ) → H β (Td ).
The sampling operator Q ∆(ξ ) is determined by ∆(ξ ) from (1.6) with γ = β. Let us simplify the
structure by considering the index sets ∆(αm) for m ∈ N which consists of all k ∈ Nd0 satisfying
|k|1 ≤ m.
Theorem 5.4. Let β = γ ≥ 0 and α > 21 . Then there is a constant C = C(α, β, d) > 0 such
that
∥ f − Q ∆(αm) f ∥ H β (Td ) ≤ C2−mα m

d−1
2

∥ f ∥ H α,β (Td )


 
1  
1
2
2
∥ f − Q ∆(αm) f ∥2 ≤
2−2α|k|1
22(α|k|1 +β|k|∞ ) ∥qk ( f )∥22 .
|k|1 >m

|k|1 >m

Employing the upcoming lemma and Theorem 3.6 finishes the proof.
Lemma 5.5. Let α > 0. Then

2−2α|k|1 m d−1 2−2αm
|k|1 >m

holds for all m > 0.
Proof. This lemma is well known, but see, e.g., [3] for all details.
5.3. The case γ = 0
From Theorem 5.4 we immediately obtain the special case (γ = β = 0)
∥ f − Q ∆(αm) f ∥2 ≤ C2−mα m

d−1
2

∥ f ∥H α

mix (T

∥ f − Q ∆(αm) f ∥∞ = 
qk ( f ) ≤
∞

k̸∈∆(αm)

≤





∥qk ( f )∥∞

k̸∈∆(αm)

2|k|1 /2 2α|k|1 2−α|k|1 ∥qk ( f )∥2

|k|1 >m

≤

 

2−2|k|1 (α− 2 )
1

|k|1 >m

1  

holds true for any f ∈ L q (Td ), where the right-hand side may be infinite.

1−1
q

2
Hmix

(Td )


224

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

Proof. The proof of the first relation in Lemma 5.7 is elementary using the Littlewood–Paley
decomposition in L q (Td ) together with q/2 ≥ 1, see for instance [34, Theorem 0.3.2, Page 20].
The second relation follows by an application of Nikol’skij’s inequality in Lemma 2.7.
Remark 5.8. Let us mention that Lemma 5.7 can be refined to


q 1/q
∥ f ∥q
2q|k|1 (1/2−1/q) ∥δk ( f )∥2
.
k∈Nd0

For this deep result we refer to [34, Lemma II.2.1] and to [9, Lemma 5.3] as well as
[24, Lemma 1] for non-periodic versions. In a more general context this embedding is a special
case of a Jawerth–Franke type embedding, see [19].

(i) The index sets ∆(α, β, γ ; ξ ) defined in (1.6) and ∆(ε, α, β, γ ; ξ ) defined in (1.7) are solid
sets in the sense of Lemma 6.1 for every ξ > 0.
(ii) The index set ∆(α; ξ ) is defined in (1.6) with γ = β is a solid set for every ξ > 0.


G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

225

Proof. The second result is trivial. We prove the first one. Let
ψ(k) := α|k|1 − (γ − β)|k|∞ .
The set ∆(ξ ) consists of all k ∈ Nd0 with ψ(k) ≤ ξ . Applying Lemma 3.1 yields
ψ(k ′ ) ≤ ψ(k) ≤ ξ
for all k ′ ≤ k ∈ ∆(ξ ). That means all the k ′ also belong to ∆(ξ ).

In the next lemma we give sharp estimates for k∈∆(ξ ) 2|k|1 with ∆(ξ ) from (1.6).
Lemma 6.3. Let α > 0, γ ≥ 0, β ∈ R such that γ > β and α > γ − β. Then

ξ
2|k|1 ≍ 2 α−(γ −β)
k∈∆(ξ )

holds for all ξ ≥ α − (γ − β), where the constants behind “≍” only depend on α, γ − β, and d.
Proof. Step 1. First we deal with the upper bound. We are going to use the same notation as in
(4.2) and (4.3). We obtain the following inequality


2|k|1 ≤

k∈∆(ξ )

|k|

˜1
ξ − α|k|
˜ ∞ ≤ ξ.
˜ 1 + (α − (γ − β))|k|
⇐⇒ α|k|
α − (γ − β)

We shall use these inequalities to produce an appropriate decomposition of K 1 ∩ ∆(ξ ) which
results in


2|k|1 ≤ d

k∈∆(ξ )

˜



2|k|1

˜ d−1
k∈N
0
˜ +(α−(γ −β))|k|
˜ ∞ ≤ξ
α|k|
1


−α˜

2 α−(γ −β)

˜1
|k|


226

G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

Step 2. We prove the lower bound. First we claim that


ξ
k ∗ :=
(1, 0, . . . , 0) ∈ ∆(ξ ).
α − (γ − β)
Indeed,
k ∗ ∈ ∆(ξ ) ⇐⇒ α|k ∗ |1 − (γ − β)|k ∗ |∞ ≤ ξ




ξ
ξ
− ((γ − β) − ε)
≤ξ

rank Q ∆(ξ ) ≍ 2 α−(γ −β) ,

ξ ≥ α − (γ − β),

where the constants behind “≍” only depend on α, γ − β, and d.
Proof. Clearly, Jm f uses 2m + 1 values of function f , hence ηm f is using ≤ 2m+2 function
values. This implies that qk f applies ≤ 22d 2|k|1 function values. As a consequence of Lemma 6.3
we find that Q ∆(ξ ) f is using

ξ
2|k|1 ≍ 2 α−(γ −β)
k∈∆(ξ )

function values of f . Part (ii) follows from Lemma 6.1 and the lower bound in Lemma 6.3.
Let us now count the degrees of freedom for a classical Smolyak grid.
Lemma 6.5. For any d ∈ N and m ∈ Nd0 , we have the inequality
 m + d − 1 d−1
 e(m + d − 1) d−1

2m ≤
2|k|1 ≤
2m+1 .
d −1
d
−
1
|k| ≤m
1

Proof. This assertion is a direct consequence of [12, Lemma 3.10] together with the well-known

≍ m −(α−γ +β) ,

m ≥ 1.

Proof. Step 1. Let α > γ − β > 0. We claim
an (I : H α,β (Td ) → H γ (Td )) ≍ n −α+γ −β ,

n ∈ N.

This has been proved in [12, Theorem 4.7], however, with the additional restriction that
2(γ −β) > α > γ −β. For the convenience of the reader we give a proof without this restriction.
The lower bound is a consequence of a well-known abstract result (see [36, Theorem 1] or [21,
Theorem 1.4, p. 405]) on lower bounds for linear n-widths, namely
Lemma 6.8. Let L n+1 be an n + 1-dimensional subspace in a Banach space X , and Bn+1 (r ) :=
{ f ∈ L n+1 : ∥ f ∥ X ≤ r }. Then
λn (Bn+1 (r ), X ) ≥ r.
Here λn (Bn+1 (r ), X ) denotes the linear n-width of the set Bn+1 (r ) in X .
We apply this lemma with X = H γ and L n+1 to be the subspace of all trigonometric polynomials
with frequencies in H∆(ξ ) from (6.1) with ∆(ξ ) = ∆(α, β, γ ; ξ ) and ξ chosen accordingly. From
Lemma 6.3 we get n ≍ 2ξ/(α−(γ −β)) . We immediately see the Bernstein type inequality
∥ f ∥ H α,β

2ξ ∥ f ∥ H γ ,

f ∈ L n+1 .

(6.2)

Hence, by choosing r := 2−ξ we get from (6.2) that Bn+1 (r ) is contained in the unit ball of
H α,β . Finally, by Lemma 6.8 we conclude

This proves the estimate from above in case m = Dε . The corresponding estimate for all m
follows by a simple monotonicity argument.
Remark 6.9. In case β = 0 Griebel and Hamaekers recently proved a similar upper bound
for gm (I1 ) (see [16, Lemma 9]). Under the conditions of Theorem 6.7 the family of sampling
operators Q ∆ε (ξ ) for 0 < ε < γ − β is optimal in order. A non-periodic version of Theorem 6.7
has been proved recently by D˜ung [10].
The next two theorems collect results for sampling numbers which are based on Smolyak’s
algorithm.
Theorem 6.10. Let α > 1/2 and suppose 0 < γ < α.
(i) We have for m ≥ 2
γ

γ

α
α
(Td ) → Hmix (Td ))
(Td ) → Hmix (Td )) ≍ am (I5 : Hmix
gm (I5 : Hmix

≍ m −(α−γ ) (log m)(d−1)(α−γ ) .
(ii) Let 2 < q < ∞. Then we have for m ≥ 2
α
α
gm (I4 : Hmix
(Td ) → L q (Td )) ≍ am (I4 : Hmix
(Td ) → L q (Td ))

≍m


α
am (I : Hmix
(Td ) → L 2 (Td )) ≍ m −α (log m)α(d−1) ,

2 ≤ m ∈ N,

(6.3)

holds true for any α > 0 and is due to Galeev [14]. In case α > γ ≥ 0 we use a simple lifting
argument to obtain
γ

α−γ

α
am (I : Hmix
(Td ) → Hmix (Td )) ≍ am (I : Hmix (Td ) → L 2 (Td ))

≍ m −(α−γ ) (log m)(d−1)(α−γ ) ,

2 ≤ m ∈ N.

Note, that a similar lifting argument does in general not apply for sampling numbers gm .


G. Byrenheid et al. / Journal of Approximation Theory 207 (2016) 207–231

229

Step 2. Proof of (i). By Step 1 we obtain for m ≥ 2


log D(n) ≍ n.

Rewriting (6.4) gives
∥ f − Q ∆((α−γ )n) f ∥ H γ

mix (T

d)

D(n)−(α−γ ) (log D(n))(d−1)(α−γ ) .

Obvious monotonicity arguments complete the proof.
Step 3. Proof of (ii). The estimate from below for the approximation numbers is due to
Romanyuk [22]. The corresponding estimate from above for the sampling numbers is an
immediate consequence of Lemma 5.7 together with (i), where γ = 1/2 − 1/q.
Step 4. Proof of (iii). For the lower bound by approximation numbers we follow Step 1. The
upper bound is obtained similar to (i) applying Theorem 5.4 and Corollary 6.6(i), (ii).
Step 5. Proof of (iv).
The estimate from below for the approximation numbers is due to Temlyakov [35]. Let us
mention that this lower bound is also implied by a recent general result by Cobos, K¨uhn and
Sickel [6]. The estimate from above for sampling numbers follows from Theorem 5.6 combined
with Corollary 6.6(i), (ii) in the same way as in (i).
Theorem 6.11. Let α > 1/2 and β ≥ 0. Then it holds
m −α (log m)α(d−1) ≍ am (I2 : H α,β (Td ) → H β (Td ))
≤ gm (I2 : H α,β (Td ) → H β (Td ))
m −α (log m)(d−1)(α+ 2 ) ,
1

m ≥ 2.

Remark 6.12. As we have mentioned before, not all the results in Theorem 6.10 are new. A
non-periodic version of (ii) has been proved recently by D˜ung [9]. What concerns (iii) let us
refer to [9,28,30,31] where even more general situations are treated. Part (iv) reproduces a result
due to Temlyakov [35]. Note, that our methods allow for proving this result in the framework
of classical trigonometric interpolation, see Theorem 5.6, whereas Temlyakov had to use de la
Vall´ee-Poussin sampling operators. In any case, it is remarkable that Smolyak’s algorithm yields
optimal bounds here.
Acknowledgments
The authors would like to thank the organizers of the HCM-workshop “Discrepancy,
Numerical Integration, and Hyperbolic Cross Approximation”, where this work has been
initiated, for providing a pleasant and fruitful working atmosphere. In addition, the authors
would like to thank the Hausdorff-Center for Mathematics (HCM) and the Bonn International
Graduate School (BIGS) for providing additional financial support to finish this work. Dinh
D˜ung’s research work is funded by Vietnam National Foundation for Science and Technology
Development (NAFOSTED) under Grant No. 102.01-2014.02, and a part of it was done when he
was working as a research professor at the Vietnam Institute for Advanced Study in Mathematics
(VIASM). He would like to thank the VIASM for providing a fruitful research environment and
working condition.
References
[1] H.-J. Bungartz, M. Griebel, A note on the complexity of solving Poisson’s equation for spaces of bounded mixed
derivatives, J. Complexity 15 (1999) 167–199.
[2] H.-J. Bungartz, M. Griebel, Sparse grids, Acta Numer. 13 (2004) 147–269.
[3] G. Byrenheid, Dinh D˜ung, W. Sickel, T. Ullrich, Sampling on energy-norm based sparse grids for the optimal
recovery of Sobolev type functions in H γ , arXiv:1408.3498.
[4] G. Byrenheid, T. Ullrich, Optimal sampling recovery of mixed order Sobolev embeddings via discrete
Littlewood–Paley type characterizations, Preprint, Bonn.
[5] A. Chernov, Dinh D˜ung, New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic
crosses and approximation of functions having mixed smoothness, J. Complexity 32 (2016) 92–121.
[6] F. Cobos, T. K¨uhn, W. Sickel, Optimal approximation of Sobolev functions in the sup-norm, Preprint, Leipzig,
2014.

Math. J. 16 (4) (2009) 667–682.
[20] T. K¨uhn, W. Sickel, T. Ullrich, Approximation of mixed order Sobolev functions on the d-torus: asymptotics,
preasymptotics, and d-dependence, Constr. Approx. 42 (2015) 353–398.
[21] G.G. Lorentz, M. von Golitschek, Y. Makovoz, Constructive Approximation. Advanced Problems, in: Grundlehren
der Mathematischen Wissenschaften, vol. 304, Springer-Verlag, Berlin, 1996.
[22] A.S. Romanyuk, Linear widths of the Besov classes of periodic functions of many variables. II, Ukrain. Math. Zh.
53 (2001) 965–977.
[23] H.J. Schmeißer, H. Triebel, Topics in Fourier Analysis and Function Spaces, Wiley, Chichester, 1987.
[24] H.-J. Schmeisser, W. Sickel, Spaces of functions of mixed smoothness and their relations to approximation from
hyperbolic crosses, J. Approx. Theory 128 (2004) 115–150.
[25] Ch. Schwab, E. S¨uli, R.A. Todor, Sparse finite element approximation of high-dimensional transport-dominated
diffusion problems, ESAIM Math. Model. Numer. Anal. 42 (05) (2008) 777–819.
[26] W. Sickel, Some remarks on trigonometric interpolation on the n-torus, Z. Anal. Anwend. 10 (1991) 551–562.
[27] W. Sickel, Approximate recovery of functions and Besov spaces of dominating mixed smoothness, in: Constructive
theory of functions, Varna 2002, DARBA, Sofia, 2003, pp. 404–411.
[28] W. Sickel, Approximation from sparse grids and function spaces of dominating mixed smoothness, Banach Center
Publ. 72 (2006) 271–283.
s type, Z. Anal.
[29] W. Sickel, H. Triebel, H¨older inequalities and sharp embeddings in function spaces of B sp,q and F p,q
Anwend. 14 (1995) 105–140.
[30] W. Sickel, T. Ullrich, Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed
smoothness, East J. Approx. 13 (2007) 387–425.
[31] W. Sickel, T. Ullrich, Spline interpolation on sparse grids, Appl. Anal. 90 (2011) 337–383.
[32] S.A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl.
Akad. Nauk 148 (1963) 1042–1045.
[33] V.N. Temlyakov, Approximation recovery of periodic functions of several variables, Mat. Sb. 128 (1985) 256–268.
[34] V.N. Temlyakov, Approximation of Periodic Functions, Nova Science, New York, 1993.
[35] V.N. Temlyakov, On approximate recovery of functions with bounded mixed derivative, J. Complexity 9 (1993)
41–59.
[36] V.M. Tikhomirov, Widths of sets in function spaces and the theory of best approximations, Uspekhi Mat. Nauk 15