#  A sharp upper bound for
sampling numbers in $\mathbf{L}_{\mathbf{2}}$

Matthieu Dolbeault1 and David Krieg2,3 and Mario Ullrich2 1Sorbonne
Université, Paris, France  2Institut für Analysis, Johannes Kepler Universität
Linz, Austria  3RICAM, Austrian Academy of Sciences, Linz, Austria.
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

For a class $F$ of complex-valued functions on a set $D$, we denote by
$g_{n}(F)$ its sampling numbers, i.e., the minimal worst-case error on $F$,
measured in $L_{2}$, that can be achieved with a recovery algorithm based on
$n$ function evaluations. We prove that there is a universal constant
$c\in\mathbb{N}$ such that, if $F$ is the unit ball of a separable reproducing
kernel Hilbert space, then

$g_{cn}(F)^{2}\,\leq\,\frac{1}{n}\sum_{k\geq n}d_{k}(F)^{2},$

where $d_{k}(F)$ are the Kolmogorov widths (or approximation numbers) of $F$
in $L_{2}$. We also obtain similar upper bounds for more general classes $F$,
including all compact subsets of the space of continuous functions on a
bounded domain $D\subset\mathbb{R}^{d}$, and show that these bounds are sharp
by providing examples where the converse inequality holds up to a constant.
The results rely on the solution to the Kadison-Singer problem, which we
extend to the subsampling of a sum of infinite rank-one matrices.

###### Key words and phrases:

$L_{2}$-approximation, information-based complexity, least squares, rate of
convergence, random matrices, Kadison-Singer

###### 2010 Mathematics Subject Classification:

41A25, 41A45, 46B09, 46B15, 60B20.

DK is supported by the Austrian Science Fund Project F5506, which is part of
the Special Research Program _Quasi-Monte Carlo Methods: Theory and
Applications_.

##  1\. Introduction and main results

The general question of how well point-wise evaluations perform for
approximating a function, which is often called _sampling recovery_ or
approximation using _standard information_ , is a classical question in
theoretical and applied mathematics. A historical treatment and various basics
may be found in the monographs [9, 10, 11, 49, 61] for general approximation
theory and in [41, 42, 43] for information-based complexity. It is of
particular interest to compare the _power of function evaluations_ with the
power of optimal linear measurements (which could be Fourier coefficients or
derivatives), since the latter are well understood in many cases and easier to
handle from a theoretical point of view, while the first are of larger
practical relevance. The quest for a systematic comparison has attracted much
attention recently. We will describe the history and related results below
after presenting the setting and the main results, see also Section 1.1.

The _power_ of a given class of measurements is often expressed in terms of
the minimal error achievable with a given amount of such information. Here, we
consider $L_{2}$-approximation in a worst-case setting, so that these minimal
errors correspond to sampling numbers and Kolmogorov (or approximation)
numbers, as we summarize below.

Let $(D,\mathcal{A},\mu)$ be a measure space and
$L_{2}:=L_{2}(D,\mathcal{A},\mu)$ be the space of square-integrable complex-
valued functions on $D$. Let $F$ be a set of functions contained in $L_{2}$.
The _Kolmogorov widths_ of $F$ in $L_{2}$ are defined by

$d_{k}(F)\,:=\,\inf_{\begin{subarray}{c}\ell_{1},\dots,\ell_{k}\colon
F\to\mathbb{C}\\\ \varphi_{1},\dots,\varphi_{k}\in
L_{2}\end{subarray}}\,\sup_{f\in
F}\,\Big{\|}f-\sum_{i=1}^{k}\ell_{i}(f)\,\varphi_{i}\Big{\|}_{L_{2}}.$

This is the worst-case error of an optimal approximation within a linear space
of dimension $k$. It coincides with the $k$th approximation number (or linear
width) of $F$, which is the worst-case error of an optimal linear algorithm
that uses at most $k$ linear functionals as information, see Remark 5. On the
other hand, the _sampling numbers_ are given by

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

i.e., $g_{n}(F)$ is the minimal worst-case error of linear algorithms based on
$n$ function evaluations. Therefore, the task is to compare the numbers
$d_{k}(F)$ and $g_{n}(F)$.

It is clear that we have $g_{n}(F)\geq d_{n}(F)$. Here, we aim for an upper
bound of $g_{n}(F)$ in terms of the numbers $d_{k}(F)$. We first describe the
situation where $F$ is the unit ball of a separable reproducing kernel Hilbert
space (RKHS). A priori, it is not clear whether such a bound is even possible.
And indeed, there can be no such bound in the case that
$(d_{k}(F))\notin\ell_{2}$. More precisely, it is shown in [13] that for any
non-negative and non-increasing sequence $(\sigma_{k})\notin\ell_{2}$ and any
sequence $(\tau_{n})$ tending to infinity, e.g. $\tau_{n}=\log\log n$, there
exists a RKHS with unit ball $F$ such that $d_{k}(F)=\sigma_{k}$ for all $k$
but $\limsup_{n\to\infty}\tau_{n}\cdot g_{n}(F)>0$.

The situation is completely different when $(d_{k}(F))\in\ell_{2}$, which is
equivalent to assuming that the kernel $K$ of the Hilbert space has finite
trace

(1) $\int_{D}K(x,x)\,d\mu(x)<\infty,$

see, e.g., [37]. Under this assumption, first upper bounds on $g_{n}(F)$ in
terms of the numbers $d_{k}(F)$ were obtained more than 20 years ago in [59].
These upper bounds were later improved in [27, 30, 38]. On the other hand, a
lower bound from [17, Theorem 2] tells us how far these improvements might go:
for every non-negative and non-increasing $(\sigma_{k})\in\ell_{2}$, there
exists a separable RKHS with unit ball $F$ such that $d_{k}(F)=\sigma_{k}$ for
all $k\in\mathbb{N}$ and

(2) $g_{\lfloor m/8\rfloor}(F)\,\geq\,\sqrt{\frac{1}{m}\sum_{k\geq
m}d_{k}(F)^{2}}$

for infinitely many values of $m\in\mathbb{N}$. And indeed, it turns out that
this is already the worst possible scenario. The main result of this paper is
an upper bound, which matches the above lower bound (2) up to a universal
constant, and which is true for any separable reproducing kernel Hilbert
space.

######  Theorem 1.

There is a universal constant $c\in\mathbb{N}$ such that the following holds.
Let $\mu$ be a measure on a set $D$ and let $F\subset L_{2}(\mu)$ be the unit
ball of a separable RKHS on $D$ such that the finite trace assumption (1)
holds. Then, for all $m\in\mathbb{N}$, we have

$g_{cm}(F)\,\leq\,\sqrt{\frac{1}{m}\sum_{k\geq m}d_{k}(F)^{2}}.$

This settles the question on the power of standard information compared to
general linear information for the problem of $L_{2}$-approximation on Hilbert
spaces, and solves the open problems from [17, 27], Open Problem 140 in [43],
as well as Outstanding Open Problem 1.4 in [11] for $L_{2}$-approximation. The
latter is discussed in Example 28, where we consider tensor product spaces. We
note that the case of $L_{p}$-approximation ($p\neq 2$) is widely open. A
slightly stronger version of Theorem 1 and explicit constants are given in
Theorem 23.

Let us add that, in principle, Theorem 1 does only imply the _existence_ of
(linear) sampling algorithms achieving the error bound. However, all upper
bounds on $g_{n}(F)$ will be obtained by a suitable (unregularized) _least
squares method_ , see Remark 7 and Section 5.

Theorem 1 is a direct continuation of the series of works initiated in [27],
in which the sampling numbers were bounded by

$g_{\lfloor c\,m\log m\rfloor}(F)\,\leq\,\sqrt{\frac{1}{m}\sum_{k\geq
m}d_{k}(F)^{2}},$

see also [19, 55], and an improvement from [38], where the logarithmic
oversampling was removed in exchange for an additional factor $\sqrt{\log m}$
on the right hand side.

The ingredients for the proof are still the existence of good point sets with
$\mathcal{O}(m\log m)$ points from [27], and a subsampling of $\mathcal{O}(m)$
points based on the solution to the Kadison-Singer problem [34]. The Kadison-
Singer subsampling has already been applied for the related problem of
sampling discretization in [32] (see [20] for a survey) and was subsequently
introduced to the study of sampling numbers in [38, 50]. In these papers, the
subsampling was, roughly speaking, only performed for a finite-dimensional
sub-problem which resulted in the excessive factor $\sqrt{\log m}$ in [38].
The new ingredient here is an infinite-dimensional version of the subsampling
theorem that might be of independent interest, see Proposition 17.

If we apply Theorem 1 and the lower bound from [17] to sequences with
polynomial decay, we obtain the following characterization.

######  Corollary 2.

Let $F$ be the unit ball of a separable RKHS with

(3) $d_{n}(F)\,\lesssim\,n^{-\alpha}\log^{-\beta}n$

for some $\alpha\geq 1/2$, $\beta\in\mathbb{R}$ and $c>0$. Then

(4)
$g_{n}(F)\,\lesssim\,\begin{cases}n^{-\alpha}\log^{-\beta}n\quad&\text{if}\
\alpha>1/2,\\\\[2.0pt] n^{-\alpha}\log^{-\beta+1/2}n\quad&\text{if}\
\alpha=1/2\text{ and }\beta>1/2.\end{cases}$

Moreover, there exist classes $F$ such that these bounds are sharp.

Here, $a_{n}\lesssim b_{n}$ means that there is a constant $c>0$ such that
$a_{n}\leq cb_{n}$ for all but finitely many $n\in\mathbb{N}$; later we will
also use the symbols $\gtrsim$ and $\asymp$ which are defined accordingly. It
is clear from Theorem 1 that the hidden constant in (4) is given by the
product of the hidden constant in (3) and a constant that only depends on
$\alpha$ and $\beta$.

We now turn to general function classes $F$ that are assumed to satisfy the
following assumption.

Assumption A. Let $F$ be a class of complex-valued functions on a set $D$ and
let $\mu$ be a measure on $D$. We say that $F$ and $\mu$ satisfy Assumption A,
if there is a metric on $F$ such that $F$ is continuously embedded into
$L_{2}$, separable, and function evaluation $f\mapsto f(x)$ is, for each $x\in
D$, continuous on $F$.

Note that Assumption A is satisfied, for example, if

  * •

$F$ is a separable subset of the space of bounded functions equipped with the
maximum distance and the measure $\mu$ is finite, or

  * •

$F$ is the unit ball of a separable normed space that is continuously embedded
in $L_{2}$ and on which function evaluation at each point is a continuous
functional, or

  * •

$F$ is a countable set of square-integrable functions, equipped with the
discrete metric.

