# Sampling recovery in the uniform norm

David Krieg1, Kateryna Pozharska2,3, Mario Ullrich1, Tino Ullrich3 1Institute
of Analysis, Johannes Kepler University Linz, Austria 2 Institute of
Mathematics of NAS of Ukraine, Kyiv, Ukraine 3 Faculty of Mathematics,
Chemnitz University of Technology, Chemnitz, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>chemnitz.de

###### Abstract.

We study the recovery of functions in the uniform norm based on function
evaluations. We obtain worst case error bounds for general classes of
functions, also in $L_{p}$-norm, in terms of the best $L_{2}$-approximation
from a given nested sequence of subspaces combined with bounds on the the
Christoffel function of these subspaces.
Our results imply that linear sampling algorithms are optimal (up to
constants) among all algorithms using arbitrary linear information for many
reproducing kernel Hilbert spaces; a result that has been observed
independently in [Geng & Wang, arXiv:2304.14748].

###### Key words and phrases:

uniform approximation, information-based complexity, Christoffel function,
optimal sampling

###### 2010 Mathematics Subject Classification:

41A50, 46B09, 46B15, 41A63.

DK is supported by the Austrian Science Fund (FWF) Project M 3212-N. KP would
like to acknowledge support by the Philipp Schwartz Fellowship of the
Alexander von Humboldt Foundation

##  1\. Introduction

The aim of the present paper is to shed further light to the problem of
uniform approximation from samples. Our results can be seen as a continuation
of [44] employing recent results from [6]. We provide a general method to
transfer results for $L_{2}$-approximation to the uniform norm using the
Christoffel function of the involved subspaces. Together with the (optimal)
results for $L_{2}$-approximation from [6], this leads to sharp error bounds
in many scenarios, some of which will be discussed in Section 4.

To explain our results in more detail, let us first introduce the basic
concepts. We fix an arbitrary set $D$ and a measure $\mu$ on $D$. By
$L_{p}=L_{p}(\mu)$, $1\leq p<\infty$, we denote the space of complex-valued
functions that are $p$-integrable with respect to $\mu$, and by
$L_{\infty}=L_{\infty}(\mu)$ the space of essentially bounded functions on
$D$. The norms in the respective spaces are given by

$\displaystyle\|f\|_{p}\ \,:=\,\bigg{(}\int_{D}|f|^{p}\,{\rm
d}\mu\bigg{)}^{1/p},\quad 1\leq p<\infty,$
$\displaystyle\|f\|_{\infty}\,:=\,\underset{x\in
D}{\mu\text{-}\operatorname{ess\,sup}}\,|f(x)|.$

Moreover, we denote by $B(D)$ the space of bounded, complex-valued functions
on $D$ with the sup-norm. For a class $F\subset L_{p}$ and $n\in\mathbb{N}$,
we define the $n$-th linear sampling number in $L_{p}$ by

$\displaystyle
g_{n}^{\mathrm{lin}}(F,L_{p})\,:=\,\inf_{\begin{subarray}{c}x_{1},\dots,x_{n}\in{D}\\\
\varphi_{1},\dots,\varphi_{n}\in L_{p}\end{subarray}}\,\sup_{f\in
F}\,\Big{\|}f-\sum_{i=1}^{n}f(x_{i})\,\varphi_{i}\Big{\|}_{p}.$

This is the _minimal worst case error_ that can be achieved with linear
algorithms based on at most $n$ function values, if the error is measured in
$L_{p}$. We stress that, for $p=\infty$, we approximate in the space
$L_{\infty}(\mu)$ with the weak sup-norm and not in the space $B(D)$ with the
strong sup-norm. However, the two settings often coincide, see Remark 3.

Our goal is to identify properties of classes $F$ that allow for the existence
of good linear sampling recovery algorithms for the uniform norm. The main
assumption here is that there exists a sequence of subspaces $V_{n}$ that are
“good” for $L_{2}$-approximation. In addition, the (inverse of the)
_Christoffel function_ , which is sometimes also called _spectral function_ ,
defined by

(1) $\Lambda_{n}\;:=\;\Lambda(V_{n})\;:=\;\sup\limits_{f\in V_{n},\,f\neq
0}\frac{\|f\|_{\infty}}{\|f\|_{2}}$

will play an important role. This is no surprise as this function (especially
for $V_{n}$ being a space of polynomials) is an important quantity in
approximation theory, see [8, 14, 37], and has already turned out to be
instrumental in proving results in the uniform norm, see e.g. [30, 44]. Note
that for any orthonormal basis $\\{b_{k}\\}_{k=1}^{n}$ of the $n$-dimensional
space $V_{n}$ we have

$\Lambda_{n}=\Big{\|}\sum_{k=1}^{n}\left|b_{k}\right|^{2}\Big{\|}_{\infty}^{1/2}.$

One of the main results of this paper can be stated as follows.

######  Theorem 1.

Let $\mu$ be a finite measure on a set $D$, $(V_{n})_{n=1}^{\infty}$ be a
nested sequence of subspaces of $B(D)$ of dimension $n$, and $F$ be a
separable subset of $B(D)$. Assume that

$\Lambda(V_{n})\;\lesssim\;n^{\beta}\qquad\text{ and }\qquad\sup_{f\in
F}\,\inf_{g\in V_{n}}\|f-g\|_{2}\,\lesssim\,n^{-\alpha}(\log n)^{\gamma}$

for some $\alpha>\beta\geq 1/2$ and $\gamma\in\mathbb{R}$.111The condition on
$\beta$ is no restriction because for a finite measure, where $L_{2}$-norm is
dominated by $L_{\infty}$-norm, we always have $\beta\geq 1/2$. Then, for all
$1\leq p\leq\infty$,

$g_{n}^{\mathrm{lin}}(F,L_{p})\;\lesssim\;n^{-\alpha+(1-2/p)_{+}\beta}(\log
n)^{\gamma}$

with $a_{+}:=\max\\{a,0\\}$.

See Theorem 12 for the general statement with more explicit constants. In
Section 4 we discuss some examples that show that this bound is often sharp up
to constants.

There are numerous results in the literature on uniform approximation, often
for specific classes $F$ and explicit algorithms, see Section 4. The advantage
of Theorem 1 is its generality, as it comes without any possibly redundant
assumption. However, this result is non-constructive. The underlying (least
squares) algorithm is based on a random construction and subsampling based on
the solution of the Kadison-Singer problem, see Remark 5.

To measure the quality of our upper bounds, one may take the Gelfand widths of
the class $F$ as a benchmark. The _$n$ -th Gelfand width_ of $F$ in $L_{p}$ is
defined by

$\displaystyle
c_{n}(F,L_{p})\,:=\,\inf_{\begin{subarray}{c}\psi\colon\mathbb{C}^{n}\to
L_{p}\\\ N\colon F\to\mathbb{C}^{n}\;\text{ linear}\end{subarray}}\;\sup_{f\in
F}\,\big{\|}f-\psi\circ N(f)\big{\|}_{p}$

and measures the worst case error of the optimal (possibly non-linear)
algorithm using $n$ pieces of arbitrary linear information. Unfortunately,
Theorem 1 does not allow for a direct comparison of
$g_{n}^{\mathrm{lin}}(F,L_{\infty})$ and $c_{n}(F,L_{\infty})$. This is
clearly a desirable goal since it corresponds to the question whether, for a
fixed “budget” ($n$) and under the given assumptions on the “problem
instances” ($f\in F$), other algorithms may perform better than linear
algorithms based on function values.

A general bound is due to Novak, see [39, Prop. 1.2.5] or [42, Thm. 29.7],
which states that

(2) $g_{n}^{\mathrm{lin}}(F,L_{\infty})\,\leq\,(1+n)\,c_{n}(F,L_{\infty})$

whenever $F$ is a Banach space. Here and in the following, whenever $F$ is a
normed space, we abuse the definition of the widths by taking the supremum
over the unit ball of $F$ in place of $F$. In fact, Novak’s bound holds for
the Kolmogorov widths instead of the Gelfand widths on the right-hand side,
which is a stronger result that is often better by $\sqrt{n}$. The factor
$(1+n)$, on the other hand, cannot be improved: For each $n$, there even is a
Hilbert space $F$, where (2) is an equality, see [42, Example 29.8]. See also
[19, Thm. 5.2] for a result that complements the above bound for slowly
decaying $c_{n}$.

Here we show that (2) can be improved to an optimal bound (up to constants)
for _reproducing kernel Hilbert spaces_ , which satisfy an additional
boundedness assumption related to the Christoffel function, see Section 2.1
for details.

######  Theorem 2.

There are absolute constants $b,c\in\mathbb{N}$ such that the following holds.
Let $\mu$ be a measure on a set $D$ and $H\subset L_{2}$ be a reproducing
kernel Hilbert space with kernel

$K(x,y)=\sum_{k=1}^{\infty}\sigma_{k}^{2}\,b_{k}(x)\,\overline{b_{k}(y)},\qquad
x,y\in D,$

where $(\sigma_{k})\in\ell_{2}$ is a non-increasing sequence and
$\\{b_{k}\\}_{k=1}^{\infty}$ is an orthonormal system in $L_{2}$ such that
there is a constant $B>0$ with

$\Big{\|}\frac{1}{n}\sum_{k=1}^{n}\left|b_{k}\right|^{2}\Big{\|}_{\infty}\,\leq\,B$

for all $n\in\mathbb{N}$. Under these conditions we have $H\subset L_{\infty}$
and

$g_{bn}^{\mathrm{lin}}(H,L_{\infty})^{2}\,\leq\,cB\sum\limits_{k>n}\sigma_{k}^{2}.$

In particular, if $\mu$ is a finite measure, then

$g_{bn}^{\mathrm{lin}}(H,L_{\infty})\,\leq\,\sqrt{cB\cdot\mu(D)}\cdot
c_{n}(H,L_{\infty}).$

This result has been observed independently in [12, Thm. 2.2] for the
trigonometric system. It represents a special case of a more general result
for reproducing kernel Hilbert spaces where we do not need the uniform
boundedness of the basis, see our Theorem 8 and [12, Thm. 2.1]. These results
further improve on the previous results of [29] in the Hilbert space setting,
see [44, Sect. 5] for a discussion.

Clearly, Theorem 2 can also be applied for other orthonormal systems than the
trigonometric monomials, including the Haar or the Walsh system, certain
wavelets, the Chebychev polynomials, and the spherical harmonics, if $\mu$ is
their corresponding orthogonality measure; see Section 4 for examples. In all
these cases, we obtain that linear sampling algorithms are (up to constants)
as powerful as arbitrary non-linear algorithms using general linear
measurements. Note that we do not require any decay of the Gelfand width
$c_{n}$. In this sense, the comparison statement is even stronger than the
recently obtained result for $L_{2}$-approximation which is discussed below.

To place our findings in a general picture, let us also define the _$n$ -th
linear width_ (or _approximation number_) as

(3) $a_{n}(F,L_{p})\,:=\,\inf_{\begin{subarray}{c}T\colon L_{p}\to L_{p}\\\
{\rm rank}(T)\,\leq\,n\end{subarray}}\,\sup_{f\in
F}\,\big{\|}f-Tf\big{\|}_{p}.$

This is the minimal worst case error over $F$ that can be achieved with
arbitrary linear measurements by using only linear algorithms.
Note that it is a classical result that
$a_{n}(F,L_{\infty})=c_{n}(F,L_{\infty})$ if $F$ is symmetric and convex, but
they are different in many other situations. See [41, Chapter 4] for details
and generalizations.

The numbers $a_{n}$ and $c_{n}$ are well-studied objects in approximation
theory and the geometry of Banach spaces, and are therefore well-known for
many classes $F$. In fact, they fall under the general category of _$s$
-numbers_ which allows the use of some fundamental techniques. We refer to [5,
43] for a general treatment of this, and to [11, 20, 48] for more
approximation theoretic background.

In contrast, the numbers $g_{n}^{\mathrm{lin}}$ do not (yet) fit into such a
general framework, and their dependence on $n$ is often still unknown. It is
therefore of interest, and one of the major concerns of _information-based
complexity_ to determine the relations of all the above widths depending on
properties of the classes $F$, see e.g. [41, 42, 51].
We clearly have the relation $g_{n}^{\mathrm{lin}}\geq a_{n}\geq c_{n}$
whenever function evaluation is a continuous linear functional on $F$ (for
every $x\in D$). However, it is not always clear how large the gaps can be.