In this setting, we prove the following bound.

######  Theorem 3.

Let $0<p<2$. There is a constant $c_{p}\in\mathbb{N}$, depending only on $p$,
such that for any $F$ and $\mu$ that satisfy Assumption A and all
$m\in\mathbb{N}$,

$g_{c_{p}m}(F)\,\leq\,\bigg{(}\frac{1}{m}\sum_{k\geq
m}d_{k}(F)^{p}\bigg{)}^{1/p}.$

Theorem 3 is an improvement over [28], where again we removed the excessive
logarithmic factor. We will also show that the result is not true for $p=2$,
see Example 30. However, we provide a variant of Theorem 3 under the weaker
condition $\big{(}(\log k)^{s}d_{k}(F)\big{)}\in\ell_{2}$ for some $s>1/2$ in
Section 6.2. This leads to the following corollary.

######  Corollary 4.

Let $F$ and $\mu$ satisfy Assumption A and

(5) $d_{n}(F)\,\lesssim\,n^{-\alpha}\log^{-\beta}n$

for some $\alpha>0$ and $\beta\in\mathbb{R}$. Then

(6)
$g_{n}(F)\,\lesssim\,\begin{cases}n^{-\alpha}\log^{-\beta}n\quad&\text{if}\
\alpha>1/2,\\\\[2.0pt] n^{-\alpha}\log^{-\beta+1}n\quad&\text{if}\
\alpha=1/2\text{ and }\beta>1,\\\\[2.0pt] 1\quad&\text{otherwise}.\end{cases}$

Moreover, there exist classes $F$ such that these bounds are sharp.

Again, the hidden constant in (6) is given by the product of the hidden
constant in (5) and a constant that only depends on $\alpha$ and $\beta$. The
difference compared to unit balls of RKHSs is the case $\alpha=1/2$, where we
need $\beta>1$ instead of $\beta>1/2$ and lose a factor $\log n$ instead of
$\sqrt{\log n}$, see Example 29. In addition, if $(d_{k}(F))\notin\ell_{2}$,
then $g_{n}(F)$ might be bounded below by a constant, opposite to the RKHS
setting where $g_{n}(F)$ tends to zero as soon as $d_{k}(F)$ does, see [13].
However, for $\alpha>1/2$, the results for general classes are just as strong
as before.

###  1.1. Remarks and related literature

We want to add several remarks on the history of the result and related
topics.

######  Remark 5 (Equivalent widths).

There are several quantities to measure the “width” of a set $F$. Although we
work here with the Kolmogorov numbers $d_{k}(F)$ as benchmark, let us add that
these quantities coincide in $L_{2}$ with the _approximation numbers_ of $F$,
i.e.

$d_{k}(F)\,=\,a_{k}(F)\,:=\,\inf_{\begin{subarray}{c}\ell_{1},\dots,\ell_{k}\colon
F\to\mathbb{C}\text{ linear}\\\ \varphi_{1},\dots,\varphi_{k}\in
L_{2}\end{subarray}}\,\sup_{f\in
F}\,\Big{\|}f-\sum_{i=1}^{k}\ell_{i}(f)\,\varphi_{i}\Big{\|}_{L_{2}},$

as the infimum in the definition of $d_{k}(F)$ for given
$\varphi_{1},\dots,\varphi_{k}$ is attained by the $L_{2}$-orthogonal
projection onto their span, which is linear in any case. The approximation
numbers of a class represent the worst-case error of an optimal linear
algorithm that uses at most $k$ linear functionals as information. If $F$ is
the unit ball of some Hilbert space $H$, then the approximation numbers agree
with the _singular values_ of the identity $\operatorname{Id}\colon H\to
L_{2}$. In this case, the $d_{k}(F)$ also coincide with the _Gelfand
$k$-widths_ $c_{k}(F)$, which represent the minimal worst-case error of
(possibly non-linear) algorithms based on $k$ arbitrary linear functionals,
see, e.g., Chapter 4 in [41].

######  Remark 6 (Extreme classes $F$).

It is interesting to note that the lower bound (2) from [17] is attained
already for univariate Sobolev spaces of periodic functions. By Theorem 1,
this means that these basic classes already represent the most difficult RKHSs
for sampling recovery when the numbers $d_{k}(F)$ are fixed.

######  Remark 7 (Least squares methods).

The upper bounds in Theorem 1 and 3 are proven for a weighted least squares
algorithm using samples from a set of $cm$ points that is subsampled from a
set of $cm\log m$ i.i.d. random points, see Section 5. Depending on the
function class $F$, the algorithm using the full set of random points may be
constructive but the subsampling is based on an existence result from [34] and
is therefore not constructive. It would be very interesting to make the
subsampling constructive, see Remark 21.

######  Remark 8 (Spline algorithm).

Let $F$ be the unit ball of a RKHS $H$. If we fix the sampling points
$x_{1},...,x_{n}$, it is known that the smallest possible worst case error is
achieved by the spline algorithm

$S_{n}(f)\,:=\,\underset{g\in H\colon g(x_{i})=f(x_{i})}{\rm
argmin}\,\|g\|_{H},$

that is,

$\inf_{\begin{subarray}{c}\varphi_{1},\dots,\varphi_{n}\in
L_{2}\end{subarray}}\,\sup_{f\in
F}\,\Big{\|}f-\sum_{i=1}^{n}f(x_{i})\,\varphi_{i}\Big{\|}_{L_{2}}\,=\,\sup_{f\in
F}\,\Big{\|}f-S_{n}(f)\Big{\|}_{L_{2}},$

see e.g. [54, Theorem 5.1]. The function $S_{n}(f)$ is also known as the
minimal norm interpolant and, by the famous _representer theorem_ , can be
expressed as a linear combination of the kernel functions $K(x_{i},\cdot)$,
see e.g. [57, Proposition 12.32]. Therefore, our upper bounds are true not
only for the least squares algorithm, but also for the kernel-based
approximation $S_{n}(f)$. Both types of algorithms are common in the context
of learning, see e.g. the seminal paper [9].

######  Remark 9 (The power of i.i.d. sampling).

It is remarkable that, up to a logarithmic factor, the upper bound from
Theorem 1 is achieved with high probability for i.i.d. random sampling points,
see [27, 55]. In regard of the personal history of the authors DK and MU,
Theorem 1 is a byproduct of a series of work on the power of i.i.d. sampling
for approximation and integration problems that started in [14, 15] and was
also continued in [18, 23, 25, 26].

######  Remark 10 (Expected error).

A different approach to $L_{2}$-approximation is by using randomized
algorithms and taking the worst case expected error instead of a worst case
deterministic error. The results in this randomized setting are quite
different; the error of optimal algorithms does not depend on the tail of the
sequence $(d_{k}(F))$. We refer to [7, 8, 21, 33, 43, 60].

######  Remark 11 (Upper bounds for infinite trace).

We note that our bounds make sense also if $d_{k}(F)$ is infinite for small
$k$, but they are useless if the _tail_ of $(d_{k}(F))$ is not square-
summable, which is the case, e.g., if $F$ is the unit ball of a RKHS with
infinite trace, see (1).
An alternative approach is to bound the numbers $g_{n}(F)$ by the Kolmogorov
widths $d_{k}(F,L_{\infty})$ in $L_{\infty}$: it is shown in [50] that there
is a universal constant $c\in\mathbb{N}$ such that $g_{cm}(F)\leq
c\,d_{m}(F,L_{\infty})$ for probability spaces
$(D,\mathcal{A},\mathcal{\mu})$. Although this bound is sometimes weaker than
Theorem 3 (see Example 1 in [28]), it has the great advantage that it may be
applied in situations where the Kolmogorov widths in $L_{2}$ are not square-
summable, see, e.g., [52, 53]. It would be very interesting to see whether it
is possible to unify the two approaches.

######  Remark 12 (Tractability).

Assume now that a whole sequence of classes $F_{d}$ is given, where $d$ could
be the dimension of the underlying domain. For some classes we know that the
curse of dimensionality is present, if only standard information (function
values) is allowed, while the problem is tractable for general linear
information, see, e.g., [16, 44, 56]. However, since the constants from
Theorems 1 and 3 are independent of the dimension, it is possible to transfer
certain tractability properties from linear information to standard
information, see, e.g., [19, 24, 43].

######  Remark 13 (Separability of $F$).

Contrarily to the $\ell_{2}$-summability of the Kolmogorov widths, it should
be possible to remove the separability assumption on the class $F$, at least
in Theorem 1, by adding a term ${{\rm tr}_{0}(K)}/{m}$ inside the square root
in the right-hand side, as done in [37].

######  Remark 14 (Discretization of continuous frames).

A related problem is the question whether a _continuous frame_ for a Hilbert
space may be sampled to obtain a frame, see [6] for details. This problem,
which was originally posed in the physics book [1], has only recently been
solved in [12], see also the survey [5]. Although seemingly independent, this
line of research uses remarkably similar methods. We leave it to future
research to better understand and expand the connections.

###  1.2. Outline

The rest of the paper can be outlined as follows. Sections 2–5 form the proof
of Theorem 1. In Section 2, we collect some basics on the RKHS setting. In
Section 3, we obtain our initial sample of $\mathcal{O}(m\log m)$ points based
on a concentration inequality for infinite matrices. The subsampling is
performed in Section 4, which applies the solution to the Kadison-Singer
problem in a slightly original way, leading to the core of the proof in
Section 5. In Section 6, we prove our results for general function classes by
constructing a suitable RKHS, on which a local version of Theorem 1 (Theorem
23) can be applied. Finally, in Section 7, we present examples, applying our
result to tensor product problems and showing that our upper bounds are sharp.

Acknowledgement: The authors thank Albert Cohen, Daniel Freeman, Aicke
Hinrichs and Erich Novak for useful discussions and detailed corrections.
Moreover, DK and MU want to acknowledge that MD obtained Theorem 1 on his own
and presented it at the _MASCOT-NUM Workshop on “Optimal Sampling for
Approximation”_ at the IHP in Paris on March 10, 2022. The current work is the
product of subsequent collaboration.

##  2\. Hilbert space setting

We first consider the case where $F$ is the unit ball of a separable Hilbert
space $H$ with reproducing kernel $K\in\mathbb{C}^{D\times D}$. We refer to
[37] and references therein for theoretical background on RKHSs.

Thanks to the finite trace assumption (1), we know that the identity map
$\operatorname{Id}\colon H\to L_{2}$ is Hilbert-Schmidt, thus its left and
right singular vectors $(b_{k})_{k\in\mathbb{I}}$ and
$(\sigma_{k}b_{k})_{k\in\mathbb{I}}$ are orthonormal families in $L_{2}$ and
$H$, respectively. Here, we only list the singular vectors with respect to the
nonzero singular values $\sigma_{k}>0$, and the index set is of the form
$\mathbb{I}=\\{k\in\mathbb{N}_{0}\colon k<M\\}$ with
$M\in\mathbb{N}\cup\\{\infty\\}$. The singular vectors satisfy

$\langle f,b_{k}\rangle_{L_{2}}=\langle
f,\sigma_{k}^{2}b_{k}\rangle_{H}\quad\text{for all }f\in H\text{ and
}k\in\mathbb{I}.$

We use the convention that $\mathbb{N}_{0}:=\\{0,1,2,\dots\\}$ and the
singular values are arranged in a non-increasing order. In particular,
$\sum_{k\in\mathbb{I}}\sigma_{k}^{2}<\infty$ and the Kolmogorov width
$d_{m}(F)=\sigma_{m}$ is attained by the $L_{2}$-orthogonal projection $P_{m}$
onto $V_{m}=\operatorname{span}\\{b_{k}\colon k<m\\}$. Moreover, the
separability of $H$ ensures that the equality

$K(x,y)=\sum_{k\in\mathbb{I}}\sigma_{k}^{2}\,{b_{k}(x)}\overline{b_{k}(y)}$

holds for all $x,y\in D_{0}$ with some set $D_{0}\subset D$ satisfying
$\mu(D\setminus D_{0})=0$. We therefore have the identity

(7) $f(x)\,=\,\sum_{k\in\mathbb{I}}\left\langle
f,b_{k}\right\rangle_{L_{2}}b_{k}(x)\quad\text{for all }f\in H\text{ and }x\in
D_{0}.$

Our sampling points will be contained in the set $D_{0}$.

As a consequence of the following lemma, we only have to show the validity of
Theorem 1 for all $1\leq m<M$.

######  Lemma 15.

Let $M=\min\\{m\in\mathbb{N}\colon d_{m}(F)=0\\}<\infty$. Then we have
$g_{n}(F)=0$ for all $n\geq M$.

###### Proof.

For $x\in D_{0}$, we write $b(x)=(b_{0}(x),\ldots,b_{M-1}(x))$. Then there are
points $x_{0},\ldots,x_{M-1}\in D_{0}$ such that every $b(x)$ is contained in
the span of the vectors $b(x_{i})$. We write $b(x)=\sum\varphi_{i}(x)b(x_{i})$
with coefficients $\varphi_{i}(x)\in\mathbb{C}$. By (7), we have

$f(x)=\sum_{k<M}\langle
f,b_{k}\rangle_{L_{2}}\sum_{i<M}\varphi_{i}(x)b_{k}(x_{i})=\sum_{i<M}f(x_{i})\varphi_{i}(x),$

for all $x\in D_{0}$ and $f\in H$. Thus, the identity $f=\sum
f(x_{i})\varphi_{i}$ holds almost everywhere. Moreover, the functions
$b_{0},\dots,b_{M-1}$ restricted to $D_{0}$ form a basis of
$\operatorname{span}\\{\varphi_{i}\colon i<M\\}$, and thus $\varphi_{i}\in
L_{2}$. ∎

We fix an integer $1\leq m<M$ for the rest of the proof of Theorem 1.

##  3\. Concentration inequality

As proposed in [27] and applied in [19, 28, 37, 38, 55], we define the
probability density

$\rho_{m}(x)=\frac{1}{2}\left(\frac{1}{m}\sum_{k<m}|b_{k}(x)|^{2}+\frac{\sum_{k\geq
m}\sigma_{k}^{2}\,|b_{k}(x)|^{2}}{\sum_{k\geq m}\sigma_{k}^{2}}\right).$

and draw i.i.d. random points $x_{1},\dots,x_{n}\in D$ according to this
density. We define the $M$-dimensional vectors $y_{1},\dots,y_{n}$ by