An exception is the case of $L_{2}$-approximation: It was recently shown in
[6] that the numbers $g_{n}^{\mathrm{lin}}$ have the same asymptotic decay as
the $a_{n}$, whenever the sequence $(a_{n})$ decays fast enough. In fact, if
$H\hookrightarrow L_{2}(\mu)$ is a separable reproducing kernel Hilbert space,
then we have

$g_{bn}^{\mathrm{lin}}(H,L_{2})\,\leq\,\sqrt{\frac{1}{n}\sum_{k\geq
n}a_{k}(H,L_{2})^{2}}$

for all $n\in\mathbb{N}$ with a universal constant $b\in\mathbb{N}$. For a
much more general family of classes $F$ (like compact subsets of the space of
bounded functions), the similar relation

(4) $g_{bn}^{\mathrm{lin}}(F,L_{2})\,\leq\,\bigg{(}\frac{1}{n}\sum_{k\geq
n}a_{k}(F,L_{2})^{p}\bigg{)}^{1/p}$

is shown for all $p<2$ with a constant $b\in\mathbb{N}$ determined by $p$. See
also [24, 25, 30, 36] for forerunners, [16, 17, 26] for corresponding lower
bounds, and [49, 50] for an approach via Kolmogorov numbers in $L_{\infty}$
which allows for treating the case where the sequence $(a_{k})_{k}$ is not
square summable. We give a slight improvement of (4) in Proposition 11, namely
that

$g_{bn}^{\mathrm{lin}}(F,L_{2})\,\leq\,\sum_{k\geq
n}\frac{a_{k}(F,L_{2})}{\sqrt{k}},$

with a universal constant $b\in\mathbb{N}$. In particular, these results show
that

$g_{n}^{\mathrm{lin}}(F,L_{2})\;\asymp\;a_{n}(F,L_{2}).$

if $a_{n}(F,L_{2})$ decays with a polynomial rate greater than $1/2$, see [6,
Corollary 4]. This shows that function values are asymptotically as powerful
as arbitrary linear information in this case.

Theorem 2 above shows that an analogous relation is true for uniform
approximation without assumption on the main rate $\alpha$, at least for
certain Hilbert spaces.

The remaining paper is structured as follows. In Section 2, we first introduce
some necessary concepts, especially of reproducing kernel Hilbert spaces, and
then prove our results for Hilbert spaces. Section 3 is for our most general
result. In Section 4 we then consider several applications of our theorems.

######  Remark 3 (The sup-norm).

The results in the Hilbert space setting remain true if we replace the
$L_{\infty}(\mu)$-norm by the strong sup-norm (also in the definition of the
Christoffel function). The proof is exactly the same. The same replacement is
allowed in our results for general classes $F$ under the additional assumption
that the sup-norm and the $L_{\infty}(\mu)$-norm coincide on the classes
$V_{m}$ and $F-V_{m}$, $m\in\mathbb{N}$. This is true since the algorithm that
we use to prove the upper bounds maps to $V_{m}$.

######  Remark 4 ($L_{p}$-approximation).

It is interesting that Theorem 1 sometimes leads to sharp results for
$L_{p}$-approximation for both $p=2$ and $p=\infty$ but not for $2<p<\infty$.
This phenomenon appears for the classes of mixed smoothness considered in
Section 4.1. Examples of classes where the bound is optimal for all $1\leq
p\leq\infty$ are isotropic Sobolev spaces on compact Riemannian manifolds, see
Section 4.3.

######  Remark 5 (The algorithm).

It is worth noting that the complexity bounds given above are based on the
very same, but non-constructive, algorithm used in [6]. This is a _weighted
least squares method_ , with specific weights that were introduced in [24] to
prove that $n\log n$ random sampling points (with a specific density) are
“good” for recovery in $L_{2}$, see also [25, 35, 52]. A first subsampling
approach to obtain $n$ optimal points was considered in [36]. This uses a
(finite-dimensional) _frame subsampling_ that is based on the non-constructive
solution to the Kadison-Singer problem. In [6], this was extended to an
infinte-dimensional version, leading to an optimal bound. It is open if this
can be done constructively, see e.g. [2] for first results.

######  Remark 6 (Tractability).

Theorem 2 is particularly useful if we consider approximation for multivariate
functions, e.g. on $D=[0,1]^{d}$, and are interested in the dependence of the
complexity on the dimension $d$, that is, in the tractability of the recovery
problem.
For example, for uniform approximation of periodic functions, the theorem
implies that the curse of dimensionality holds for approximation based on
function values (sometimes called _standard information_) if and only if it
holds for linear information. Details can be found in [12]. The corresponding
statement for $L_{2}$-recovery is not true, see, e.g., [17], but similar
results can be obtained if $c_{n}(H,L_{2})$ decays exponentially with $n$, see
[22].

Notation.  If $H$ is a Hilbert space we denote with $\left\langle
f,g\right\rangle_{H}$ the inner product of $f,g\in H$. By $\log$ we denote the
logarithm with base 2 and $a_{+}:=\max\\{a,0\\}$. For two sequences
$(a_{n})_{n=1}^{\infty},(b_{n})_{n=1}^{\infty}\subset\mathbb{R}$ we write
$a_{n}\lesssim b_{n}$ if there exists a constant $c>0$, such that $a_{n}\leq
cb_{n}$ for all $n$. We write $a_{n}\asymp b_{n}$ if $a_{n}\lesssim b_{n}$ and
$b_{n}\lesssim a_{n}$. If the constant $c$ depends, e.g, on two parameters
$\alpha$ and $\beta$, we indicate it by $\lesssim_{\alpha,\beta}$ and
$\asymp_{\alpha,\beta}$.

##  2\. The Hilbert space setting

We first consider the special case that the class $F$ is the unit ball of a
Hilbert space. For this, we (clearly) need that function evaluation is a well-
defined linear functional for all functions from $F$, and that Hilbert spaces
with this property are called reproducing kernel Hilbert spaces (RKHS).

###  2.1. Preliminaries

Let $H$ be an RKHS of complex-valued functions defined on a set $D$ with a
bounded kernel $K\colon D\times D\rightarrow\mathbb{C}$ of the form

(5) $K(x,y)=\sum_{k=1}^{\infty}\sigma_{k}^{2}\,b_{k}(x)\overline{b_{k}(y)},$

with pointwise convergence on $D\times D$, where
$\sigma_{1}\geq\sigma_{2}\geq\ldots\geq 0$ and $\\{b_{k}\\}_{k=1}^{\infty}$ is
orthonormal in $L_{2}(\mu)$ w.r.t. the measure $\mu$.

For the embedding operator $\operatorname{Id}\colon H\rightarrow L_{2}(\mu)$,
the sequence $(\sigma_{n})_{n=1}^{\infty}$ is the sequence of its singular
numbers. Further we put $e_{k}(x):=\sigma_{k}b_{k}(x)$, $k=1,2,\dots$. The
crucial property for functions $f$ from the RKHS $H$ is the identity

$f(x)=\left\langle f,K(\cdot,x)\right\rangle_{H}$

for all $x\in D$. It ensures that point evaluations are continuous functionals
on $H$. In the framework of this paper, the boundedness of the kernel $K$ is
assumed, i.e.,

(6) $\|K\|_{\infty}:=\sup\limits_{x\in D}\sqrt{K(x,x)}<\infty.$

The condition (6) implies that $H$ is continuously embedded into $L_{\infty}$,
i.e.,

$\|f\|_{\infty}\leq\|K\|_{\infty}\cdot\|f\|_{H}\,.$

Taking into account [46, Lemma 2.6], we have that the set
$\\{e_{k}\\}_{k=1}^{\infty}$ is an orthonormal basis in $H$. Hence, for every
$f\in H$, it holds

$f=\sum_{k=1}^{\infty}\left\langle f,e_{k}\right\rangle_{H}e_{k},$

where $\left\langle f,e_{k}\right\rangle_{H}$, $k=1,2,\dots$, are the Fourier
coefficients of $f$ with respect to the system $\\{e_{k}\\}_{k=1}^{\infty}$.
Let us further denote

$P_{m}f:=\sum\limits_{k=1}^{m}\left\langle f,e_{k}\right\rangle_{H}e_{k}$

the projection onto the space $\operatorname{span}\\{e_{1},...,e_{m}\\}$,
which we denote by $V_{m}$. Due to Parseval’s identity, the norm of the space
$H$ takes the following form

$\|f\|^{2}_{H}=\sum_{k=1}^{\infty}|\left\langle
f,e_{k}\right\rangle_{H}|^{2}.$

We also define

$K_{m}(x,y):=\sum_{k>m}\sigma_{k}^{2}b_{k}(x)\overline{b_{k}(y)},$

i.e., the reproducing kernel of the orthogonal complement of $V_{m}$ in $H$.

###  2.2. The main results

Using the Christoffel function (1), we can lift $L_{2}$-error bounds for
$V_{m}$-valued algorithms to $L_{\infty}$-error bounds.

######  Lemma 7.

For any mapping $A\colon H\to V_{m}$ and all $f\in H$, we have

(7)
$\|f-Af\|_{\infty}\,\leq\,\|K_{m}\|_{\infty}^{1/2}\cdot\|f-P_{m}f\|_{H}\,+\,\Lambda_{m}\cdot\|f-Af\|_{2},$

where

$\|K_{m}\|_{\infty}\,\leq\,2\sum\limits_{k>\lfloor
m/4\rfloor}\frac{\Lambda_{4k}^{2}\sigma_{k}^{2}}{k}.$

###### Proof.

By the triangle inequality,

(8) $\|f-Af\|_{\infty}\,\leq\,\|f-P_{m}f\|_{\infty}+\|P_{m}f-Af\|_{\infty}.$

To estimate the first term in (8), we use that
$(\operatorname{Id}-P_{m})^{2}=\operatorname{Id}-P_{m}$ and that the operator
$\operatorname{Id}-P_{m}$ is self-adjoint, and get, for all $x\in D$,

$\begin{split}\left|(f-P_{m}f)(x)\right|^{2}&=\left|\left\langle(\operatorname{Id}-P_{m})f,K(\cdot,x)\right\rangle_{H}\right|^{2}\\\
&=\left|\left\langle(\operatorname{Id}-P_{m})^{2}f,K(\cdot,x)\right\rangle_{H}\right|^{2}\\\
&=\left|\left\langle(\operatorname{Id}-P_{m})f,(\operatorname{Id}-P_{m})K(\cdot,x)\right\rangle_{H}\right|^{2}\\\
&=\left|\left\langle f-P_{m}f,K_{m}(\cdot,x)\right\rangle_{H}\right|^{2}\\\
&\leq\|f-P_{m}f\|_{H}^{2}\cdot K_{m}(x,x).\end{split}$

We turn to the second term in (8). Since $A$ maps to $V_{m}$, we have
$Af=P_{m}(Af)$, and hence

$\displaystyle\|P_{m}f-$ $\displaystyle
Af\|_{\infty}=\|P_{m}(f-Af)\|_{\infty}$
$\displaystyle\leq\Lambda_{m}\|P_{m}(f-Af)\|_{2}\leq\Lambda_{m}\|f-Af\|_{2}.$

This gives (7). It remains to bound $K_{m}(x,x)$. Using that the sequence
$(\sigma_{n})_{n=1}^{\infty}$ is non-increasing, i.e., for all $2^{\ell}\leq
k<2^{\ell+1}$ it holds

$\sigma_{k}^{2}\leq\frac{1}{2^{\ell-1}}\sum\limits_{2^{\ell-1}<j\leq
2^{\ell}}\sigma_{j}^{2},$

we obtain by a straight-forward calculation

$K_{m}(x,x)\leq\sum_{\ell\geq\lfloor\log m\rfloor}\sum_{2^{\ell}\leq
k<2^{\ell+1}}\sigma_{k}^{2}\left|b_{k}(x)\right|^{2}\leq\sum_{\ell\geq\lfloor\log
m\rfloor}\frac{\Lambda_{2^{\ell+1}}^{2}}{2^{\ell-1}}\sum_{2^{\ell-1}<j\leq
2^{\ell}}\sigma_{j}^{2}\,.$