$(y_{i})_{k}=\left\\{\begin{array}[]{cl}\rho_{m}(x_{i})^{-1/2}\,b_{k}(x_{i})&\text{
if }0\leq k<m,\\\
\rho_{m}(x_{i})^{-1/2}\,\gamma_{m}^{-1}\,\sigma_{k}\,b_{k}(x_{i})&\text{ if
}m\leq k<M,\end{array}\right.$

where

$\gamma_{m}\,:=\,\max\bigg{\\{}\sigma_{m},\,\sqrt{\frac{1}{m}\sum_{k\geq
m}\sigma_{k}^{2}}\,\bigg{\\}}>0.$

Note that $\rho_{m}(x_{i})>0$ almost surely. It follows from these definitions
that $y_{i}\in\ell_{2}(\mathbb{I})$ with

$\|y_{i}\|_{2}^{2}=\rho_{m}(x_{i})^{-1}\bigg{(}\sum_{k<m}|b_{k}(x_{i})|^{2}+\gamma_{m}^{-2}\sum_{k\geq
m}\sigma_{k}^{2}\,|b_{k}(x_{i})|^{2}\bigg{)}\leq 2m,$

and

$\mathbb{E}(y_{i}y_{i}^{*})=\operatorname{diag}(1,\dots,1,\sigma_{m}^{2}/\gamma_{m}^{2},\sigma_{m+1}^{2}/\gamma_{m}^{2},\dots)=:E,$

with $\|E\|_{2\to 2}=1$ since $\sigma_{k}^{2}/\gamma_{m}^{2}\leq 1$ for $k\geq
m$. Here, $\operatorname{diag}(v)$ denotes a diagonal matrix with diagonal
$v$, and $\|\cdot\|_{2\to 2}$ denotes the spectral norm of a matrix.

We apply the following concentration inequality for infinite matrices, which
was proved by Mendelson and Pajor in [35, Theorem 2.1]. We use a version of
this result from [37, Theorem 1.1] and [38, Theorem 5.3].

######  Lemma 16.

Let $n\geq 3$ and $y_{1},\dots,y_{n}$ be i.i.d. random sequences from
$\ell_{2}(\mathbb{I})$ satisfying $\|y_{i}\|_{2}^{2}\leq 2m$ almost surely and
$\|E\|_{2\to 2}\leq 1$, with $E=\mathbb{E}(y_{i}y_{i}^{*})$. Then, for $0\leq
t\leq 1$,

$\mathbb{P}\left(\Big{\|}\frac{1}{n}\sum_{i=1}^{n}y_{i}y_{i}^{*}-E\Big{\|}_{2\to
2}>t\right)\,\leq\,2^{3/4}\,n\,\exp\left(-\frac{nt^{2}}{42\,m}\right).$

For $t=1/2$, this probability is less than $1/2$ as soon as
$\frac{n}{\log(4n)}\geq 168\,m$. In the sequel we take

$n=\lfloor C_{0}m\log(m+1)\rfloor,$

with $C_{0}$ large enough, so that the previous inequality holds true. (One
can take $C_{0}=10^{4}$, for instance.) Thanks to Lemma 16, we know that there
exists a realization $x_{1},\dots,x_{n}\in D_{0}$ of the random sampling such
that the corresponding family $y_{1},\dots,y_{n}$ satisfies

(8) $\Big{\|}\frac{1}{n}\sum_{i=1}^{n}y_{i}y_{i}^{*}-E\Big{\|}_{2\to
2}\leq\frac{1}{2}.$

We fix such a sequence for the rest of the proof of Theorem 1.

##  4\. Subsampling of infinite vectors

We now want to apply the solution to the Kadison-Singer problem, or
specifically to Weaver’s conjecture, to the sum of rank-one matrices

$\frac{1}{n}\sum_{i=1}^{n}y_{i}y_{i}^{*},$

in order to find a subsampling of order $m$ preserving the spectral properties
of the sum. The original result comes from the celebrated paper [34] by
Marcus, Spielman and Srivastava, and has already been applied numerous times
in approximation theory, see for instance [7, 21, 27, 28, 37, 38, 40, 50].
However, the original subsampling strategy only works for finite matrices. The
main result of this section is the following infinite-dimensional variant,
that might be of independent interest.

######  Proposition 17.

There are absolute constants $c_{1}\leq 43200$, $c_{2}\geq 50$, $c_{3}\leq
21600$, with the following properties. Let $n,m\in\mathbb{N}$ and
$y_{1},\dots,y_{n}$ be vectors from $\ell_{2}(\mathbb{N}_{0})$ satisfying
$\|y_{i}\|_{2}^{2}\leq 2m$ and

(9) $\left\|\frac{1}{n}\sum_{i=1}^{n}y_{i}y_{i}^{*}-\begin{pmatrix}I_{m}&0\\\
0&\Lambda\end{pmatrix}\right\|_{2\to 2}\leq\frac{1}{2},$

for some Hermitian matrix $\Lambda$ with $\|\Lambda\|_{2\to 2}\leq 1$, where
$I_{m}\in\mathbb{C}^{m\times m}$ denotes the identity.
Then, there is a subset $J\subset\\{1,\dots,n\\}$ with $|J|\leq c_{1}m$, such
that

$\bigg{(}\frac{1}{m}\sum_{i\in
J}y_{i}y_{i}^{*}\bigg{)}_{<m}\,\geq\,c_{2}\,I_{m}\qquad\text{and}\qquad\frac{1}{m}\sum_{i\in
J}y_{i}y_{i}^{*}\,\leq\,c_{3}\,I,$

where $A_{<m}:=(A_{k,l})_{k,l<m}$ and $A\leq B$ denotes the Loewner order of
Hermitian matrices $A$ and $B$.

The conclusion can be understood as an upper bound on the largest eigenvalue
of $A=\sum_{i\in J}y_{i}y_{i}^{*}$ and a lower bound on the smallest
eigenvalue of $A_{<m}$. Note that the constants in Proposition 17, and hence
also the final sampling size, are independent of $n$, the original sampling
size. The rest of this section is devoted to the proof of this proposition.

###  4.1. Reduction to finite dimension

Let $U_{0}$ be a matrix whose columns form an orthonormal basis of

${\rm span}\left\\{(y_{i})_{\geq m}\colon
i=1,\ldots,n\right\\}\subset\ell_{2},$

where $(y_{i})_{\geq m}=((y_{i})_{k})_{k\geq m}$. Clearly, $U_{0}$ has at most
$n$ columns. Then we have that $U_{0}^{*}U_{0}$ is the identity matrix and in
particular the spectral norm of $U_{0}$ and $U_{0}^{*}$ equals one. We set

$U=\begin{pmatrix}I_{m}&0\\\ 0&U_{0}\end{pmatrix},$

which is a matrix that satisfies $U^{*}U=I_{p}$, where $p\leq m+n$, and
therefore also $U$ and $U^{*}$ have unit norm. We choose vectors
$z_{i}\in\mathbb{C}^{p}$ that satisfy $Uz_{i}=y_{i}$ for all $i\leq n$. Such
vectors exist since $y_{i}$ is contained in the span of the columns of $U$.
Then we also have $z_{i}=U^{*}Uz_{i}=U^{*}y_{i}$.

Let $E=\begin{pmatrix}I_{m}&0\\\ 0&\Lambda\end{pmatrix}$ be the matrix from
Proposition 17. We define

$\hat{E}=U^{*}\,E\,U=\begin{pmatrix}I_{m}&0\\\
0&E^{\prime}\end{pmatrix}\quad\text{ where }\quad\|E^{\prime}\|_{2\to
2}\leq\|E\|_{2\to 2}\leq 1.$

With the norm bounds on $U$ and $U^{*}$, equation (9) gives

$\Big{\|}\frac{1}{n}\sum_{i=1}^{n}z_{i}z_{i}^{*}-\hat{E}\Big{\|}_{2\to
2}=\Big{\|}U^{*}\left(\frac{1}{n}\sum_{i=1}^{n}y_{i}y_{i}^{*}-E\right)U\Big{\|}_{2\to
2}\leq\frac{1}{2}.$

###  4.2. Approximating the identity

In addition to finite dimension, the result from [34] requires the matrix
$\frac{1}{n}\sum_{i=1}^{n}z_{i}z_{i}^{*}$ to be close to the identity in
spectral norm, and this is not ensured here. To mitigate this defect, we
artificially add rank-one matrices $z_{i}z_{i}^{*}\in\mathbb{C}^{p\times p}$
for $i=n+1,\dots,q$ in the following way.

As $I_{p}-\hat{E}$ is positive semi-definite, we can decompose it as a sum of
rank-one matrices

$I_{p}-\hat{E}=\begin{pmatrix}0&0\\\
0&I_{p-m}-E^{\prime}\end{pmatrix}=\sum_{j=1}^{p-m}t_{j}t_{j}^{*},$

where $t_{j}\in\mathbb{C}^{p}$. We now choose

$z_{i}=\sqrt{\frac{n}{n_{j(i)}}}\,t_{j(i)},\quad
n_{j}=\left\lceil\frac{n}{2m}\,\|t_{j}\|_{2}^{2}\right\rceil,$

with $j(i)\in\\{1,\dots,p-m\\}$ such that $\\{z_{i},\,i=n+1,\dots,q\\}$
contains exactly $n_{j}$ copies of each $\sqrt{n/n_{j}}\,t_{j}$. In this way,
for $i>n$, the first $m$ entries of $z_{i}$ are zero since this is true for
the $t_{j}$,

$\|z_{i}\|_{2}^{2}\leq\frac{n}{n_{j(i)}}\,\|t_{j(i)}\|_{2}^{2}\leq 2m,$

and

$\begin{split}\Big{\|}\frac{1}{n}\sum_{i=1}^{q}z_{i}z_{i}^{*}-I_{p}\Big{\|}_{2\to
2}&=\Big{\|}\frac{1}{n}\sum_{i=1}^{n}z_{i}z_{i}^{*}+\sum_{j=1}^{p-m}t_{j}t_{j}^{*}-I_{p}\Big{\|}_{2\to
2}\\\ &=\Big{\|}\frac{1}{n}\sum_{i=1}^{n}z_{i}z_{i}^{*}-\hat{E}\Big{\|}_{2\to
2}\leq\frac{1}{2}.\end{split}$

######  Remark 18.

As $\|t_{j}\|_{2}^{2}\leq\|I_{p}-\hat{E}\|_{2\to 2}\leq 1$, we count

$q=n+\sum_{j=1}^{p-m}n_{j}\leq
n+\sum_{j=1}^{p-m}\left(1+\frac{n}{2m}\right)\leq
n+(p-m)\frac{n}{m}=\frac{np}{m}.$

Conversely, taking traces in $\mathbb{C}^{p\times p}$, we find

$\frac{p}{2}=\operatorname{Tr}\left(\frac{1}{2}I_{p}\right)\leq\operatorname{Tr}\left(\frac{1}{n}\sum_{i=1}^{q}z_{i}z_{i}^{*}\right)=\frac{1}{n}\sum_{i=1}^{q}\|z_{i}\|_{2}^{2}\leq\frac{2mq}{n}.$

So, we obtain $n/m\geq q/p\geq n/4m$. Recall that, given $m$ the dimension of
the approximation space $V_{m}$, we took $n=\mathcal{O}(m\log m)$ initial
sample points, and vectors $z_{i}$ of size $p=\mathcal{O}(m\log m)$. Hence,
the number of such vectors is $q=\mathcal{O}(m\log^{2}m)$. Surprisingly, we do
not use estimates on $p$ and $q$ in the rest of the argument.

######  Remark 19.

In fact, we did not need an exponential speed of convergence in the
concentration inequality. The reduction of the sample size to $\mathcal{O}(m)$
points works for any initial set of sampling points satisfying (8). If the
cardinality of the initial sample is $n=m\,\ell(m)$, where $\ell(m)$ is any
positive function of $m$, we get $p=\mathcal{O}(m\,\ell(m))$ and
$q=\mathcal{O}(m\,\ell(m)^{2})$.

###  4.3. Reduction of the sample size

We can now use the Kadison-Singer solution from [34] in an iterated way, as
proposed in Lemma 3 of [40], and later used in [7, 27, 28, 32, 37, 38, 50].
The following lemma is obtained from Corollary B and Lemma 1 in [40].

######  Lemma 20.

Let $z_{1},\dots,z_{q}\in\mathbb{C}^{p}$ with $\|z_{i}\|_{2}^{2}\leq\delta$
and

$\alpha I_{p}\leq\sum_{i=1}^{q}z_{i}z_{i}^{*}\leq\beta I_{p}$

for some $\beta\geq\alpha>100\,\delta>0$. Then there is a partition of
$\\{1,\ldots,q\\}$ into sets $J_{1},\ldots,J_{t}$ such that, for all $s\leq
t$, we have

$25\,\delta I_{p}\,\leq\,\sum_{i\in
J_{s}}z_{i}z_{i}^{*}\,\leq\,3600\,\frac{\beta}{\alpha}\,\delta I_{p}.$

###### Proof.

Since the matrix $M=\sum_{i=1}^{q}z_{i}z_{i}^{*}$ is positive, we may define
$\tilde{z}_{i}=M^{-1/2}z_{i}$. Then we have
$\sum_{i=1}^{q}\tilde{z}_{i}\tilde{z}_{i}^{*}=I_{p}$ and
$\|\tilde{z}_{i}\|_{2}^{2}\leq\delta/\alpha=:\delta^{\prime}<1/100$. By
Corollary B and Lemma 1 in [40], noting that the constant $C$ from Lemma 1 is
at most 36, we get a partition of $\\{1,\ldots,q\\}$ into sets
$J_{1},\ldots,J_{t}$ such that, for all $s\leq t$, we have

$25\,\delta^{\prime}\,I_{p}\,\leq\,\sum_{i\in
J_{s}}\tilde{z}_{i}\tilde{z}_{i}^{*}\,\leq\,3600\,\delta^{\prime}\,I_{p}.$

Now, using

$\sum_{i\in J_{s}}z_{i}z_{i}^{*}=M^{1/2}\,\sum_{i\in
J_{s}}\tilde{z}_{i}\tilde{z}_{i}^{*}\,M^{1/2},$

we get the statement. ∎

Note that one could obtain better constants by adapting the proof of Theorem
2.3 from [38]. In our case, we have $\delta=2m$, $\alpha=n/2$ and
$\beta=3n/2$. The relation $\alpha>100\,\delta$ is satisfied. We thus obtain

$50\,mI_{p}\,\leq\,\sum_{i\in J_{s}}z_{i}z_{i}^{*}\,\leq\,21600\,mI_{p}.$

for every $J_{s}$ from the partition. Moreover, the inequality

$\frac{n}{2}I_{p}\,\leq\,\sum_{i=1}^{q}z_{i}z_{i}^{*}\,=\,\sum_{s=1}^{t}\sum_{i\in
J_{s}}z_{i}z_{i}^{*}\,\leq\,21600\,tmI_{p}$

implies that one of the sets $J^{\prime}=J_{s}$ from the partition must
satisfy

$|J^{\prime}\cap\\{1,\dots,n\\}|\,\leq\,\frac{n}{t}\,\leq\,43200\,m.$

After applying Lemma 20 and removing the indices from
$J^{\prime}\cap\\{n+1,\dots,q\\}$ corresponding to artificially added vectors,
we are left with a set $J:=J^{\prime}\cap\\{1,\dots,n\\}$ of cardinality

$|J|\,\leq\,43200\,m.$

It remains to show that the artificial vectors do not interfere with our
desired properties. For this, recall that $(z_{i})_{k}=(y_{i})_{k}$ for $k<m$
and $i\leq n$, whereas the first $m$ entries of $z_{i}\in\mathbb{C}^{p}$ are
zero for $i>n$. Hence,

$\left(\sum_{i\in J}y_{i}y_{i}^{*}\right)_{<m}=\left(\sum_{i\in
J^{\prime}}z_{i}z_{i}^{*}\right)_{<m}\,\geq\,50\,m\,I_{m},$

where we use a simple linear algebra fact on self-adjoint matrices $A$:

$\lambda_{\min}(A_{<m})=\inf_{\begin{subarray}{c}z\in\mathbb{C}^{p},\,\|z\|_{2}=1\\\
z_{k}=0\text{ for }k\geq
m\end{subarray}}z^{*}Az\geq\inf_{z\in\mathbb{C}^{p},\,\|z\|_{2}=1}z^{*}Az=\lambda_{\min}(A).$

Similarly, and using positive definiteness, we have

$\sum_{i\in J}z_{i}z_{i}^{*}\leq\sum_{i\in J^{\prime}}z_{i}z_{i}^{*}\leq
21600\,m\,I_{p}.$

With the orthogonal transformation $U$ from Section 4.1, we get

$\Big{\|}\sum_{i\in J}y_{i}y_{i}^{*}\Big{\|}_{2\to
2}=\Big{\|}U\left(\sum_{i\in J}z_{i}z_{i}^{*}\right)U^{*}\Big{\|}_{2\to
2}\leq\Big{\|}\sum_{i\in J}z_{i}z_{i}^{*}\Big{\|}_{2\to 2}\leq 21600\,m.$

This proves Proposition 17.
∎

######  Remark 21.

It would be an interesting improvement to use the result of Batson, Spielman
and Srivastava, see [3], instead of [34] for the subsampling. This earlier
paper is applied to approximation theory in e.g. [32, 39, 51] and more
recently in [4]. It presents a slightly less powerful method, requiring
additional weights, but comes with an almost linear algorithmic complexity,
see [31], and much smaller constants, which could make the bound presented
here sharp also in terms of numerical values.

######  Remark 22.

We recently learned that it might be possible to use results from [12], which
work directly in an infinite-dimensional setting, to save the reduction to a
finite dimension in Section 4.1. However, as the core of our method is [34],
we decided to keep our more direct deduction.

##  5\. Proof of the main theorem

We now have all the tools for proving Theorem 1.

To obtain our sampling points, we combine (8) for our initial vectors
$y_{i}\in\ell_{2}(\mathbb{I})$ with Proposition 17. Clearly, Proposition 17
stays true if we replace $\mathbb{N}_{0}$ by the possibly finite index set
$\mathbb{I}$. We obtain points $x_{1},\dots,x_{n}\in D_{0}$ with $n\leq
43200\,m$ such that the vectors

$(y_{i})_{k}=\left\\{\begin{array}[]{cl}\rho_{m}(x_{i})^{-1/2}\,b_{k}(x_{i})&\text{
if }0\leq k<m,\\\
\rho_{m}(x_{i})^{-1/2}\,\gamma_{m}^{-1}\,\sigma_{k}\,b_{k}(x_{i})&\text{ if
}m\leq k<M,\end{array}\right.$

satisfy

$\left(\sum_{i=1}^{n}y_{i}y_{i}^{*}\right)_{<m}\,\geq\,50\,m\,I,$

and

$\left(\sum_{i=1}^{n}y_{i}y_{i}^{*}\right)_{\geq m}\,\leq\,21600\,m\,I,$

where we use the notation $A_{\geq m}=(A_{k,l})_{k,l\geq m}$ for a matrix $A$.

As in earlier papers, we use the _weighted least squares estimator_

$A_{n}(f)\,:=\,\underset{g\in V_{m}}{\rm
argmin}\,\sum_{i=1}^{n}\frac{|g(x_{i})-f(x_{i})|^{2}}{\rho_{m}(x_{i})}$

with $V_{m}$ and $\rho_{m}$ as defined in Sections 2 and 3, respectively, see
[27]. This algorithm may be written as

$A_{n}(f)\,=\,\sum_{k=1}^{m}(G^{+}Nf)_{k}\,b_{k}$

where $N\colon F\to\mathbb{C}^{n}$ with
$N(f):=\left(\rho_{m}(x_{i})^{-1/2}f(x_{i})\right)_{i\leq n}$ is the
_information mapping_ and $G^{+}\in\mathbb{C}^{m\times n}$ is the Moore-
Penrose inverse of the matrix

$G:=\left(\rho_{m}(x_{i})^{-1/2}\,b_{k}(x_{i})\right)_{i\leq n,\,k\leq
m}\in\mathbb{C}^{n\times m}.$

Since we have the identity
$\overline{G^{*}G}=(\sum_{i=1}^{n}y_{i}y_{i}^{*})_{<m}$, the matrix $G$ has
full rank and the spectral norm of $G^{+}$ is bounded by $(50m)^{-1/2}$. In
particular, the argmin in the definition of $A_{n}$ is uniquely defined and
$A_{n}$ satisfies $A_{n}(f)=f$ for all $f\in V_{m}$.
Denoting with $Q_{m}$ the $L_{2}$-orthogonal projection onto ${\rm
span}\\{b_{k}\colon k\geq m\\}$, we obtain for any $f\in H$ that

$\displaystyle\allowdisplaybreaks\left\|f-A_{n}(f)\right\|_{L_{2}}^{2}\,$
$\displaystyle=\,\left\|f-P_{m}f\right\|_{L_{2}}^{2}+\left\|P_{m}f-A_{n}(f)\right\|_{L_{2}}^{2}$
$\displaystyle=\,\left\|Q_{m}f\right\|_{L_{2}}^{2}+\left\|A_{n}(f-P_{m}f)\right\|_{L_{2}}^{2}$
$\displaystyle=\,\left\|Q_{m}f\right\|_{L_{2}}^{2}+\left\|G^{+}N(f-P_{m}f)\right\|_{\ell_{2}^{n}}^{2}$
$\displaystyle\leq\,\sigma_{m}^{2}\,\left\|Q_{m}f\right\|_{H}^{2}+\left\|G^{+}\right\|_{2\to
2}^{2}\cdot\left\|N(f-P_{m}f)\right\|_{\ell_{2}^{m}}^{2}.$

By (7) we have $N(f-P_{m}f)=\Phi\xi_{f}$, where

$\Phi=\left(\rho_{m}(x_{i})^{-1/2}\sigma_{k}\,b_{k}(x_{i})\right)_{i\leq
n,\,k\geq m}\quad\text{and}\quad\xi_{f}=(\langle
f,\sigma_{k}\,b_{k}\rangle_{H})_{k\geq m}.$

The matrix $\Phi$ satisfies

$\overline{{\Phi^{*}\Phi}}\,=\,\gamma_{m}^{2}\left(\sum_{i=1}^{n}y_{i}y_{i}^{*}\right)_{\geq
m}$

and therefore its spectral norm is bounded by
$\left(21600\,m\,\gamma_{m}^{2}\right)^{1/2}$. Thus,

$\left\|N(f-P_{m}f)\right\|_{\ell_{2}^{m}}^{2}\,\leq\,21600\,m\,\gamma_{m}^{2}\|\xi_{f}\|_{2}^{2}\,=\,21600\,m\,\gamma_{m}^{2}\,\|Q_{m}f\|_{H}^{2}.$

In summary, we obtain for all $1\leq m<M$ the bound

(10)
$\left\|f-A_{n}(f)\right\|_{L_{2}}^{2}\,\leq\,433\,\max\bigg{\\{}\sigma_{m}^{2},\,\frac{1}{m}\sum_{k\geq
m}\sigma_{k}^{2}\,\bigg{\\}}\,\left\|Q_{m}f\right\|_{H}^{2}.$

for all $f\in H$ and some $n\leq 43200\,m$. Taking the supremum over $f\in F$
and using that

$\max\bigg{\\{}\sigma_{m}^{2},\,\frac{1}{m}\sum_{k\geq
m}\sigma_{k}^{2}\,\bigg{\\}}\,\leq\,\frac{2}{m}\sum_{k\geq\lceil
m/2\rceil}\sigma_{k}^{2},$

we obtain

$g_{43200\,m}(F)^{2}\,\leq\,\frac{866}{m}\sum_{k\geq\lceil
m/2\rceil}\sigma_{k}^{2}.$

This finishes the proof of Theorem 1 with $c=43200\cdot 866$.
∎

In fact, equation (10) provides a local upper bound which is sometimes
superior to Theorem 1. We therefore state it separately.

######  Theorem 23.

Let $\mu$ be a measure on a set $D$ and let $F\subset L_{2}(\mu)$ be the unit
ball of a separable RKHS $H$ such that the finite trace assumption (1) holds.
For $m\in\mathbb{N}$, let $P_{m}$ be the orthogonal projection onto the span
$V_{m}$ of the singular vectors corresponding to the $m$ largest singular
values of the embedding of $H$ into $L_{2}$. Then there exist
$x_{1},\ldots,x_{n}\in D$ and $\varphi_{1},\ldots,\varphi_{n}\in V_{m}$, where
$n\leq 43200m$, such that, for all $f\in H$,

$\Big{\|}f-\sum_{i=1}^{n}f(x_{i})\,\varphi_{i}\Big{\|}_{L_{2}}^{2}\leq
433\max\bigg{\\{}d_{m}(F)^{2},\,\frac{1}{m}\sum_{k\geq
m}d_{k}(F)^{2}\bigg{\\}}\big{\|}f-P_{m}f\big{\|}_{H}^{2}.$

######  Remark 24.

For the purpose of Theorem 1 it was enough to bound
$\left\|f-P_{m}f\right\|_{H}\leq\left\|f\right\|_{H}$. However, Theorem 23
will be of advantage later for the study of general classes since it is able
to see additional decay of the Fourier coefficients $\langle
f,b_{k}\rangle_{L_{2}}$ compared to the decay implied by $f\in H$. Note that
faster decay of the Fourier coefficients often corresponds to higher
smoothness of the function. In a certain sense, this means that the algorithm
is universal. The error has the optimal rate of decay for any smoothness
higher than the smoothness of $H$.

######  Remark 25.

The condition on the point sets can also be given by finite matrices that are
related to the kernel $K$ of the Hilbert space. For this, let us define
$K_{m}(x,y):=\sum_{k<m}b_{k}(x)b_{k}(y)$, and $R_{m}(x,y):=\sum_{k\geq
m}\sigma_{k}^{2}\,b_{k}(x)b_{k}(y)$. The non-zero singular values of $GG^{*}$
are the same as those of $G^{*}G$, and the non-zero singular values of
$\Phi\Phi^{*}$ are the same as those of $\Phi^{*}\Phi$, where $G$ and $\Phi$
are from above. Hence, the algorithm $A_{n}$ based on points
$x_{1},\dots,x_{n}$ satisfies the error bound above (up to a constant) if

$c\,m\,\leq\,\lambda_{m}\left(GG^{*}\right)\,=\,\lambda_{m}\left(\left(\frac{K_{m}(x_{i},x_{j})}{\sqrt{\rho_{m}(x_{i})\rho_{m}(x_{j})}}\right)_{i,j=1}^{n}\right)$

and

$\left(\frac{R_{m}(x_{i},x_{j})}{\sqrt{\rho_{m}(x_{i})\rho_{m}(x_{j})}}\right)_{i,j=1}^{n}\,=\,\Phi\Phi^{*}\,\leq\,C\,m\,\gamma_{m}^{2}\,I$

for some constants $c,C>0$, where $\lambda_{m}$ denotes the $m$th eigenvalue.
It would be interesting to find a property that only involves the kernel $K$
directly (instead of the truncated kernels above), or to verify that a similar
property characterizes _good_ point sets, in a way similar to Proposition 1 of
[16] for integration.

###  5.1. Proof of Corollary 2

For the given bounds on the sampling numbers for sequences of polynomial
decay, we only need to note that

$\frac{1}{n}\sum_{k\geq
n}k^{-a}\log^{-b}k\,\lesssim\,\begin{cases}n^{-a}\log^{-b}n\quad&\text{if}\
a>1,\,b\in\mathbb{R},\\\\[2.0pt] n^{-a}\log^{-b+1}n\quad&\text{if}\
a=1,\,b>1.\end{cases}$

Hence, Corollary 2 immediately follows from Theorem 1, and the existence of
$F$ where the bounds are attained comes from (2), see [17].
∎

##  6\. General function classes

We now prove all results related to general function classes.

###  6.1. Proof of Theorem 3

We will make use of the following observation from [28, Lemma 3]. We copy its
proof for completeness.

######  Lemma 26.

Let $F\subset L_{2}$ and let $L_{2}$ be infinite-dimensional. There is an
orthonormal system $(b_{k})_{k\in\mathbb{N}_{0}}$ in $L_{2}$ such that for all
$m\geq 1$, the orthogonal projection $P_{m}$ onto
$V_{m}=\operatorname{span}\\{b_{k}\colon k<m\\}$ satisfies

(11) $\sup_{f\in F}\|f-P_{m}f\|_{L_{2}}\,\leq\,2\,d_{\lfloor m/4\rfloor}(F).$

###### Proof.

Clearly it is enough to find an increasing sequence of subspaces of $L_{2}$,

$U_{1}\subseteq U_{2}\subseteq U_{3}\subseteq\ldots,\qquad\dim(U_{m})\leq m,$

such that the projection $P_{m}$ onto $U_{m}$ satisfies (11). By the
definition of $d_{k}(F)$, $k\in\mathbb{N}_{0}$, there is a subspace
$W_{k}\subset L_{2}$ of dimension $k$ and a mapping $T_{k}\colon F\to W_{k}$
such that

$\sup_{f\in F}\|f-T_{k}f\|_{L_{2}}\,\leq\,2\,d_{k}(F).$

This is also true if $d_{k}(F)=0$. We let $U_{m}$ be the space that is spanned
by the union of the spaces $W_{2^{\ell}}$ over all $\ell\in\mathbb{N}_{0}$
such that $2^{\ell}\leq m/2$. Note that $U_{m}$ contains a subspace $W_{k}$
with $k\geq\lfloor m/4\rfloor$. Therefore, $P_{m}f$ is at least as close to
$f$ as $T_{k}f$ for some $k\geq\lfloor m/4\rfloor$, which implies (11). ∎

We now turn to the proof of Theorem 3. The basic idea is to construct a
suitable reproducing kernel Hilbert space $H$ that contains a dense subset of
$F$ and apply Theorem 23 to this Hilbert space. It will be important to use
the local bound from Theorem 23 instead of the global bound from Theorem 1.

###### Proof of Theorem 3.

Without loss of generality, we assume that $L_{2}$ is infinite-dimensional.
Moreover, we assume that $d_{k}(F)$ is finite for $k\geq k_{0}$ and that
$(d_{k}(F))_{k\geq k_{0}}\in\ell_{p}$. Otherwise, the statement is trivial.

By Lemma 26, there is an orthonormal system $(b_{k})_{k\in\mathbb{N}_{0}}$
such that (11) is satisfied for all $m\in\mathbb{N}$. We will consider $b_{k}$
as a function, where we fix an arbitrary representer from the equivalence
class in $L_{2}$. We call

$\hat{f}(k):=\left\langle f,b_{k}\right\rangle_{L_{2}}$

the $k$th Fourier coefficient of $f$. Moreover, we fix a countable dense
subset $F_{0}$ of $F$ and set $\sigma_{k}=\max\\{1,k\\}^{-\alpha}$ for all
$k\in\mathbb{N}_{0}$ and some $\alpha\in(1/2,1/p)$. Then we have
$(\sigma_{k})\in\ell_{2}$.

We now want to define a RKHS on a set $D_{0}\subset D$, with $\mu(D\setminus
D_{0})=0$, which admits the orthonormal basis $(\sigma_{k}b_{k})$ and contains
the set $F_{0}$. Such a Hilbert space will have the reproducing kernel

$K(x,y)\,=\,\sum_{k\in\mathbb{N}_{0}}\sigma_{k}^{2}b_{k}(x)\overline{b_{k}(y)}.$

To find a suitable set $D_{0}$, we first note that

(12)
$\int_{D}K(x,x)\,d\mu(x)\,=\,\sum_{k\in\mathbb{N}_{0}}\sigma_{k}^{2}<\infty$

and thus $K(x,x)$ is finite for all $x\in D\setminus E$ with a null set
$E\subset D$. Moreover, for all $f\in F_{0}$, we have

$\sum_{k\geq 1}k\,|\hat{f}(k)|^{2}\,=\,\sum_{n\geq
0}\sum_{k>n}|\hat{f}(k)|^{2}\,=\,\sum_{n\geq
0}\|f-P_{n}f\|_{L_{2}}^{2}<\infty,$

where we use (11) and the assumptions on $F$. The Rademacher-Menchov Theorem,
see e.g. [45], now implies that the Fourier series of $f$ at $x$ converges to
$f(x)$ for all $x\in D\setminus E_{f}$ with a null set $E_{f}\subset D$. We
put $D_{0}:=D\setminus E_{0}$, where $E_{0}:=E\cup\bigcup_{f\in F_{0}}E_{f}$
is a null set. Then for all $x\in D_{0}$ and $f\in F_{0}$, we have

$K(x,x)\,<\infty\quad\text{and}\quad
f(x)\,=\,\sum_{k\in\mathbb{N}_{0}}\hat{f}(k)\,b_{k}(x).$

We now define the space $H$ as the set of all square-integrable functions
$f\colon D_{0}\to\mathbb{C}$ which are point-wise represented by their Fourier
series $\sum_{k}\hat{f}(k)\,b_{k}$ and which satisfy

$\|f\|_{H}^{2}\,:=\,\sum_{k\in\mathbb{N}_{0}}\frac{|\hat{f}(k)|^{2}}{\sigma_{k}^{2}}<\infty.$

Then $H$ is a separable reproducing kernel Hilbert space on $D_{0}$ since

$|f(x)|^{2}\leq K(x,x)\|f\|_{H}^{2}\quad\text{ for all }x\in D_{0}\text{ and
}f\in H,$

and $(\sigma_{k}b_{k})_{k\in\mathbb{N}_{0}}$ is an orthonormal basis of $H$.
The reproducing kernel is $K$, which has finite trace from (12).

We now show that $F_{0}$ (with functions restricted to $D_{0}$) is a subset of
$H$. Recall that any $f\in F_{0}$ is point-wise represented by its Fourier
series. Moreover, note that the Kolmogorov widths of $F_{0}$ and $F$ are the
same. We use

$d_{2m}(F)=\big{(}d_{2m}(F)^{p}\big{)}^{1/p}\leq\bigg{(}\frac{1}{m}\sum_{k\geq
m}d_{k}(F)^{p}\bigg{)}^{1/p}$

and obtain for any $m\in 8\mathbb{N}$ and $f\in F_{0}$ that

$\begin{split}\|f-P_{m}f\|_{H}^{2}&=\sum_{k\geq
m}k^{2\alpha}\,|\hat{f}(k)|^{2}\leq\sum_{\ell\in\mathbb{N}_{0}}\left(m2^{\ell+1}\right)^{2\alpha}\sum_{k=m2^{\ell}}^{m2^{\ell+1}-1}|\hat{f}(k)|^{2}\\\
&\leq
4\sum_{\ell\in\mathbb{N}_{0}}\left(m2^{\ell+1}\right)^{2\alpha}d_{m2^{\ell-2}}(F)^{2}\\\
&\leq
4\sum_{\ell\in\mathbb{N}_{0}}\left(m2^{\ell+1}\right)^{2\alpha}\bigg{(}\frac{1}{m2^{\ell-3}}\sum_{k\geq
m2^{\ell-3}}d_{k}(F)^{p}\bigg{)}^{2/p}\\\
&\leq\,2^{2+2\alpha+6/p}m^{2\alpha-2/p}\sum_{\ell\in\mathbb{N}_{0}}2^{(2\alpha-2/p)\ell}\bigg{(}\sum_{k\geq
m/8}d_{k}(F)^{p}\bigg{)}^{2/p}.\end{split}$

The last expression is finite for $m\geq 8k_{0}$, since $2\alpha-2/p<0$. This
implies that $f\in H$ and

(13) $\|f-P_{m}f\|_{H}\,\leq\,C\,m^{\alpha}\bigg{(}\frac{1}{m}\sum_{k\geq
m/8}d_{k}(F)^{p}\bigg{)}^{1/p},$

where $C>0$ only depends on $p\in(0,2)$ and
$\alpha\in(\frac{1}{2},\frac{1}{p})$.

We now apply Theorem 23 to the newly constructed Hilbert space $H$ to find
$n\leq 43200\,m$ and a linear algorithm $A_{n}$ of the form

$A_{n}(f)\,=\,\sum_{i=1}^{n}f(x_{i})g_{i},\quad x_{i}\in D_{0},\ g_{i}\in
L_{2},$

such that

(14)
$\|f-A_{n}f\|_{L_{2}(D_{0},\mu)}^{2}\,\leq\,433\,\max\bigg{\\{}\sigma_{m}^{2},\,\frac{1}{m}\sum_{k\geq
m}\sigma_{k}^{2}\,\bigg{\\}}\,\|f-P_{m}f\|_{H}^{2}$

for all $f\in H$ and thus, for all $f\in F_{0}$. Clearly, in the last
inequality, $D_{0}$ can be replaced with $D$. If we now insert the estimate
(13) and the estimate

(15) $\max\bigg{\\{}\sigma_{m}^{2},\,\frac{1}{m}\sum_{k\geq
m}\sigma_{k}^{2}\,\bigg{\\}}\,\lesssim\,m^{-2\alpha},$

into (14), we obtain that

$\|f-A_{n}f\|_{L_{2}}^{2}\,\leq\,\bigg{(}\frac{\tilde{c}_{p}}{m}\sum_{k\geq
m/8}d_{k}(F)^{p}\bigg{)}^{2/p}$

for all $f\in F_{0}$ and some $\tilde{c}_{p}>0$ that only depends on $p$.
Since $F_{0}$ is dense in $F$ and both ${\rm id}\colon F\to L_{2}$ and
$A_{n}\colon F\to L_{2}$ are continuous, the last bound is true for all $f\in
F$. This finishes the proof of Theorem 3 with
$c_{p}=43200\,\max(\tilde{c}_{p},8)$.
∎

###  6.2. The boundary case

We provide a variant of Theorem 3 under a weaker condition than
$(d_{k}(F))\in\ell_{p}$ for $p<2$. In fact, we show that the condition
$\big{(}(\log k)^{s}d_{k}(F)\big{)}\in\ell_{2}$ for some $s>1/2$ is enough for
a comparison of the sampling and the Kolmogorov widths, while the same
assumption for $s=1/2$ is not enough, see Example 30.

######  Theorem 27.

Let $s>1/2$. There is a universal constant $c\in\mathbb{N}$ and a constant
$c_{s}>0$, depending only on $s$, such that for every $F$ and $\mu$ that
satisfy Assumption A and all $m\geq 2$,

$g_{cm}(F)^{2}\,\leq\,c_{s}\,m^{-1}\log^{-2s+1}m\sum_{k\geq
m}d_{k}(F)^{2}\cdot\log^{2s}k.$

###### Proof.

The proof follows the same lines as the proof of Theorem 3. The only
difference is that we now choose $\sigma_{k}=k^{-1/2}\log^{-s}k$ for $k\geq
2$. Then, inequality (13) becomes

$\begin{split}\|f-P_{m}f\|_{H}^{2}&=\sum_{k\geq
m}|\hat{f}(k)|^{2}k\log^{2s}(k)\leq\sum_{k\geq m}|\hat{f}(k)|^{2}\sum_{m\leq
r\leq 2k}\log^{2s}(r)\\\ &\leq\sum_{r\geq m}\log^{2s}(r)\sum_{k\geq
r/2}\,|\hat{f}(k)|^{2}\leq 4\sum_{r\geq m}\log^{2s}(r)\,d_{\lfloor
r/8\rfloor}(F)^{2}\\\ &\leq 32\sum_{k\geq\lfloor
m/8\rfloor}\log^{2s}(8k+7)\,d_{k}(F)^{2}.\end{split}$

Likewise, inequality (15) becomes

$\max\bigg{\\{}\sigma_{m}^{2},\,\frac{1}{m}\sum_{k\geq
m}\sigma_{k}^{2}\,\bigg{\\}}\,\lesssim\,m^{-1}\log^{-2s+1}m$

and the stated inequality is obtained. ∎

###  6.3. Proof of Corollary 4

Using the same bound as in the proof of Corollary 2, the case $\alpha>1/2$
immediately follows from Theorem 3 if we choose $1/\alpha<p<2$, and the case
$\alpha=1/2$, $\beta>1$ from Theorem 27 if we choose $1/2<s<\beta-1/2$.

All bounds are attained with the same classes $F$ as in Corollary 2 for the
first case, and with the constructions from the next section for the two other
cases.
∎

##  7\. Examples

We first apply Theorem 1 to tensor product spaces.

######  Example 28.

Let $H$ be a RKHS on $D$ that is compactly embedded into $L_{2}$ and let $F$
be its unit ball. We consider $L_{2}$-approximation on the unit ball $F_{d}$
of the $d$-fold tensor product $H_{d}$ of $H$, which is a RKHS on the domain
$D^{d}$. We assume that $g_{n}(F)\lesssim n^{-\alpha}$ for some $\alpha>0$.
The famous Smolyak algorithm, see [47], gives the estimate

(16) $g_{n}(F_{d})\,\lesssim\,n^{-\alpha}\log^{(\alpha+1)(d-1)}n.$

An example of such tensor product spaces are the spaces of dominating mixed
smoothness $\alpha>1/2$, see [11]. For these spaces, it is known that the
error bound (16) for the Smolyak algorithm can be improved [46]; the exponent
of the logarithm can be reduced to $(\alpha+1/2)(d-1)$. With Corollary 2 and
known results on the approximation numbers of tensor product operators, see
[2, 36], we now obtain

(17) $g_{n}(F_{d})\,\lesssim\,n^{-\alpha}\log^{\alpha(d-1)}n\quad\text{if }\
\alpha>1/2.$

This bound is asymptotically optimal for the spaces of mixed smoothness, see
[48, Theorem 1] or [49, Theorem 6.4.3]. More generally, it is known that
$d_{n}(F)\asymp n^{-\alpha}$ implies $d_{n}(F_{d})\asymp
n^{-\alpha}\log^{\alpha(d-1)}n$ (see e.g. [22]) and therefore the asymptotic
bound (17) is optimal whenever the approximation numbers in the univariate
case are of order $n^{-\alpha}$. Let us note, however, that also preasymptotic
estimates on the sampling numbers (say, for $n<d^{d}$) are of interest,
especially if the dimension $d$ is high, see [22, 29, 58].
∎

We now present two examples that show that our upper bounds cannot be improved
without further assumptions on the class $F$.

First, we show that the worst possible behavior of the sampling numbers in the
case $d_{n}(F)\lesssim n^{-1/2}\log^{-\beta}n$ with $\beta>1$ is indeed
$n^{-1/2}\log^{-\beta+1}n$.

######  Example 29.

For $\ell\in\mathbb{N}_{0}$ and $k\in\\{1,\ldots,2^{\ell}\\}$ define the
interval $I_{\ell,k}=[(k-1)2^{-\ell},k2^{-\ell})$ and denote with
$\chi_{\ell,k}$ the indicator function of $I_{\ell,k}$. Let $\beta>1$. We set

$\mathcal{C}_{\beta}\,:=\,\bigg{\\{}\mathbf{c}:=(c_{\ell,k})_{\ell\in\mathbb{N}_{0},\,1\leq
k\leq
2^{\ell}}\,\Big{|}\,\sum_{k=1}^{2^{\ell}}|c_{\ell,k}|^{2}\leq(\ell+1)^{-2\beta}\text{
for all }\ell\in\mathbb{N}_{0}\bigg{\\}}$

and consider the class

$F_{\beta}\,:=\,\bigg{\\{}f_{\mathbf{c}}:=\sum_{\ell\in\mathbb{N}_{0}}\sum_{k=1}^{2^{\ell}}c_{\ell,k}\chi_{\ell,k}\,\Big{|}\,\mathbf{c}\in\mathcal{C}_{\beta}\bigg{\\}}.$

Note that the series $f_{\mathbf{c}}$ converge uniformly, since the inner sum
is bounded by $(\ell+1)^{-\beta}$. If $F_{\beta}$ is equipped with the maximum
distance on $[0,1)$, it is a separable metric space, function evaluation is
continuous, and the embedding in $L_{2}([0,1))$ is continuous.

For every $L\in\mathbb{N}_{0}$, the span $V_{L}$ of the functions
$\chi_{\ell,k}$ with $\ell\leq L$ has dimension $2^{L}$. If $P_{L}$ is the
$L_{2}$-orthogonal projection onto $V_{L}$, we have for all
$\mathbf{c}\in\mathcal{C}_{\beta}$ that

$\big{\|}f_{\mathbf{c}}-P_{L}f_{\mathbf{c}}\big{\|}_{2}\leq\Big{\|}\sum_{(\ell,k)\colon\ell>L}c_{\ell,k}\chi_{\ell,k}\Big{\|}_{2}\leq\sum_{\ell>L}\Big{\|}\sum_{k=1}^{2^{\ell}}c_{\ell,k}\chi_{\ell,k}\Big{\|}_{2}\\\
=\sum_{\ell>L}\bigg{(}\sum_{k=1}^{2^{\ell}}c_{\ell,k}^{2}\|\chi_{\ell,k}\|_{2}^{2}\bigg{)}^{1/2}\leq\sum_{\ell>L}2^{-\ell/2}(\ell+1)^{-\beta}\lesssim
2^{-L/2}L^{-\beta},$

and thus

$d_{2^{L}}(F_{\beta})\,\lesssim\,2^{-L/2}L^{-\beta},$

or equivalently

$d_{n}(F_{\beta})\,\lesssim\,n^{-1/2}\log^{-\beta}n.$

We now show a lower bound for the sampling numbers. Let
$x_{1},\ldots,x_{n}\in[0,1)$. For all $\ell\in\mathbb{N}_{0}$, we let
$J_{\ell}$ be the set of indices $1\leq k\leq 2^{\ell}$ such that $I_{\ell,k}$
contains at least one of these points. Clearly, the cardinality of $J_{\ell}$
is at most $n$. We choose $L\in\mathbb{N}_{0}$ of order $\log n$ and define

$f_{L}\,:=\,\sum_{\ell>L}|J_{\ell}|^{-1/2}(\ell+1)^{-\beta}\sum_{k\in
J_{\ell}}\chi_{\ell,k}.$

This function is contained in $F_{\beta}$ and for all $i\leq n$, we have

$h\,:=\,f_{L}(x_{i})\,=\,\sum_{\ell>L}|J_{\ell}|^{-1/2}(\ell+1)^{-\beta}\,\gtrsim\,n^{-1/2}\log^{-\beta+1}n,$

where $h$ is independent of $i$. On the other hand, as shown by our previous
calculation,

$\Big{|}\int_{0}^{1}f_{L}(x)\,dx\Big{|}\,\leq\,\big{\|}f_{L}\big{\|}_{2}\,\lesssim\,2^{-L/2}L^{-\beta}\,\lesssim\,n^{-1/2}\log^{-\beta}n.$

Thus, if we set $f=h-f_{L}$, the function is contained in $F_{\beta}$,
vanishes at all points $x_{1},\ldots,x_{n}$, and satisfies

$\|f\|_{2}\,\geq\,\int_{0}^{1}f(x)\,dx\,\geq\,h-\Big{|}\int_{0}^{1}f_{L}(x)\,dx\Big{|}\,\gtrsim\,n^{-1/2}\log^{-\beta+1}n.$

This shows $g_{n}(F_{\beta})\gtrsim n^{-1/2}\log^{-\beta+1}n$.
∎

The next example shows that, in the case $d_{n}(F)\lesssim
n^{-1/2}\log^{-\beta}n$ with $\beta\leq 1$, no general statement on the
sampling numbers is possible.

######  Example 30.

Similar to Example 29, we define

$\mathcal{C}\,:=\,\bigg{\\{}\mathbf{c}\,\,\Big{|}\,\sum_{k=1}^{2^{\ell}}|c_{\ell,k}|^{2}\leq(\ell+1)^{-2}\log(\ell+e)^{-2}\text{
for all }\ell\in\mathbb{N}_{0}\bigg{\\}}$

and consider the class

$F\,:=\,\bigg{\\{}f_{\mathbf{c}}:=\sum_{\ell\in\mathbb{N}_{0}}\sum_{k=1}^{2^{\ell}}c_{\ell,k}\chi_{\ell,k}\,\Big{|}\,\mathbf{c}\in\mathcal{C},\,\mathbf{c}\text{
finite}\bigg{\\}}.$

The finiteness of the sequences ensures that $F$, equipped with the maximum
distance, is still a separable metric space, where function evaluation is
continuous, and the embedding in $L_{2}([0,1))$ is continuous. As above, we
obtain

$d_{n}(F)\,\lesssim\,n^{-1/2}(\log n)^{-1}(\log\log n)^{-1}.$

In particular, we have $(d_{n}(F)\log^{1/2}n)\in\ell_{2}$. On the other hand,
given $x_{1},\ldots,x_{n}$ and $\varepsilon>0$, we choose $L\in\mathbb{N}_{0}$
with

$\sum_{\ell>L}2^{-\ell/2}(\ell+1)^{-1}(\log(\ell+e))^{-1}\,\leq\,\varepsilon,$

define the sets $J_{\ell}$ as above, and choose $N\in\mathbb{N}_{0}$ such that

$h\,:=\,\sum_{\ell=L+1}^{N}|J_{\ell}|^{-1/2}(\ell+1)^{-1}(\log(\ell+e))^{-1}\,\geq\,1.$

The function

$f_{L}\,:=\,\frac{1}{h}\sum_{\ell=L+1}^{N}|J_{\ell}|^{-1/2}(\ell+1)^{-1}(\log(\ell+e))^{-1}\sum_{k\in
J_{\ell}}\chi_{\ell,k},$

is contained in $F$, its integral is at most $\varepsilon$, and it satisfies
$f_{L}(x_{i})=1$ for all $i\leq n$. Then $f=1-f_{L}$ is contained in $F$,
vanishes at all points $x_{1},\ldots,x_{n}$, and satisfies

$\|f\|_{2}\,\geq\,\int_{0}^{1}f(x)\,dx\,\geq\,1-\Big{|}\int_{0}^{1}f_{L}(x)\,dx\Big{|}\,\geq\,1-\varepsilon.$

This shows $g_{n}(F)\geq 1$ for all $n\in\mathbb{N}_{0}$.
∎

We note that the lower bounds in Example 29 and 30 already hold for the easier
problem of numerical integration on $F_{\beta}$. Thus, the upper bounds from
Corollary 4 are also sharp for the minimal error of quadrature rules on
probability spaces.

## References

  * [1] S. T. Ali, J.-P. Antoine, J.-P. Gazeau, _Coherent states, wavelets, and their generalizations_. Second edition. Theoretical and Mathematical Physics. Springer, New York, 2014.
  * [2] K. I. Babenko, About the approximation of periodic functions of many variable trigonometric polynomials. Doklady Akademii Nauk SSSR, 32, 247–250, 1960.
  * [3] J. Batson, D.A. Spielman, and N. Srivastava, Twice-Ramanujan Sparsifiers, SIAM Review, 56, 315-334, 2014.
  * [4] F. Bartel, M. Schäfer and T. Ullrich, Constructive subsampling of finite frames with applications in optimal function recovery, arXiv:2202.12625, 2022.
  * [5] M. Bownik, _Continuous frames and the Kadison-Singer problem_. Coherent states and their applications, 63-88. Springer, Cham, 2018.
  * [6] O. Christensen, _An introduction to frames and Riesz bases_ , Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Inc., Boston, MA, 2003.
  * [7] A. Cohen and M. Dolbeault, Optimal pointwise sampling for $L_{2}$ approximation, Journal of Complexity, 68, 101602, 2022.
  * [8] A. Cohen and G. Migliorati, _Optimal weighted least squares methods,_ SMAI Journal of Computational Mathematics, 3, 181-203, 2017.
  * [9] F. Cucker and S. Smale, _On the mathematical foundations of learning_ , Bulletin of the American mathematical society, 39(1), 1-49, 2002.
  * [10] R.A. DeVore and G.G. Lorentz, _Constructive approximation_ , Vol. 303. Springer Science & Business Media, 1993.
  * [11] D. Dũng, V. N. Temlyakov and T. Ullrich.  Hyperbolic Cross Approximation.  Advanced Courses in Mathematics - CRM Barcelona. Springer International Publishing, 2018.
  * [12] D. Freeman and D. Speegle _The discretization problem for continuous frames_ , Advances in Mathematics 345, 784-813, 2019.
  * [13] 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.
  * [14] A. Hinrichs, D. Krieg, E. Novak, J. Prochno and M. Ullrich, Random sections of ellipsoids and the power of random information, Transactions of the American Mathematical Society 374(12), 8691-8713, 2021.
  * [15] A. Hinrichs, D. Krieg, E. Novak, J. Prochno, and M. Ullrich.  On the power of random information.  In F. J. Hickernell and P. Kritzer, editors, Multivariate Algorithms and Information-Based Complexity, 43-64. De Gruyter, Berlin/Boston, 2020.
  * [16] A. Hinrichs, D. Krieg, E. Novak and J. Vybiral, Lower bounds for the error of quadrature formulas for Hilbert spaces, Journal of Complexity, 65, 101544, 2021, https://doi.org/10.1016/j.jco.2020.101544.
  * [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] A. Hinrichs, J. Prochno, and M. Sonnleitner, Random sections of $\ell_{p}$-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators, arXiv:2109.14504, 2021.
  * [19] L. Kaemmerer, T. Ullrich, and T. Volkmer, Worst case recovery guarantees for least squares approximation using random samples, Constructive Approximation, 54(2), 295-352, 2021.
  * [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] D. Krieg, Optimal Monte Carlo methods for $L_{2}$-approximation, Constructive Approximation, 49, 385–403, 2019.
  * [22] D. Krieg, Tensor power sequences and the approximation of tensor product operators, Journal of Complexity, 44, 30–51, 2018.
  * [23] D. Krieg, E. Novak, and M. Sonnleitner, Recovery of Sobolev functions restricted to iid sampling, Mathematics of Computation, 91, 2715–2738, 2022.
  * [24] D. Krieg, P. Siedlecki, M. Ullrich, and H. Woźniakowski, Exponential tractability of $L_{2}$-approximation with function values, arXiv:2205.04141, 2022.
  * [25] D. Krieg and M. Sonnleitner, Random points are optimal for the approximation of Sobolev functions, arXiv:2009.11275, 2022.
  * [26] D. Krieg and M. Sonnleitner, Function recovery on manifolds using scattered data, arXiv:2109.04106, 2022.
  * [27] D. Krieg and M. Ullrich, Function values are enough for $L_{2}$-approximation, Foundations of Computational Mathematics, 21(4), 1141-1151, 2021.
  * [28] 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.
  * [29] 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.
  * [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] Y. T. Lee and H. Sun, Constructing linear-sized spectral sparsification in almost-linear time, SIAM Journal on Computing, 47(6), 2315-2336, 2018.
  * [32] I. Limonova and V. Temlyakov, On sampling discretization in $L_{2}$, Journal of Mathematical Analysis and Applications, 515(2), 126457, 2022.
  * [33] W. Lu and H. Wang, On the power of standard information for tractability for $L_{2}$-approximation in the randomized setting, Journal of Complexity, 70, 101618, 2022.
  * [34] A. Marcus, D. Spielman and N. Srivastava, Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem, Annals of Mathemathics, 327-350, 2015, http://dx.doi.org/10.4007/annals.2015.182.1.8.
  * [35] S. Mendelson and A. Pajor, On singular values of matrices with independent rows, Bernoulli, 12(5), 761-773, 2006.
  * [36] B. S. Mityagin, Approximation of functions in $L^{p}$ and $C$ on the torus. Mathematical Notes, 58, 397–414, 1962.
  * [37] 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.
  * [38] N. Nagel, M. Schäfer, and T. Ullrich, A new upper bound for sampling numbers, Foundations of Computational Mathematics, 22(2), 445-468, 2022.
  * [39] S. Nitzan, A. Olevskii and A. Ulanovskii, A few remarks on sampling of signals with small spectrum, Proceedings of the Steklov Institute of Mathematics, 280(1), 240-247, 2013.
  * [40] S. Nitzan, A. Olevskii and A. Ulanovskii, Exponential frames on unbounded sets, Proceedings of the American Mathematical Society, vol. 144, no 1, 109-118, 2016, http://dx.doi.org/10.1090/proc/12868.
  * [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 II: Standard information for functionals, volume 12 of EMS Tracts in Mathematics.  European Mathematical Society (EMS), Zürich, 2010.
  * [43] 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.
  * [44] E. Novak and H. Woźniakowski.  Tractability of multivariate problems for standard and linear information in the worst case setting: part I,  Journal of Approximation Theory, 207, 177–192, 2016.
  * [45] R. Salem. A new proof of a theorem of Menchoff, Duke Mathematical Journal, 8(2), 269–272, 1941.
  * [46] W. Sickel and T. Ullrich, Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness, East Journal on Approximations, 13(4), 387–425, 2007.
  * [47] S. A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Soviet Mathematics Doklady, 4, 240–243, 1963.
  * [48] V. N. Temlyakov.  On a way of obtaining lower estimates for the errors of quadrature formulas, Mathematics of the USSR-Sbornik, 71(1), 247, 1992.
  * [49] V. N. Temlyakov.  Multivariate Approximation, volume 32 of Cambridge Monographs on Applied and Computational Mathematics.  Cambridge University Press, 2018.
  * [50] V. N. Temlyakov, On optimal recovery in $L_{2}$, Journal of Complexity, 65, 101545, 2020, https://doi.org/10.1016/j.jco.2020.101545.
  * [51] V. N. Temlyakov, The Marcinkiewicz-type discretization theorems, Constructive Approximation, 48, 337-369, 2018.
  * [52] V. N. Temlyakov, T. Ullrich. Approximation of functions with small mixed smoothness in the uniform norm, Journal of Approximation Theory, 277, 105718, 2022.
  * [53] V. N. Temlyakov and T. Ullrich, Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness, Journal of Complexity, 67, 101575, 2021.
  * [54] J. F. Traub, H. Woźniakowski.  A general theory of optimal algorithms.  Academic Press, 1980.
  * [55] M. Ullrich, On the worst-case error of least squares algorithms for $L_{2}$-approximation with high probability, Journal of Complexity, 60, 2020.
  * [56] J. Vybíral, A variant of Schur’s product theorem and its applications, Advances in Mathematics, 368, 107140, 2020.
  * [57] M. J. Wainwright.  High-Dimensional statistics. A non-asymptotic viewpoint.  Cambridge University Press, 2019.
  * [58] G. W. Wasilkowski and H. Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems, Journal of Complexity, 11, 1–56, 1995.
  * [59] G. W. Wasilkowski and H. Woźniakowski. On the power of standard information for weighted approximation, Foundations of Computational Mathematics, 1(4), 417-434, 2001.
  * [60] G.W. Wasilkowski and H. Woźniakowski, The power of standard information for multivariate approximation in the randomized setting, Mathematics of Computation, 76, 965-988, 2007.
  * [61] H. Wendland, _Scattered data approximation_ , Vol. 17, Cambridge university press, 2004.