Hence, in view of the relations $2^{\ell+1}\leq 4j$ and $1/2^{\ell-1}\leq
2/j$, that are true for all $2^{\ell-1}<j\leq 2^{\ell}$, we get

$K_{m}(x,x)\,\leq\sum_{\ell\geq\lfloor\log m\rfloor}\sum_{2^{\ell-1}<j\leq
2^{\ell}}\frac{2\Lambda_{4j}^{2}}{j}\sigma_{j}^{2}\,\leq\,2\sum\limits_{k>\lfloor
m/4\rfloor}\frac{\Lambda_{4k}^{2}\sigma_{k}^{2}}{k}.$

∎

According to [6, Thm. 23], there is a linear algorithm

$A_{m}\colon H\to V_{m}\quad A_{m}(f)=\varphi(f(x_{1}),\ldots,f(x_{n}))$

using $n\leq cm$ samples, satisfying the $L_{2}$-error bound

(9) $\displaystyle\|f-A_{m}f\|_{2}^{2}\,$
$\displaystyle\leq\,433\,\max\bigg{\\{}\sigma_{m+1}^{2},\frac{1}{m}\sum_{k>m}\sigma_{k}^{2}\bigg{\\}}\cdot\|f-P_{m}f\|_{H}^{2}$
$\displaystyle\leq\,\frac{866}{m}\sum_{k>\lfloor
m/2\rfloor}\sigma_{k}^{2}\cdot\|f-P_{m}f\|_{H}^{2}$

for all $f\in H$, where $c>0$ is a universal constant. If we plug this
algorithm into Lemma 7, we immediately get the following result. Recall that
this result has recently also been observed in [12].

######  Theorem 8.

There is an absolute constant $c>0$, such that the following holds. Let
$(D,\Sigma,\mu)$ be a measure space and $H\subset L_{2}(\mu)$ be a RKHS with
bounded kernel $K\colon D\times D\to\mathbb{C}$ of the form (5) and
$\Lambda_{m}$ be defined as in (1). Then it holds for all $m\in\mathbb{N}$
that

$g^{\mathrm{lin}}_{cm}(H,L_{\infty})\,\leq\,\sqrt{\frac{866\,\Lambda_{m}^{2}}{m}\sum_{k>\lfloor
m/2\rfloor}\sigma_{k}^{2}}\,+\,\sqrt{2\sum_{k>\lfloor
m/4\rfloor}\frac{\Lambda_{4k}^{2}\sigma_{k}^{2}}{k}}\,.$

This estimate simplifies a lot in the case that $\Lambda_{m}^{2}$ grows
linearly with $m$, as we stated in Theorem 2 in the introduction. In this
case, our upper bounds are sharp up to constants due to a matching lower bound
on the Gelfand width in $L_{\infty}$. In fact, it has been shown in [40, Thm.
3] that

(10) $\sum_{k>m}\sigma_{k}^{2}\,\leq\,\mu(D)\cdot c_{m}(H,L_{\infty})^{2},$

see also [4, Lemma 3.3], [27, Proposition 2.7], and [29, Thm. 4].

###### Proof of Theorem 2.

We apply Theorem 8 with $4n$ instead of $m$ (and thus $b=4c$) for the upper
bound, and (10) for the lower bound. ∎

######  Remark 9.

The assumption on the basis in Theorem 2 is clearly fulfilled if the basis is
uniformly bounded, i.e., if

$\sup_{k\in\mathbb{N}}\,\sup_{x\in D}|b_{k}(x)|\,\leq\,B.$

For example, this is the case for the trigonometric system on the unit cube
with $B=1$. In this case, we can improve the constants if we use the equality
$\|K_{m}\|_{\infty}=\sum_{k>m}\sigma_{k}^{2}$ in Lemma 7.

##  3\. The general setting

We now formulate similar statements also for the approximation of functions
belonging to arbitrary separable subsets $F\subset L_{\infty}$. We consider
the following setting.

Let $\mu$ be a measure on a set $D$, $(V_{n})_{n=1}^{\infty}$ be a nested
sequence of subspaces of $L_{\infty}$ with dimension $n$, and $F$ be a
separable subset of $L_{\infty}$. For $n\in\mathbb{N}$, define

(11) $\Lambda_{n}\;:=\;\Lambda(V_{n})\;:=\;\sup\limits_{f\in V_{n},\,f\neq
0}\frac{\|f\|_{\infty}}{\|f\|_{2}}$

and

(12) $\alpha_{n}\;:=\;\sup_{f\in F}\|f-P_{V_{n}}f\|_{2}\;=\;\sup_{f\in
F}\,\inf_{g\in V_{n}}\|f-g\|_{2},$

where $P_{V_{n}}$ is the orthogonal projection onto $V_{n}$ in $L_{2}(\mu)$.
We choose an orthonormal system $\\{b_{k}\\}_{k=1}^{\infty}$ such that
$b_{1},\dots,b_{n}$ form a basis of $V_{n}$ for all $n\in\mathbb{N}$.

Again, we first show how to lift $L_{2}$-error bounds to $L_{\infty}$-error
bounds using the Christoffel function $\Lambda_{n}$ and then apply this to
algorithms with good $L_{2}$-error bounds.

######  Lemma 10.

For any mapping $A\colon F\to V_{m}$ and all $f\in F$, we have

(13) $\|f-Af\|_{\infty}\,\leq\,2\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}\Lambda_{4k}}{k}\,+\,\Lambda_{m}\,\|f-Af\|_{2}.$

###### Proof.

Note that there is nothing to prove if the right hand side of (13) is infinite
so we may assume that it is finite. Arguing similarly as in Lemma 7, we first
observe

$\displaystyle\|f-Af\|_{\infty}$
$\displaystyle\leq\,\|f-P_{V_{m}}f\|_{\infty}+\|P_{V_{m}}f-Af\|_{\infty}$
$\displaystyle\leq\,\|f-P_{V_{m}}f\|_{\infty}+\Lambda_{m}\|f-Af\|_{2}.$

In order to estimate $\|f-P_{V_{m}}f\|_{\infty}$, we first show that
$P_{V_{m}}f$ converges almost everywhere to $f$. We observe

$\displaystyle\|Q_{V_{m}}f\|_{\infty}\,:=\,\underset{x\in
D}{{\operatorname{ess\,sup}}}\left|\sum_{k>m}\left\langle
f,b_{k}\right\rangle_{2}b_{k}(x)\right|$
$\displaystyle\leq\sum_{\ell\geq\lfloor\log
m\rfloor}\left(\sum\limits_{2^{\ell}\leq k<2^{\ell+1}}\left|\left\langle
f,b_{k}\right\rangle_{2}\right|^{2}\right)^{1/2}\left(\underset{x\in
D}{{\operatorname{ess\,sup}}}\sum\limits_{2^{\ell}\leq
k<2^{\ell+1}}\left|b_{k}(x)\right|^{2}\right)^{1/2}$
$\displaystyle\leq\sum_{\ell\geq\lfloor\log
m\rfloor}\|f-P_{V_{2^{\ell}}}f\|_{2}\cdot\Lambda_{2^{\ell+1}}\leq\sum_{\ell\geq\lfloor\log
m\rfloor}\alpha_{2^{\ell}}\Lambda_{2^{\ell+1}}.$

Further we use the fact that the sequence $(\alpha_{n})_{n=1}^{\infty}$ is
non-increasing, and therefore

$\alpha_{2^{\ell}}\leq\frac{1}{2^{\ell-1}}\sum\limits_{2^{\ell-1}<j\leq
2^{\ell}}\alpha_{k},$

and hence, since the sequence $(\Lambda_{n})_{n=1}^{\infty}$ is non-
decreasing,

$\begin{split}\|Q_{V_{m}}f\|_{\infty}&\leq 2\sum_{\ell\geq\lfloor\log
m\rfloor}\sum\limits_{2^{\ell-1}<j\leq
2^{\ell}}\frac{\alpha_{j}\Lambda_{2^{\ell+1}}}{2^{\ell}}\\\ &\leq
2\sum_{\ell\geq\lfloor\log m\rfloor}\sum\limits_{2^{\ell-1}<j\leq
2^{\ell}}\frac{\alpha_{j}\Lambda_{4j}}{j}\,\leq\,2\sum_{j>\lfloor
m/4\rfloor}\frac{\alpha_{j}\Lambda_{4j}}{j},\end{split}$

which is convergent due to the assumption. This means that $P_{V_{m}}f$
converges uniformly to some function $g$. Since we also know that $P_{V_{m}}f$
converges to $f$ in $L_{2}(\mu)$, we must have $f=g$ almost everywhere. Thus

$\|f-P_{V_{m}}f\|_{\infty}\,=\,\|Q_{V_{m}}f\|_{\infty},$

which yields the statement. ∎

Now, we could proceed by inserting into Lemma 10 the known error bound for
$L_{2}$-approximation from [6, Thm. 3]. Instead, we provide a slight
improvement of [6, Thm. 3].

######  Proposition 11.

There is an absolute constant $c>0$ such that the following holds. Let $D$,
$\mu$ and $F$ satisfy Assumption A from [6]. Moreover, let
$(V_{m})_{m=1}^{\infty}$ be a nested sequence of subspaces with dimension $m$
and let $(\alpha_{m})_{m=1}^{\infty}$ as in (12). Then, for every
$m\in\mathbb{N}$, there is a linear sampling algorithm $A_{m}\colon F\to
V_{m}$, using at most $cm$ samples, such that

$\sup_{f\in F}\,\|f-A_{m}f\|_{2}\;\leq\;\frac{70}{\sqrt{m}}\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}}{\sqrt{k}}.$

###### Proof.

We follow the lines of [6, Proof of Theorem 3], replacing the numbers
$d_{k}(F)$ by the numbers $\alpha_{k}$, and only choose the parameter sequence
$\sigma$ differently, namely,

$\sigma_{k}^{2}\,:=\,\frac{\alpha_{\lceil k/2\rceil}}{\sqrt{k}}.$

Note that the sequence $(\sigma_{k})_{k=1}^{\infty}$, and thus also the
sequence $(\alpha_{k})_{k=1}^{\infty}$, is square-summable or else we have
nothing to prove. The estimate of $\|f-P_{m}f\|_{H}^{2}$ is replaced with

$\begin{split}\|f-P_{V_{m}}f\|^{2}_{H}\,&=\,\sum_{k>m}\sigma_{k}^{-2}\left|\left\langle
f,b_{k}\right\rangle_{2}\right|^{2}\,\leq\,\sum_{\ell=0}^{\infty}\frac{\sqrt{2^{\ell+1}m}}{\alpha_{2^{\ell}m}}\sum_{k=2^{\ell}m+1}^{2^{\ell+1}m}\left|\left\langle
f,b_{k}\right\rangle_{2}\right|^{2}\\\
&\leq\,\sum_{\ell=0}^{\infty}\sqrt{2^{\ell+1}m}\cdot\alpha_{2^{\ell}m}\,\leq\,\sum_{\ell=0}^{\infty}\sqrt{2^{\ell+1}m}\cdot\frac{1}{2^{\ell-1}m}\sum_{k=\lfloor
2^{\ell-1}m\rfloor+1}^{2^{\ell}m}\alpha_{k}\\\
&\leq\,2\sqrt{2}\sum_{\ell=0}^{\infty}\sum_{k=\lfloor
2^{\ell-1}m\rfloor+1}^{2^{\ell}m}\frac{\alpha_{k}}{\sqrt{k}}\,=\,2\sqrt{2}\sum_{k>\lfloor
m/2\rfloor}\frac{\alpha_{k}}{\sqrt{k}}.\end{split}$

and taking into account that

$\sigma_{m}^{2}\leq\frac{1}{m/2}\sum_{k=\lfloor
m/2\rfloor+1}^{m}\sigma_{k}^{2}\leq\frac{2}{m}\sum_{k>\lfloor
m/2\rfloor}\sigma_{k}^{2}\,\leq\frac{4}{m}\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}}{\sqrt{k}},$

[6, Equation (14)] becomes

$\|f-A_{m}f\|_{2}\;\leq\;\frac{\sqrt{4\cdot 2\sqrt{2}\cdot
433}}{\sqrt{m}}\sum_{k>\lfloor m/4\rfloor}\frac{\alpha_{k}}{\sqrt{k}}\,,$

as claimed. ∎

If we insert the algorithm from Proposition 11 into Lemma 10, we immediately
get the following, which is the main result of this section. The main idea to
prove Proposition 11 and the Theorem below is to construct an appropriate
“intermediate” RKHS $H$ and then apply the bounds available for Hilbert
spaces, i.e., Theorem 23 from [6]. Note that the classes considered here
satisfy Assumption A in [6].

######  Theorem 12.

Let $\mu$ be a finite222The finiteness of the measure ensures that Assumption
A in [6] is satisfied (embedding into $L_{2}$). This assumption might be
redundant. measure on a set $D$, $(V_{n})_{n=1}^{\infty}$ be a nested sequence
of subspaces of $B(D)$ of dimension $n$, and $F$ be a separable subset of
$B(D)$. Moreover, let $\Lambda_{m}$ and $\alpha_{m}$ be defined as in (11) and
(12) and let $c$ be the universal constant from Proposition 11. Then, for all
$m\in\mathbb{N}$, the linear algorithm $A_{m}\colon F\to V_{m}$ from
Proposition 11, that uses at most $cm$ function evaluations, satisfies

$\sup_{f\in F}\,\|f-A_{m}f\|_{\infty}\leq\sum_{k>\lfloor
m/4\rfloor}\frac{2\alpha_{k}\Lambda_{4k}}{k}+\frac{70\Lambda_{m}}{\sqrt{m}}\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}}{\sqrt{k}}.$

If the Christoffel function of the approximation spaces $V_{m}$ shows the
optimal behavior $\sqrt{m}$, our upper bound simplifies as follows.

######  Corollary 13.

There is a universal constant $c\in\mathbb{N}$ such that, whenever the
assumptions of Theorem 12 hold together with $\Lambda_{m}\leq Cm^{1/2}$, then

$g_{cm}^{\mathrm{lin}}(F,L_{\infty})\,\leq\,74C\sum_{k>m}\frac{\alpha_{k}}{\sqrt{k}}.$

###### Proof.

We use Theorem 12 with $4m$ instead of $m$. ∎

For a different rate of growth of $\Lambda_{m}$, we get the asymptotics as
stated in Theorem 1.

###### Proof of Theorem 1.

The upper bound in the case $p\leq 2$ follows from Proposition 11 with

$\frac{1}{\sqrt{m}}\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}}{\sqrt{k}}\,\lesssim_{\alpha}\,m^{-\alpha}(\log
m)^{\gamma}.$

For $p=\infty$, we observe that

$\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}\Lambda_{4k}}{k}\lesssim_{\beta}\sum_{k>\lfloor
m/4\rfloor}k^{-\alpha}(\log
k)^{\gamma}k^{\beta-1}\lesssim_{\alpha,\beta}m^{-\alpha+\beta}(\log
m)^{\gamma}$

and

$\frac{\Lambda_{m}}{\sqrt{m}}\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}}{\sqrt{k}}\lesssim
m^{\beta-\frac{1}{2}}\sum_{k>\lfloor m/4\rfloor}k^{-\alpha-\frac{1}{2}}(\log
k)^{\gamma}\lesssim_{\alpha}m^{-\alpha+\beta}(\log m)^{\gamma},$

such that the stated bound follows from Theorem 12. For $2<p<\infty$, we use
the fact that Theorem 12 and Proposition 11 are proven for the same algorithm
$A_{m}$ and that

$\|f-A_{m}f\|_{p}\,\leq\,\|f-A_{m}f\|_{2}^{2/p}\cdot\|f-A_{m}f\|_{\infty}^{1-2/p}.$

∎

We now would like to give an alternative proof of Theorem 12 which makes the
“intermediate” Hilbert space in Theorem 3 of [6] explicit and even finite-
dimensional.

###### Alternative proof of Theorem 12.

Let $g:=P_{V_{M}}f$, where $M$ depends on $m$ and is chosen later. For $f\in
F$, any linear sampling operator $A_{m}$ (mapping to $V_{m}$) satisfies

(14)
$\|f-A_{m}f\|_{\infty}\leq\,\|f-g\|_{\infty}+\|g-A_{m}g\|_{\infty}+\|A_{m}(g-f)\|_{\infty}.$

Since $M$ is large, $\|f-g\|_{\infty}$ will get small and does not influence
the estimate, see the proof of Lemma 10. We choose a sequence
$(\sigma_{k})_{k=1}^{M}$ such that

$\sigma_{k}^{2}\,:=\,\frac{\alpha_{\lceil k/2\rceil}}{\sqrt{k}}$

and define a density

$\rho_{m,M}(x)=\frac{1}{3}\Big{(}\frac{1}{m}\sum_{k=1}^{m}\left|b_{k}(x)\right|^{2}+\frac{\sum_{k=m+1}^{M}\sigma_{k}^{2}|b_{k}(x)|^{2}}{\sum_{k=m+1}^{M}\sigma_{k}^{2}}+\frac{1}{\mu(D)}\Big{)}.$

For the last term in (14) this leads to the bound

$\|A_{m}(g-f)\|_{\infty}\leq\Lambda_{m}\|g-f\|_{2}\leq
C\Lambda_{m}\left(\frac{1}{n}\sum_{i=1}^{n}\frac{|g(x_{i})-f(x_{i})|^{2}}{\varrho_{m}(x^{i})}\right)^{1/2}$

now for a weighted least-squares algorithm $A_{m}$ described in Remark 5 using
$n$ subsampled random points $(x_{i})_{i=1}^{n}$. Using that the weight
(density) is bounded away from zero we obtain

$\displaystyle\|A_{m}(g-f)\|_{\infty}$ $\displaystyle\leq
C_{\mu}\Lambda_{m}\|g-f\|_{\infty}.$

According to the choice of $g$, the right hand side will be small if $M$ is
large (depending on $m$ and $\mu$). It remains to estimate the term
$\|g-A_{m}g\|_{\infty}$ in (14). To do that we introduce an artificial
$M$-dimensional RKHS $H_{M}$ with the kernel

$K_{M}(x,y)=\sum_{k=1}^{M}\sigma_{k}^{2}b_{k}(x)\overline{b_{k}(y)}$

using the sequence $(\sigma_{k})\in\ell_{2}$ from above. The set
$\\{\sigma_{k}b_{k}\\}_{k=1}^{M}$ is an ONB in $H_{M}$. Let $V_{\ell}$ be the
space spanned by the $b_{\ell}$ with $k\leq\ell$. Hence, $V_{M}\subset H_{M}$.
The norm of functions $g\in H_{M}$ is defined by

$\|g\|_{H_{M}}^{2}:=\sum_{k=1}^{M}\frac{\left|g_{k}\right|^{2}}{\sigma_{k}^{2}}.$

Applying the arguments in the proof in Lemma 10 we estimate
$\|g-A_{m}g\|_{\infty}$. This gives

$\|g-A_{m}g\|_{\infty}\leq 2\sum_{k>\lfloor
m/4\rfloor}\frac{\alpha_{k}\Lambda_{4k}}{k}\,+\,\Lambda_{m}\,\|g-A_{m}g\|_{2}.$

Note, that all arguments in Lemma 10 apply since
$\|g-P_{V_{2^{\ell}}}g\|_{2}\leq\|f-P_{V_{\ell}}f\|_{2}$ and the corresponding
projections commute.

What remains is to estimate $\|g-A_{m}g\|_{2}$. This goes along the lines of
the proof of Proposition 11, where we this time use the finite-dimensional
Hilbert space $H_{M}$ from above together with [6, Thm. 23]. Here it is
important that all arguments in the Hilbert space result in [6, Thm. 23] also
go through with the modified density. Of course, the absolute constants may
change a little, but this is hidden in the constant $n\leq c^{\prime}m$ which
we did not specify here ∎

##  4\. Examples and discussion

We formulate here the main results for a wide range of functional classes
(Hilbert as well as non-Hilbert one). Some details on the calculations are put
into Appendix A. Let $\mathbb{T}=[0,2\pi]$ be a torus where the endpoints of
the interval are identified. By $\mathbb{T}^{d}$ we denote a $d$-dimensional
torus and equip it with the normalized Lebesgue measure $(2\pi)^{-d}{\rm
d}\mathbf{x}$. For functions $f\in L_{1}:=L_{1}(\mathbb{T}^{d})$ we define the
Fourier coefficients
$f_{\mathbf{k}}=(2\pi)^{-d}\int_{\mathbb{T}^{d}}f(\mathbf{x})e^{-i\mathbf{k}\cdot\mathbf{x}}{\rm
d}\mathbf{x}$, $\mathbf{k}\in\mathbb{Z}^{d}$, w.r.t. the trigonometric system
$\left\\{e^{i\mathbf{k}\cdot\mathbf{x}}\colon\mathbf{k}\in\mathbb{Z}^{d}\right\\}$
which forms a $1$-bounded orthonormal basis of $L_{2}$, i.e., for $f\in L_{2}$
we have
$f(\mathbf{x})=\sum_{\mathbf{k}\in\mathbb{Z}^{d}}f_{\mathbf{k}}e^{i\mathbf{k}\cdot\mathbf{x}}$
in the sense of convergence in $L_{2}$.

###  4.1. Hilbert spaces on the $d$-torus

Let us consider the space $H^{w}$ of integrable w.r.t. ${\rm
d}\mu(\mathbf{x})=(2\pi)^{-d}{\rm d}\mathbf{x}$ functions $f$ on the torus
$D=\mathbb{T}^{d}$, such that

$\|f\|^{2}_{H^{w}}=\sum_{\mathbf{k}\in\mathbb{Z}^{d}}(w(\mathbf{k}))^{2}|f_{\mathbf{k}}|^{2}<\infty,$

where $w(\mathbf{k})>0$, $\mathbf{k}\in\mathbb{Z}^{d}$, are certain weights
which satisfy the condition
$\sum_{\mathbf{k}\in\mathbb{Z}^{d}}(w(\mathbf{k}))^{-2}<\infty,$ and
$f_{\mathbf{k}}$ are the Fourier coefficients w.r.t. the trigonometric system
$\left\\{e^{i\mathbf{k}\cdot\mathbf{x}}\colon\mathbf{k}\in\mathbb{Z}^{d}\right\\}=:\\{b_{k}\colon
k\in\mathbb{N}\\}$.

We get the following results, see Appendix A for details.

######  Corollary 14.

There are absolute constants $C,c>0$, such that for the introduced above RKHSs
$H^{w}$ it holds for all $m\in\mathbb{N}$ that

$g_{cm}^{\mathrm{lin}}(H^{w},L_{\infty})\leq
C\sqrt{\sum\limits_{k>m}\sigma_{k}^{2}}\,\leq\,C\cdot
c_{m}(H^{w},L_{\infty}),$

where $\\{\sigma_{k}\colon k\in\mathbb{N}\\}$ is the non-increasing
rearrangement of the sequence
$\\{(w(\mathbf{k}))^{-1}\colon\mathbf{k}\in\mathbb{Z}^{d}\\}$.

The result of Corollary 14 improves the respective estimate from [44, Thm.
6.2] where the authors have an additional $\sqrt{\log m}$-factor on the right
hand side.

In particular, if $w(\mathbf{k})=\prod_{j=1}^{d}(1+|k_{j}|)^{s}$ ,
$\mathbf{k}=(k_{1},\dots,k_{d})\in\mathbb{Z}^{d}$, $s>1/2$, then for the
respective unit ball of the periodic Sobolev space

$H^{s}_{\mathrm{mix}}=\Big{\\{}f\in
L_{2}\colon\,\sum_{\mathbf{k}\in\mathbb{Z}^{d}}|f_{\mathbf{k}}|^{2}\prod_{j=1}^{d}(1+|k_{j}|)^{2s}\leq
1\Big{\\}},$

see, e.g., [28], we obtain the following.

######  Theorem 15.

For $H^{s}_{\mathrm{mix}}$, $s>1/2$, it holds for all $m\in\mathbb{N}$ that

$g_{cm}^{\mathrm{lin}}(H^{s}_{\mathrm{mix}},L_{\infty})\lesssim_{s,d}m^{-s+1/2}\left(\log
m\right)^{s(d-1)}.$

where $c>0$.

The obtained estimate coincides with the known result for sparse grids by
Temlyakov [47]. Note, that in this case we even have the correct order, i.e.,

$g_{cm}^{\mathrm{lin}}(H^{s}_{\mathrm{mix}},L_{\infty})\asymp_{s,d}m^{-s+1/2}\left(\log
m\right)^{s(d-1)}.$

###  4.2. Example of a non-uniformly bounded basis system

Let us consider a case where the Christoffel function is not bounded by
$\sqrt{n}$. For this, we define a second order operator $A$ on $[-1,1]$ by
$Af(x)=-((1-x^{2})f^{\prime})^{\prime}$. Together with the uniform measure
$\rm dx$ on $[-1,1]$, it characterizes for $s>1$ weighted Sobolev spaces

$H(K_{s}):=\\{f\in L_{2}\colon\ A^{s/2}f\in L_{2}\\}\,.$

These spaces are RKHS with the kernel

$K_{s}(x,y)=\sum_{k\in\mathbb{N}}\frac{{L}_{k}(x){L}_{k}(y)}{1+(k(k+1))^{s}}\,,$

where ${L}_{k}\colon[-1,1]\rightarrow\mathbb{R}$, $k\in\mathbb{N}$, are
$L_{2}$-normalized Legendre polynomials. We refer to [3] for the details and
the first $L_{2}$-approximation result for Gauss points.

In this case, the Christoffel function satisfies

$\Lambda_{m}^{2}=\sup_{x\in[-1,1]}\sum_{k=1}^{m}|L_{k}(x)|^{2}=\sum_{k=0}^{m-1}\frac{2k+1}{2}=\frac{m^{2}}{2}\,.$

We get the following result.

######  Theorem 16.

For $H(K_{s})$, $s>1$, it holds for all $m\in\mathbb{N}$ that

(15) $g_{cm}^{\mathrm{lin}}(H(K_{s}),L_{\infty})\,\lesssim_{s}\,m^{-s+1}.$

The estimate (15) is better by a logarithmic factor than those obtained in
Section 6.3 of [44].

###### Proof of Theorem 16 .

From Theorem 8 we have for all $m\in\mathbb{N}$ the following estimate for the
sampling numbers

$g_{cm}^{\mathrm{lin}}(H(K_{s}),L_{\infty})^{2}\leq\sqrt{\frac{m}{2}\sum_{k>\lfloor
m/2\rfloor}\sigma_{k}^{2}}\,+\,4\sqrt{\sum_{k>\lfloor
m/4\rfloor}k\sigma_{k}^{2}}.$

In this setting, we have $\sigma_{k}=(1+(k(k+1))^{s})^{-1/2}$, and hence

$\displaystyle\frac{m}{2}\sum\limits_{k>\lfloor
m/2\rfloor}\sigma_{k}^{2}\lesssim m\sum\limits_{k>\lfloor
m/2\rfloor}k^{-2s}\lesssim_{s}m^{-2s+2},$ $\displaystyle\sum\limits_{k>\lfloor
m/4\rfloor}k\sigma_{k}^{2}\lesssim\sum\limits_{k>\lfloor
m/4\rfloor}kk^{-2s}\lesssim_{s}m^{-2s+2}.$

From this, we obtain

$g_{cm}^{\mathrm{lin}}(H(K_{s}),L_{\infty})\lesssim_{s}m^{-s+1}.$

∎

###  4.3. Sobolev spaces on manifolds

Let $D$ be a compact homogeneous Riemannian manifold equipped with the
normalized volume measure $\mu$. Typical examples are the torus and the
sphere. We let $0=\lambda_{0}<\lambda_{1}<\dots$ be the eigenvalues of the
Laplace-Beltrami operator and $E_{0},E_{1},\dots$ be the corresponding
eigenspaces. The eigenspaces are known to be finite-dimensional and orthogonal
in $L_{2}(\mu)$. We take orthonormal bases
$(b_{\ell,k})_{k\leq\dim(E_{\ell})}$ of the spaces $E_{\ell}$. By the addition
theorem, see [13, Thm. 3.2], we have

$\sum_{k=1}^{\dim(E_{\ell})}|b_{\ell,k}(x)|^{2}\,=\,\dim(E_{\ell}),\quad x\in
D.$

We define the generalized Sobolev spaces $H^{w}=H^{w}(D)$ via the reproduing
kernel

$K(x,y)\,=\,\sum_{\ell=0}^{\infty}w_{\ell}^{2}\sum_{k=1}^{\dim(E_{\ell})}b_{\ell,k}(x)\overline{b_{\ell,k}(y)},$

where we assume that the sequence $(w_{\ell})$ is non-increasing and satisfies

(16) $\sum_{\ell=0}^{\infty}w_{\ell}^{2}\dim(E_{\ell})\,<\,\infty.$

This condition is needed for the kernel to be well-defined and ensures the
boundedness of the kernel at the same time. The classical Sobolev spaces
$H^{s}=H^{s}(D)$ of smoothness $s$ are obtained if we put
$w_{\ell}^{2}=\lambda_{\ell}^{-s}$ and then the relation (16) is satisfied if
and only if $s>\dim(D)/2$, see again [13] and the references therein.

To apply our results, we observe that

$\Lambda_{m}^{2}=m\quad\text{and}\quad
K_{m}(x,x)\,=\,\sum_{\ell>L}^{\infty}w_{\ell}^{2}\,\dim(E_{\ell})$

for all $m$ of the form

$m=\sum_{\ell\leq L}\dim(E_{\ell}),\quad L\in\mathbb{N}_{0}.$

By Lemma 7 and the $L_{2}$-error bound (9) from [6, Thm. 23] we obtain
universal constants $C,c$ such that, for $m$ as above,

(17)
$g_{cm}^{\mathrm{lin}}(H^{w},L_{\infty})\,\leq\,C\max\bigg{\\{}\sqrt{m}\,w_{L+1},\,\sqrt{\sum_{\ell>L}^{\infty}w_{\ell}^{2}\,\dim(E_{\ell})}\bigg{\\}},$

or more generally, for $2\leq p\leq\infty$,

(18)
$g_{cm}^{\mathrm{lin}}(H^{w},L_{p})\,\leq\,Cm^{-1/p}\max\bigg{\\{}\sqrt{m}\,w_{L+1},\,\sqrt{\sum_{\ell>L}^{\infty}w_{\ell}^{2}\,\dim(E_{\ell})}\bigg{\\}}.$

On the other hand, the approximation numbers (as defined in (3)) satisfy
$a_{m}(H,L_{2})=w_{L+1}$ and (10) gives

$a_{m}(H^{w},L_{\infty})\,=\,c_{m}(H^{w},L_{\infty})\,=\,\sqrt{\sum_{\ell>L}^{\infty}w_{\ell}^{2}\,\dim(E_{\ell})}.$

such that (17) alternatively reads

$g_{cm}^{\mathrm{lin}}(H^{w},L_{\infty})\,\leq\,C\max\big{\\{}\sqrt{m}\cdot
a_{m}(H^{w},L_{2}),\,a_{m}(H^{w},L_{\infty})\big{\\}}.$

Note that both terms in the maximum are dominated by $a_{\lfloor
m/2\rfloor}(H^{w},L_{\infty})$. In this sense, standard information (function
values) is as powerful as linear information for the problem of uniform
approximation for all generalized Sobolev spaces on compact homogeneous
Riemannian manifolds.

We also note that the dimension of $E_{\ell}$ increases at most polynomially
(see Weyl’s formula) such that the relation (18) in fact holds for all
$m\in\mathbb{N}$ and a modified constant $c$, now depending on the dimension
of the manifold $D$. It can also be deduced from Weyl’s formula that

$a_{m}(H^{s},L_{\infty})\,\asymp_{D,s}\,m^{-s/\dim(D)+1/2},$

and

$a_{m}(H^{s},L_{2})\,\asymp_{D,s}\,m^{-s/\dim(D)},$

such that we obtain the following.

######  Corollary 17.

There are universal constants $c,C>0$ such that for any $d\in\mathbb{N}$, any
compact homogeneous Riemannian manifold $D$ of dimension $d$, all Sobolev
spaces $H^{w}=H^{w}(D)$ as above, and all $2\leq p\leq\infty$, we have

$g_{cm}^{\mathrm{lin}}(H^{w},L_{p})\,\leq\,Cm^{-1/p}\max\big{\\{}\sqrt{m}\cdot
a_{m}(H^{w},L_{2}),\,a_{m}(H^{w},L_{\infty})\big{\\}},$

whenever $m$ equals the number of eigenvalues of the Laplace-Beltrami smaller
than some $T>0$ (counted with multiplicity).
In particular, for all $1\leq p\leq\infty$ and $s>d/2$,

$g_{m}^{\mathrm{lin}}(H^{s},L_{p})\,\lesssim_{d,s,p}\,m^{-s/d+(1/2-1/p)_{+}}.$

######  Remark 18.

The asymptotic relation

$g_{m}^{\mathrm{lin}}(H^{s},L_{p})\,\asymp_{d,s,p}\,m^{-s/d+(1/2-1/p)_{+}}$

is known. This is a classical result for Sobolev spaces on the cube (see,
e.g., [15, Chapter 6]) and can be transferred to smooth manifolds, e.g., as in
[23]. We refer to [18, Section 3.3] and [7, 14, 31, 32, 33] for more direct
approaches to function recovery on manifolds. Our contributions are the
alternative proof, the dimension-independent constants and a simple almost-
optimal algorithm, see below.

If we insert the algorithm from [24, Thm. 1] instead of [6, Thm. 23] into our
Lemma 7, we obtain the following slightly worse but more practical error
bound. Namely, for all $m=\dim(W_{L})$, where $W_{L}$ denotes the span of the
eigenspaces $E_{0},\dots,E_{L}$, the least-squares algorithm

(19) $A_{n}(f)\,=\,\underset{g\in W_{L}}{\rm
argmin}\,\sum_{i=1}^{n}|f(x_{i})-g(x_{i})|^{2},$

using $n=cm\log(m)$ i.i.d. samples $x_{1},\dots,x_{n}\in D$ distributed
according to the volume measure $\mu$, satisfies with high probability that

$\|f-A_{n}f\|_{p}\,\leq\,Cm^{-1/p}\max\big{\\{}\sqrt{m}\cdot
a_{m}(H^{w},L_{2}),\,a_{m}(H^{w},L_{\infty})\big{\\}}$

for all $f\in H^{w}$ and $2\leq p\leq\infty$. Here, $C,c>0$ are universal
constants again, independent of the dimension.

In particular, we see that i.i.d. random samples are optimal up to a
logarithmic oversampling factor for uniform approximation on such manifolds.
This observation was already made in [23]. We improve upon the corresponding
observation in [23] in the sense of the dimension-independent constants, the
more general sequence $w$, and a possibly simpler algorithm $A_{n}$.

Recall that the logarithmic oversampling factor can be removed by using only a
subset of the random points in (19), but the corresponding subsampling
approach from [6] is non-constructive. We note that there is also a
constructive way to (not remove but) reduce the logarithmic oversampling
factor using the subsampling approach from [2].

Finally, let us mention that our results can also be applied for non-
homogeneous Riemannian manifolds as the asymptotic bound
$\Lambda_{m}\lesssim\sqrt{m}$ remains true in this setting, see [33, Lemma
5.2].

###  4.4. Sobolev- and Besov-Nikol’skii spaces on the $d$-torus

Here, we consider the unit balls of the Sobolev spaces $\mathbf{W}^{r}_{p}$
and the Besov-Nikol’skii spaces $\mathbf{H}^{r}_{p}$ on the $d$-dimensional
torus $D=\mathbb{T}^{d}$.

For $\boldsymbol{s}=(s_{1},\dots,s_{d})$ with $s_{j}\in\mathbb{N}_{0}$,
$j=1,\dots,d$, we define the sets

$\rho(\boldsymbol{s}):=\left\\{(k_{1},\dots,k_{d})\in\mathbb{Z}^{d}\colon\
\lfloor 2^{s_{j}-1}\rfloor\leq\left|k_{j}\right|<2^{s_{j}},\
j=1,\dots,d\right\\},$

and the so-called step hyperbolic crosses

$\Omega_{\ell}\,:=\,\bigcup_{\left|\boldsymbol{s}\right|_{1}\leq\ell}\rho(\boldsymbol{s})\,=\,\left\\{(k_{1},\dots,k_{d})\in\mathbb{Z}^{d}\colon\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}<2^{\ell}\right\\}.$

The cardinality $\left|\Omega_{\ell}\right|$ is of order $2^{\ell}\ell^{d-1}$.
For $f\in L_{1}$ and $\mathbf{x}\in\mathbb{T}^{d}$ we set

$\delta_{\boldsymbol{s}}(f)(\mathbf{x})\,:=\,\sum_{\mathbf{k}\in\rho(\boldsymbol{s})}f_{\mathbf{k}}\,e^{i\mathbf{k}\cdot\mathbf{x}}.$

We now define, for $1<p<\infty$ and $r>0$, the classes

$\mathbf{H}^{r}_{p}\,:=\,\left\\{f\in
L_{1}(\mathbb{T}^{d})\colon\;\sup_{\boldsymbol{s}\in\mathbb{N}_{0}}\,2^{r\left|\boldsymbol{s}\right|_{1}}\,\|\delta_{\boldsymbol{s}}(f)\|_{p}\leq
1\right\\}$

and

$\mathbf{W}^{r}_{p}\,:=\,\left\\{f\in
L_{1}(\mathbb{T}^{d})\colon\;\left\|\left(\sum_{\boldsymbol{s}\in\mathbb{N}_{0}}\,2^{2r\left|\boldsymbol{s}\right|_{1}}\left|\delta_{\boldsymbol{s}}(f)\right|^{2}\right)^{1/2}\right\|_{p}\leq
1\right\\},$

see Appendix A.2 (or [11]) for further details.

We obtain the following result, where $Q_{\ell}$ denotes the set of
trigonometric polynomials with frequencies from a step hyperbolic cross, i.e.,
we put

(20) $Q_{\ell}:=\operatorname{span}\\{e^{i\mathbf{k}\cdot\mathbf{x}}\colon\
\mathbf{k}\in\Omega_{\ell}\\}.$

######  Corollary 19.

There are linear sampling algorithms $A_{m}\colon\mathbf{H}^{r}_{p}\to
Q_{\ell}$, $r>\max\\{1/2,1/p\\}$, $1<p<\infty$, with $m\asymp\dim
Q_{\ell}\asymp 2^{\ell}\ell^{d-1}$ many points, satisfying for $1\leq
q\leq\infty$

$\sup_{f\in{\mathbf{H}^{r}_{p}}}\,\|f-A_{m}f\|_{q}\,\lesssim\,m^{-(r-(\frac{1}{p}-\frac{1}{2})_{+}-(\frac{1}{2}-\frac{1}{q})_{+})}(\log
m)^{(d-1)\left(r+\frac{1}{2}-(\frac{1}{p}-\frac{1}{2})_{+}\right)}.$

In particular, we obtain in case $1<p<\infty$ and $q=2$ the sharp bound

$\sup_{f\in{\mathbf{H}^{r}_{p}}}\|f-A_{m}f\|_{2}\,\asymp\,m^{-(r-(\frac{1}{p}-\frac{1}{2})_{+})}(\log
m)^{(d-1)\left(r+\frac{1}{2}-(\frac{1}{p}-\frac{1}{2})_{+}\right)}\,,$

and the $L_{\infty}$-bounds

$\displaystyle\sup_{f\in{\mathbf{H}^{r}_{p}}}\|f-A_{m}f\|_{\infty}$
$\displaystyle\,\lesssim\,m^{-(r-\frac{1}{p})}(\log
m)^{(d-1)\left(r-\frac{1}{p}+1\right)}\,,\quad 1<p<2,$
$\displaystyle\sup_{f\in{\mathbf{H}^{r}_{p}}}\|f-A_{m}f\|_{\infty}$
$\displaystyle\,\lesssim\,m^{-(r-\frac{1}{2})}(\log
m)^{(d-1)\left(r+\frac{1}{2}\right)}\,,\quad 2\leq p<\infty.$

######  Remark 20.

Let us compare the estimate of Corollary 19 with the bound $m^{-(r-1/p)}(\log
m)^{(d-1)(r-1/p+1)}$ for the uniform recovery of functions from
$\mathbf{H}^{r}_{p}$, $1<p<\infty$, $r>1/p$, on the Smolyak grids (see [10],
[11, Thm. 5.3.3 (ii)] and the references therein). We see, that for $1<p\leq
2$ the $L_{\infty}$-estimates coincide. Note, that it is not known whether
these bounds are sharp. However, for $2<p<\infty$, Smolyak’s algorithm gives
bounds that are better even in the main rate, while in case $p=q=2$ the above
result is asymptotically sharp and better in order than Smolyak.

For the Sobolev classes $\mathbf{W}^{r}_{p}$ we obtain the following.

######  Corollary 21.

There are linear sampling algorithms $A_{m}\colon\mathbf{W}^{r}_{p}\to
Q_{\ell}$, $r>\max\\{1/2,1/p\\}$, $1<p<\infty$, with $m\asymp\dim
Q_{\ell}\asymp 2^{\ell}\ell^{d-1}$ many points, satisfying for $1\leq
q\leq\infty$

$\sup_{f\in{\mathbf{W}^{r}_{p}}}\|f-A_{m}f\|_{q}\lesssim
m^{-(r-(\frac{1}{p}-\frac{1}{2})_{+}-(\frac{1}{2}-\frac{1}{q})_{+})}(\log
m)^{(d-1)(r-(\frac{1}{p}-\frac{1}{2})_{+})},$

In particular, we obtain the $L_{\infty}$-bounds

$\displaystyle\sup_{f\in{\mathbf{W}^{r}_{p}}}\|f-A_{m}f\|_{\infty}$
$\displaystyle\lesssim m^{-(r-\frac{1}{p})}(\log
m)^{(d-1)(r-(\frac{1}{p}-\frac{1}{2}))},\,\quad 1<p<2,$
$\displaystyle\sup_{f\in{\mathbf{W}^{r}_{p}}}\|f-A_{m}f\|_{\infty}$
$\displaystyle\lesssim m^{-(r-\frac{1}{2})}(\log m)^{(d-1)r},\,\quad 2\leq
p<\infty.$

######  Remark 22.

In [9, Cor. 7.8] the worst case recovery guarantees in the uniform norm were
obtained for functions with bounded mixed derivative in a general case. The
authors consider linear Smolyak-type interpolation algorithms and, in our
notation, get the upper bound $m^{-(r-1/p)}$ $(\log m)^{(d-1)(r-2/p+1)}$ for
the approximation of $f\in\mathbf{W}^{r}_{p}$, $1<p<\infty$, $r>1/p$, in
$L_{\infty}$. Comparing this with the estimate of Corollary 21, we see that
the Smolyak’s algorithm gives better bounds in both of the cases $p<2$ and
$p>2$. For $p=2$ the respective bounds coincide and are asymptotically sharp.
Let us emphasize again, that in the case $p=q=2$ the above result is
asymptotically sharp and better in order than Smolyak, see also [6].

###  4.5. Wiener-type and Korobov spaces

For $r>0$, let

$\mathcal{A}^{r}_{\mathrm{mix}}:=\left\\{f\in
L_{1}(\mathbb{T}^{d})\colon\;\sum_{\mathbf{k}\in\mathbb{Z}^{d}}\left|f_{\mathbf{k}}\right|\cdot\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}^{r}\leq
1\right\\}$

be a mixed Wiener class, where $f_{\mathbf{k}}$ are the Fourier coefficients
of $f$ w.r.t. trigonometric system. We obtain (see Appendix A for details)

######  Corollary 23.

For $r>1/2$, there are linear sampling algorithms
$A_{m}\colon\mathcal{A}^{r}_{\mathrm{mix}}\to Q_{\ell}$ with $Q_{\ell}$ from
(20) and $m\asymp\dim Q_{\ell}\asymp 2^{\ell}\ell^{d-1}$ many points,
satisfying

$\sup_{f\in{\mathcal{A}^{r}_{\mathrm{mix}}}}\|f-A_{m}f\|_{q}\lesssim
m^{-(r-(\frac{1}{2}-\frac{1}{q})_{+})}(\log m)^{(d-1)r}.$

for every $1\leq q\leq\infty$. In particular, it holds

$\displaystyle\sup_{f\in{\mathcal{A}^{r}_{\mathrm{mix}}}}\|f-A_{m}f\|_{2}$
$\displaystyle\asymp m^{-r}(\log m)^{(d-1)r},$
$\displaystyle\sup_{f\in{\mathcal{A}^{r}_{\mathrm{mix}}}}\|f-A_{m}f\|_{\infty}$
$\displaystyle\lesssim m^{-(r-\frac{1}{2})}(\log m)^{(d-1)r}.$

######  Remark 24.

From [21, Thm. 5.1 (Remark 6.4)] (putting $\alpha=r$, $p=1$,
$\sigma_{1,q^{\prime}}=0$ and $m\asymp 2^{n}n^{d-1}$), we get the upper bound
$m^{-r}(\log m)^{(d-1)r}$ for the approximation of functions from the weighted
Wiener spaces by sparse grid methods in $L_{q}$, $2\leq q\leq\infty$.
This bound in the case $q=2$ coincides with those obtained in our Corollary
23. This bound is asymptotically sharp as the recent results in [38] on the
Kolmogorov numbers for this embedding show. However, Smolyak-type algorithms
give better in the main rate estimates for the rest $2<q\leq\infty$.

Let us now consider the Korobov classes

$\mathbf{E}^{r}_{d}:=\left\\{f\in
L_{1}(\mathbb{T}^{d})\colon\sup_{\mathbf{k}\in\mathbb{Z}^{d}}\left(\left|f_{\mathbf{k}}\right|\cdot\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}^{r}\right)\leq
1\right\\}.$

We obtain the following.

######  Corollary 25.

For $r>1$, there are linear sampling algorithms
$A_{m}\colon\mathbf{E}^{r}_{d}\to Q_{\ell}$ with $Q_{\ell}$ from (20) and
$m\asymp\dim Q_{\ell}\asymp 2^{\ell}\ell^{d-1}$ many points, satisfying

$\sup_{f\in\mathbf{E}^{r}_{d}}\|f-A_{m}f\|_{q}\lesssim
m^{-(r-\frac{1}{2}-\frac{1}{2}(1-\frac{2}{q})_{+})}(\log m)^{(d-1)r},$

for every $1\leq q\leq\infty$. In particular, it holds

$\displaystyle\sup_{f\in\mathbf{E}^{r}_{d}}\,\|f-A_{m}f\|_{2}\,$
$\displaystyle\asymp\,m^{-(r-\frac{1}{2})}(\log m)^{(d-1)r}\,,$
$\displaystyle\sup_{f\in\mathbf{E}^{r}_{d}}\,\|f-A_{m}f\|_{\infty}\,$
$\displaystyle\lesssim\,m^{-(r-1)}(\log m)^{(d-1)r}.$

Note that we obtain the same bound (but with a different method) for uniform
approximation of functions from the Korobov classes as obtained by Smolyak in
his famous 1963 paper where he introduced sparse grid methods, also known as
Smolyak’s algorithm, see [45, p. 1044].

######  Remark 26.

In the case of $L_{q}$-approximation with $2\leq q<\infty$, one can derive
(better) bounds for $f\in\mathbf{E}^{r}_{d}$ from the embedding
$\mathbf{E}^{r}_{d}\subset\mathbf{H}^{r-1/2}_{2}$. The corresponding estimate
$m^{-(r-1+1/q)}(\log m)^{(d-1)(r-1+2/q)}$ for Smolyak-type algorithms was
obtained in [9, Thm. 6.6] (putting there $r_{1}=r-1/2$, $p=2$,
$\theta=\infty$, $\mu=d$, $m\asymp 2^{n}n^{d-1}$). For $q=2$, the bounds
coincide and are asymptotically sharp. Note, that [21, Thm. 5.1 (Remark 6.4)]
(putting $\alpha=r$, $p=\infty$, $\sigma_{\infty,q^{\prime}}=1-1/q$ and
$m\asymp 2^{n}n^{d-1}$) also yields the upper bound $m^{-(r-1+1/q)}(\log
m)^{(d-1)(r+1/q)}$ for Smolyak-type recovery in $L_{q}$, $2<q<\infty$, which
is worse in the logarithmic rate even than those obtained in our Corollary 25.

##  Appendix A Details on the example section

###  A.1. Hilbert spaces on the $d$-torus

In [4, Thm. 3.1] a necessary and sufficient condition on the weights
$w(\mathbf{k})$ was established, that guarantees the existence of a compact
embedding $H^{w}\hookrightarrow L_{\infty}$:

(21) $\sum_{\mathbf{k}\in\mathbb{Z}^{d}}(w(\mathbf{k}))^{-2}<\infty\,.$

The space $H^{w}$ is a RKHS with the kernel

$K_{w}(\mathbf{x},\mathbf{y})=\sum_{\mathbf{k}\in\mathbb{Z}^{d}}\frac{e^{i\mathbf{k}\cdot(\mathbf{x}-\mathbf{y})}}{\left(w(\mathbf{k})\right)^{2}}\,,$

which is bounded under the condition (21).

###### Proof of Corollary 14.

The singular numbers $\\{\sigma_{k}\colon k\in\mathbb{N}\\}$ of the operator
$\operatorname{Id}\colon H^{w}\to L_{2}$ coincide with $(w(\mathbf{k}))^{-1}$,
which are rearranged in the non-increasing order. Besides,
$\mathcal{B}=\\{b_{k}\colon
k\in\mathbb{N}\\}=\\{e^{i\mathbf{k}\cdot\mathbf{x}}\colon\mathbf{k}\in\mathbb{Z}^{d}\\}$,
and for the basis functions it holds $\|b_{k}\|_{\infty}\leq 1$,
$k=1,2,\dots$. Therefore, from Theorem 2, we get Corollary 14. ∎

###### Proof of Theorem 15.

It is known [1, 34], that for the singular numbers $\sigma_{m}\equiv
c_{m}(H^{s}_{\mathrm{mix}},L_{2})$ it holds
$\sigma_{m}\lesssim_{s,d}m^{-s}(\log m)^{s(d-1)}\,$. Hence, Theorem 15 follows
immediately from Corollary 14 and the calculations:

$\sum_{k>m}\sigma_{k}^{2}\,\lesssim_{s,d}\,\sum_{k>m}k^{-2s}(\log
k)^{2s(d-1)}\,\lesssim_{s,d}\,m^{-2s+1}\left(\log m\right)^{2s(d-1)}.$

∎

###  A.2. Nikol’skii-Besov spaces with bounded mixed difference

We first discuss the spaces $\mathbf{H}^{r}_{p}$, $r>0$, $1<p<\infty$, of
functions with bounded mixed difference. We defined them by the equivalent
norm representation. The definition in terms of a difference operator that
includes the limit cases $p=1$ and $p=\infty$ can be found in [11, Chapter
3.2].

It is known that the embedding $\mathbf{H}^{r}_{p}\hookrightarrow L_{\infty}$
is compact under the condition $r>1/p$. However, we need the sequence
$(\alpha_{n})_{n=1}^{\infty}$ defined by (12) to be square summable, therefore
restrict ourselves in considering $r>\max\\{1/2,1/p\\}$.

###### Proof of Corollary 19.

All of the conditions of Theorem 1 (Theorem 12) are satisfied. Indeed, we
consider the nested sequence of subspaces $Q_{\ell}$, $\ell\in\mathbb{N}$, see
(20). Then, the projection $P_{Q_{\ell}}$ of $f\in\mathbf{H}^{r}_{p}$ takes
the form

$P_{Q_{\ell}}f=\sum_{\mathbf{k}\in\Omega_{\ell}}f_{\mathbf{k}}e^{i\mathbf{k}\cdot\mathbf{x}}.$

The quantity

$\sup_{f\in\mathbf{H}^{r}_{p}}\|f-P_{Q_{\ell}}f\|_{2}$

is nothing else than the best approximation
$\mathcal{E}_{Q_{\ell}}(\mathbf{H}^{r}_{p})_{2}$ of functions from
$\mathbf{H}^{r}_{p}$ by the step hyperbolic cross Fourier sums $S_{Q_{\ell}}$.
We know that for the best approximation by the step hyperbolic cross
polynomials $t\in Q_{\ell}$, i.e.,

$E_{Q_{\ell}}(\mathbf{H}^{r}_{p})_{2}:=\sup_{f\in\mathbf{H}^{r}_{p}}\inf_{t\in
Q_{\ell}}\|f-t\|_{2}$

it holds
$\mathcal{E}_{Q_{\ell}}(\mathbf{H}^{r}_{p})_{2}=E_{Q_{\ell}}(\mathbf{H}^{r}_{p})_{2}$.
Therefore, we can use the estimate

$E_{Q_{\ell}}(\mathbf{H}^{r}_{p})_{2}\asymp
2^{-\ell(r-(\frac{1}{p}-\frac{1}{2})_{+})}l^{\frac{d-1}{2}}\,,\quad
1<p<\infty,$

see [11, Thm. 4.2.6] and the references therein.

Since $\dim{Q_{\ell}}\asymp 2^{\ell}\ell^{d-1}$, we put
$\alpha_{2^{\ell}\ell^{d-1}}:=2^{-\ell(r-(1/p-1/2)_{+})}\ell^{(d-1)/2}$, and
hence

$\alpha_{m}\,\asymp\,m^{-(r-(\frac{1}{p}-\frac{1}{2})_{+})}(\log
m)^{(d-1)\left(r-(\frac{1}{p}-\frac{1}{2})_{+}+\frac{1}{2}\right)}.$

For the trigonometric system, the Christoffel function $\Lambda_{n}=\sqrt{n}$.
Then Theorem 1 with $\alpha=r-(1/p-1/2)_{+}>1/2$ (this holds for
$r>\max\\{1/2,1/p\\}$), $\gamma=(d-1)(r-(1/p-1/2)_{+}+1/2)$ and $\beta=1/2$
yields that there exist linear sampling algorithms
$A_{m}\colon\mathbf{H}^{r}_{p}\to Q_{\ell}$, with $m\asymp\dim Q_{\ell}\asymp
2^{\ell}\ell^{d-1}$ many points, satisfying

$\sup_{f\in\mathbf{H}^{r}_{p}}\|f-A_{m}f\|_{q}\lesssim
m^{-(r-(\frac{1}{p}-\frac{1}{2})_{+})+(\frac{1}{2}-\frac{1}{q})_{+}}(\log
m)^{(d-1)\left(r-(\frac{1}{p}-\frac{1}{2})_{+}+\frac{1}{2}\right)},$

where $1\leq q\leq\infty$. Note, that the condition $r>\max\\{1/2,1/p\\}$
ensures the compact embedding of $\mathbf{H}^{r}_{p}$ in $L_{q}$ for all $p$,
$q$, so the problem is well defined. ∎

###  A.3. Sobolev spaces with bounded mixed derivative

Let us consider the approximation of functions with bounded mixed derivative
from the classes $\mathbf{W}^{r}_{p}$, $r>\max\\{1/2,1/p\\}$, $1<p<\infty$
(see, e.g., [11, Chapter 3.1]).

###### Proof of Corollary 21.

Arguing similarly as above during proving Corollary 19 for the Nikol’skii-
Besov classes, we will use the estimate for the corresponding best
approximation by the step hyperbolic cross polynomials

$E_{Q_{m}}(\mathbf{W}^{r}_{p})_{2}\asymp
2^{-m(r-(\frac{1}{p}-\frac{1}{2})_{+})}\,,\quad
r>\left(\frac{1}{p}-\frac{1}{2}\right)_{+},\ 1<p<\infty,$

see [11, Thm. 4.2.4] and the references therein.

Hence, we put $\alpha_{2^{m}m^{d-1}}:=2^{-m(r-(1/p-1/2)_{+})}$, and therefore

$\alpha_{m}\,\asymp\,m^{-(r-(\frac{1}{p}-\frac{1}{2})_{+})}(\log
m)^{(d-1)(r-(\frac{1}{p}-\frac{1}{2})_{+})}.$

Theorem 1 with $\alpha=r-(1/p-1/2)_{+}$, $\gamma=(d-1)(r-(1/p-1/2)_{+})$ and
$\beta=1/2$ yields the statement of Corollary 21. ∎

###  A.4. Mixed Wiener and Korobov spaces on the torus

We now prove the recovery bound for the mixed Wiener classes
$\mathcal{A}^{r}_{\mathrm{mix}}$ .

###### Proof of Corollary 23.

We have that

$\displaystyle\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\|f-P_{Q_{\ell}}f\|_{2}=\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\|\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{m}}f_{\mathbf{k}}e^{i\mathbf{k}\cdot\mathbf{x}}\|_{2}$
$\displaystyle=\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\left(\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\left|f_{\mathbf{k}}\right|^{2}\right)^{1/2}$
$\displaystyle=\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\left(\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\left|f_{\mathbf{k}}\right|^{2}\prod_{j=1}^{d}(1+\left|k_{j}\right|)^{2r}\prod_{j=1}^{d}(1+\left|k_{j}\right|)^{-2r}\right)^{1/2}$
$\displaystyle\leq\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\sup_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\prod_{j=1}^{d}(1+\left|k_{j}\right|)^{-r}\left(\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\left|f_{\mathbf{k}}\right|^{2}\prod_{j=1}^{d}(1+\left|k_{j}\right|)^{2r}\right)^{1/2}$
$\displaystyle\leq 2^{-\ell
r}\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\left(\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\left|f_{\mathbf{k}}\right|\prod_{j=1}^{d}(1+\left|k_{j}\right|)^{r}\right)\leq
2^{-\ell r}\cdot\|f\|_{\mathcal{A}^{r}_{\mathrm{mix}}}\leq 2^{-\ell r}.$

Hence, since $\dim{Q_{\ell}}\asymp 2^{\ell}\ell^{d-1}$, we put $m\asymp
2^{\ell}\ell^{d-1}$ and get

$\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\|f-P_{V_{m}}f\|_{2}\lesssim
m^{-r}(\log m)^{(d-1)r}.$

The Christoffel function $\Lambda_{n}=\sqrt{n}$. Hence, from Theorem 1 with
$\alpha_{m}=m^{-r}(\log m)^{(d-1)r}$, $\alpha=r>1/2$, $\gamma=(d-1)r$ and
$\beta=1/2$ we get that there are linear sampling algorithms
$A_{m}\colon\mathcal{A}^{r}_{\mathrm{mix}}\to Q_{\ell}$, $r>1/2$, with
$m\asymp\dim Q_{\ell}\asymp 2^{\ell}\ell^{d-1}$ many points, satisfying

$\sup_{f\in\mathcal{A}^{r}_{\mathrm{mix}}}\|f-A_{m}f\|_{q}\lesssim
m^{-(r-(\frac{1}{2}-\frac{1}{q})_{+})}(\log m)^{(d-1)r},$

where $1\leq q\leq\infty$. ∎

Let us finally turn to the Korobov classes.

###### Proof of Corollary 25.

Hence, using similar arguments as above, we get

$\displaystyle\sup_{f\in\mathbf{E}^{r}_{d}}\|f-P_{Q_{\ell}}f\|_{2}$
$\displaystyle=\sup_{f\in\mathbf{E}^{r}_{d}}\left(\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\left|f_{\mathbf{k}}\right|^{2}\cdot\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}^{2r}\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}^{-2r}\right)^{1/2}$
$\displaystyle\leq\;\left(\sum_{\mathbf{k}\in\mathbb{Z}^{d}\setminus\Omega_{\ell}}\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}^{-2r}\right)^{1/2}.$

Note that for $\mathbf{k}=(k_{1},\dots,k_{d})\in\rho(\boldsymbol{s})$ we have
$\prod_{j=1}^{d}\max\\{1,\left|k_{j}\right|\\}^{-2r}\asymp
2^{-2r\left|\boldsymbol{s}\right|_{1}}$. Hence,

$\displaystyle\sup_{f\in\mathbf{E}^{r}_{d}}\|f-P_{Q_{\ell}}f\|_{2}\lesssim\left(\sum_{\left|\boldsymbol{s}\right|_{1}>\ell}2^{-2r\left|\boldsymbol{s}\right|_{1}}\cdot
2^{\left|\boldsymbol{s}\right|_{1}}\right)^{1/2}\lesssim\left(2^{-(2r-1)\ell}\ell^{d-1}\right)^{1/2}$
$\displaystyle=2^{-(r-\frac{1}{2})\ell}\ell^{\frac{d-1}{2}}.$

Hence, from Theorem 1 with $\alpha_{m}=m^{-(r-1/2)}(\log m)^{(d-1)r}$,
$\alpha=r>1/2$, $\gamma=(d-1)r$ and $\beta=1/2$, we get that there are linear
sampling algorithms $A_{m}\colon\mathbf{E}^{r}_{d}\to Q_{\ell}$, $r>1/2$, with
$m\asymp\dim Q_{\ell}\asymp 2^{\ell}\ell^{d-1}$ many points, satisfying

$\sup_{f\in\mathbf{E}^{r}_{d}}\|f-A_{m}f\|_{q}\lesssim
m^{-(r-\frac{1}{2}-(\frac{1}{2}-\frac{1}{q})_{+})}(\log m)^{(d-1)r},$

where $1\leq q\leq\infty$.

The corresponding lower bound for the $L_{2}$-approximation follows from the
embedding $\mathbf{H}^{r}_{1}\subset\mathbf{E}^{r}_{d}$ and the estimate for
the Kolmogorov widths of the classes $\mathbf{H}^{r}_{1}$, $r>1$, in $L_{2}$,
see [11, Thm. 4.3.12]. ∎

Acknowledgement. The authors would like to thank Mathias Sonnleitner for
valuable comments on Section 4.3.

## References

  * [1] K. I. Babenko, About the approximation of periodic functions of many variable trigonometric polynomials, Doklady Akademii Nauk SSSR, 32, 247–250, 1960.
  * [2] F. Bartel, M. Schäfer and T. Ullrich, Constructive subsampling of finite frames with applications in optimal function recovery, Applied. Comput. Harmon. Anal., to appear.
  * [3] C. Bernardi, Y. Maday, Polynomial interpolation results in Sobolev spaces, J. Comput. Appl. Math., 43(1), 53–80, 1992, https://doi.org/10.1016/0377-0427(92)90259-Z.
  * [4] F. Cobos, T. Kühn, W. Sickel, Optimal approximation of multivariate periodic Sobolev functions in the sup-norm, Journal of Functional Analysis, 270(11), 4196–4212, 2016.
  * [5] J. Diestel, Geometry of Banach Spaces – Selected Topics, Lecture Notes in Mathematics, Vol. 485. Springer-Verlag, Berlin-New York, 1975, xi+282 pp.
  * [6] M. Dolbeault, D. Krieg, and M. Ullrich, A sharp upper bound for sampling numbers in $L_{2}$, Appl. Comput. Harmon. Anal. 63 (2023), 113 pp, DOI:10.1016/j.acha.2022.12.001. arXiv:2204.12621, 2022.
  * [7] F. Filbir, R. Hielscher, T. Jahn, T. Ullrich, Marcinkiewicz–Zygmund inequalities for scattered and random data on the $q$-sphere, arXiv:2303.00045.
  * [8] G. Freud, Orthogonale Polynome. Lehrbücher und Monographien aus dem Gebiete der Exakten Wissenschaften, Mathematische Reihe, Band 33. Birkhäuser Verlag, Basel-Stuttgart, 1969.
  * [9] G. Byrenheid, T. Ullrich, Optimal sampling recovery of mixed order Sobolev embeddings via discrete Littlewood-Paley type characterizations, Analisis Matematica, 2017.
  * [10] D. Dũng, On optimal recovery of multivariate periodic functions, In: Har- monic Analysis (Conference Proceedings, Ed. S. Igary), Springer-Verlag 1991, Tokyo-Berlin.
  * [11] D. Dũng, V. N. Temlyakov, and T. Ullrich,  Hyperbolic Cross Approximation.  Advanced Courses in Mathematics - CRM Barcelona. Springer International Publishing, 2018.
  * [12] J. Geng, H. Wang, On the power of standard information for tractability for $L_{\infty}$ approximation of periodic functions in the worst case setting, arXiv:2304.14748.
  * [13] E. Giné, The addition formula for the eigenfunctions of the Laplacian, Advances in Mathematics, 18(1):102–107, 1975.
  * [14] K. Gröchenig, Sampling, Marcinkiewicz-Zygmund inequalities, approximation, and quadrature rules, J. Approx. Theory, 257:105455, 20, 2020.
  * [15] S. Heinrich, Random approximation in numerical analysis, in K. D. Bierstedt and et al., editors, Functional Analysis, pages 123–171. Dekker, New York, 1994.
  * [16] A. Hinrichs, E. Novak and J. Vybiral, Linear information versus function evaluations for $L_{2}$-approximation, Journal of approximation theory, 153(1), 97-107, 2008.
  * [17] A. Hinrichs, D. Krieg, E. Novak and J. Vybiral, Lower bounds for integration and recovery in $L_{2}$, Journal of Complexity, 101662, 2022, https://doi.org/10.1016/j.jco.2022.101662.
  * [18] S. Hubbert, T. M. Morton, Lp-error estimates for radial basis function interpolation on the sphere, J. Approx. Theory, 129(1):58–77, 2004.
  * [19] B. Kashin, S. Konyagin, V. Temlyakov, Sampling discretization of the uniform norm, arXiv:2104.01229.
  * [20] B. Kashin, E. Kosov, I. Limonova, and V. Temlyakov, Sampling discretization and related problems, Journal of Complexity, 101653, 2022, https://doi.org/10.1016/j.jco.2022.101653.
  * [21] Y. Kolomoitsev, T. Lomako, S. Tikhonov, Sparse grid approximation in weighted Wiener spaces, J. Fourier Anal. Appl., 29 (19), 2023, https://doi.org/10.1007/s00041-023-09994-2.
  * [22] D. Krieg, P. Siedlecki, M. Ullrich, and H. Woźniakowski, Exponential tractability of $L_{2}$-approximation with function values, Adv. Comput. Math. 49, 18 (2023). https://doi.org/10.1007/s10444-023-10021-7
  * [23] D. Krieg, M. Sonnleitner, Function recovery on manifolds using scattered data, arXiv:2109.04106, 2021.
  * [24] D. Krieg and M. Ullrich, Function values are enough for $L_{2}$-approximation, Foundations of Computational Mathematics, 21(4), 1141-1151, 2021.
  * [25] D. Krieg and M. Ullrich, Function values are enough for $L_{2}$-approximation: Part II, Journal of Complexity, 66, 101569, 2021, https://doi.org/10.1016/j.jco.2021.101569.
  * [26] D. Krieg and J. Vybíral, New lower bounds for the integration of periodic functions, arXiv:2302.02639, 2023.
  * [27] R. Kunsch, Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods, J. Complexity, 48, 15–35, 2018, https://doi.org/10.1016/j.jco.2018.04.002.
  * [28] T. Kühn, W. Sickel, and T. Ullrich, Approximation of mixed order Sobolev functions on the $d$-torus – asymptotics, preasymptotics and $d$-dependence. Constructive Approximation, 42, 353–398, 2015.
  * [29] F. Kuo, G. W. Wasilkowski, and H. Woźniakowski. Multivariate $L_{\infty}$ approximation in the worst case setting over reproducing kernel Hilbert spaces, Journal of Approximation Theory, 152(2), 135–160, 2008, https://doi.org/10.1016/j.jat.2007.11.006.
  * [30] F. Kuo, G. W. Wasilkowski, and H. Woźniakowski. On the power of standard information for multivariate approximation in the worst case setting, Journal of Approximation Theory, 158, 97–125, 2009.
  * [31] J. Leveslay, X. Sun, Approximation in rough native space by shifts of smooth kernels on spheres, J. Approx. Theory 133:269–283, 2005.
  * [32] H. N. Mhaskar, Weighted quadrature formulas and approximation by zonal function networks on the sphere, J. Complexity, 22(3):348–370, 2006.
  * [33] H. N. Mhaskar, Eignets for function approximation on manifolds, Appl. Comput. Harm. Anal., 29(1):63–87, 2010.
  * [34] B. S. Mityagin, Approximation of functions in $L^{p}$ and $C$ on the torus. Mathematical Notes, 58, 397–414, 1962.
  * [35] M. Moeller and T. Ullrich, $L_{2}$-norm sampling discretization and recovery of functions from RKHS with finite trace, Sampling Theory, Signal Processing, and Data Analysis, 19(2), 1-31, 2021.
  * [36] N. Nagel, M. Schäfer, and T. Ullrich, A new upper bound for sampling numbers, Foundations of Computational Mathematics, 22(2), 445-468, 2022.
  * [37] P. Nevai. _Géza Freud, orthogonal polynomials and Christoffel functions. A case study._ J. Approx. Theory, 48(1):3–167, 1986.
  * [38] V. D. Nguyen, V. K. Nguyen, and W. Sickel, $s$-numbers of embeddings of weighted Wiener algebras. J. Approx. Theory, 279, Paper No. 105745, 2022.
  * [39] E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics 1349, Springer-Verlag, 1988.
  * [40] K. Yu. Osipenko, O. G. Parfenov, Ismagilov type theorems for linear, Gel’fand and Bernstein $n$-widths, J. Complexity, 11(4), 474–492, 1995, http://dx.doi.org/10.1006/jcom.1995.1025.
  * [41] E. Novak and H. Woźniakowski.  Tractability of multivariate problems. Volume I: Linear information, volume 6 of EMS Tracts in Mathematics.  European Mathematical Society (EMS), Zürich, 2008.
  * [42] E. Novak and H. Woźniakowski, Tractability of multivariate problems. Volume III: Standard information for operators, volume 18 of EMS Tracts in Mathematics.  European Mathematical Society (EMS), Zürich, 2012.
  * [43] A. Pietsch, s-Numbers of operators in Banach spaces, Studia Mathematica 51.3 (1974): 201–223.
  * [44] K. Pozharska, T. Ullrich. A note on sampling recovery of multivariate functions in the uniform norm, SIAM J. Numer. Anal., 60(3), 1363–1384, 2022, https://doi.org/10.1137/21M1410580.
  * [45] S. A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Soviet Mathematics Doklady, 4, 240–243, 1963.
  * [46] I. Steinwart, C. Scovel, Mercer’s theorem on general domains: on the interaction between measures, kernels, and RKHSs, Constr. Approx., 35, 363–417, 2012, https://doi.org/10.1007/s00365-012-9153-3.
  * [47] V. N. Temlyakov.  Approximation of periodic functions, Computational Mathematics and Analysis Series, Nova Science Publishers, Inc., Commack, NY, 1993.
  * [48] V. N. Temlyakov.  Multivariate Approximation, volume 32 of Cambridge Monographs on Applied and Computational Mathematics.  Cambridge University Press, 2018.
  * [49] V. N. Temlyakov, On optimal recovery in $L_{2}$, Journal of Complexity, 65, 101545, 2020, https://doi.org/10.1016/j.jco.2020.101545.
  * [50] V. N. Temlyakov, T. Ullrich. Approximation of functions with small mixed smoothness in the uniform norm, Journal of Approximation Theory, 277, 105718, 2022.
  * [51] J. Traub, G. Wasilkowski, H. Woźniakowski, _Information-Based Complexity_ , Acad. Press, 1988.
  * [52] M. Ullrich, On the worst-case error of least squares algorithms for $L_{2}$-approximation with high probability, J. Complexity, 60, 2020.