$\mathbf{\Sigma}\in\mathds{R}^{n\times m}$ with $\tau_{1},\ldots,\tau_{m}$ on
the diagonal. Then

$(\bm{M}^{\ast}\bm{M})^{-1}\bm{M}^{\ast}=\bm{V}\tilde{\mathbf{\Sigma}}\bm{U}^{\ast}\quad,\;\text{with
the
matrix}\quad\tilde{\mathbf{\Sigma}}:=(\mathbf{\Sigma}^{\ast}\mathbf{\Sigma})^{-1}\mathbf{\Sigma}^{\ast}\in\mathds{R}^{m\times
n}$

being a rectangular diagonal matrix having
$\tau_{1}^{-1},\ldots,\tau_{m}^{-1}$ as diagonal entries.

  * (iii)

For the operator norm we have
$\|(\bm{M}^{\ast}\bm{M})^{-1}\bm{M}^{\ast}\|_{2\to 2}=\tau_{m}^{-1}$.

##  Appendix B Matrix theory

A basic tool in Subsection 3.3 is the matrix determinant lemma (cf. [1, Lem.
2.2]). The complex version reads as follows.

######  Lemma B.1 (Matrix determinant lemma).

If $\bm{A}\in\mathds{C}^{m\times m}$ is nonsingular and
$\bm{v}\in\mathds{C}^{m}$ is a vector, then

$\det(\bm{A}+\bm{v}\bm{v}^{\ast}\big{)}=\det(\bm{A})(1+\bm{v}^{\ast}\bm{A}^{-1}\bm{v})\,.$

Lemma B.1 is a direct consequence of the Sherman-Morrison formula (see e.g.
[10])

$\big{(}\bm{A}+\bm{v}\bm{v}^{\ast}\big{)}^{-1}=\bm{A}^{-1}-\frac{\bm{A}^{-1}\bm{v}\bm{v}^{\ast}\bm{A}^{-1}}{1+\bm{v}^{\ast}\bm{A}^{-1}\bm{v}}\,,$

which holds under the same assumptions as in Lemma B.1.

Another basic result, needed in the proof of Lemma 3.11, is the following
statement.

######  Lemma B.2.

Let $(\bm{y}^{i})_{i=1}^{M}\subset\mathds{C}^{m}$ be a frame with frame bounds
$0<A\leq B<\infty$. Let further $\bm{M}\in\mathds{C}^{m\times m}$ be a
positive semi-definite Hermitian matrix. Then

$\displaystyle
A\operatorname*{tr}(\bm{M})\leq\sum_{i=1}^{M}(\bm{y}^{i})^{\ast}\bm{M}\bm{y}^{i}\leq
B\operatorname*{tr}(\bm{M})\,.$

###### Proof.

First, observe that for an arbitrary matrix $\bm{M}\in\mathds{C}^{m\times m}$

$\displaystyle\sum_{i=1}^{M}(\bm{y}^{i})^{\ast}\bm{M}\bm{y}^{i}$
$\displaystyle=\sum_{i=1}^{M}\operatorname*{tr}\Big{(}(\bm{y}^{i})^{\ast}\bm{M}\bm{y}^{i}\Big{)}=\sum_{i=1}^{M}\operatorname*{tr}\Big{(}\bm{M}\bm{y}^{i}(\bm{y}^{i})^{\ast}\Big{)}=\operatorname*{tr}\Big{(}\bm{M}\Big{(}\sum_{i=1}^{M}\bm{y}^{i}(\bm{y}^{i})^{\ast}\Big{)}\Big{)}\,.$

Since $\bm{Y}:=\sum_{i=1}^{M}\bm{y}^{i}(\bm{y}^{i})^{\ast}$ is positive-
definite Hermitian with $\sigma(\bm{Y})\subset[A,B]$, there exists a unitary
matrix $\bm{U}$ such that $\bm{D}:=\bm{U}\bm{Y}\bm{U}^{-1}$ is diagonal with
entries in the range $[A,B]$. We can hence conclude

$\displaystyle\sum_{i=1}^{M}(\bm{y}^{i})^{\ast}\bm{M}\bm{y}^{i}=\operatorname*{tr}\Big{(}\bm{M}\bm{Y}\Big{)}=\operatorname*{tr}\Big{(}\bm{U}\bm{M}\bm{Y}\bm{U}^{-1}\Big{)}=\operatorname*{tr}\Big{(}\bm{U}\bm{M}\bm{U}^{-1}\bm{D}\Big{)}\,.$

Under the assumption that $\bm{M}$ is positive semi-definite Hermitian the
transformation $\bm{U}\bm{M}\bm{U}^{-1}$ is also positive semi-definite
Hermitian. In particular, its diagonal entries are all nonnegative real
numbers. As a consequence, we obtain the assertion

$\displaystyle
A\operatorname*{tr}\Big{(}\bm{M}\Big{)}=A\operatorname*{tr}\Big{(}\bm{U}\bm{M}\bm{U}^{-1}\Big{)}\leq\operatorname*{tr}\Big{(}\bm{M}\bm{Y}\Big{)}\leq
B\operatorname*{tr}\Big{(}\bm{U}\bm{M}\bm{U}^{-1}\Big{)}=B\operatorname*{tr}\Big{(}\bm{M}\Big{)}\,.$

∎

###  B.1 Concentration results for random matrices

Here we give some concentration inequalities which enable us to control the
spectrum of sums of Hermitian positive semi-definite rank-$1$ matrices. In the
finite case, these sums take the form

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\bm{u}^{i}\otimes\bm{u}^{i}\quad\text{for
a sequence of random vectors }\bm{u}^{i}\in\mathds{C}^{m},\,i\in[n]\,.$ (B.1)

Recall the notation $[n]=\\{1,\ldots,n\\}$. The basic assumption is always
that the vectors $\bm{u}^{i}$ are drawn i.i.d. according to some probability
distribution and that a uniform bound $\|\bm{u}^{i}\|_{2}\leq M$ is satisfied
almost surely for every $i\in[n]$. Putting
$\bm{A}_{i}:=\frac{1}{n}\bm{u}^{i}\otimes\bm{u}^{i}$, we obtain a sequence
$({\bm{A}_{i}})_{i=1}^{n}$ of i.i.d. Hermitian positive semi-definite random
matrices which satisfy
$\operatorname{\lambda_{\mathrm{m}ax}}(\bm{A}_{i})\leq\frac{M^{2}}{n}$ almost
surely. In this situation, a matrix Chernoff inequality proved by Tropp [30,
Thm. 1.1] can be applied. We derive the following form.

######  Lemma C.1 (Matrix Chernoff, cf. [30, Thm. 1.1]).

For a sequence $(\bm{A}_{i})_{i=1}^{n}\subset\mathds{C}^{m\times m}$ of
independent, Hermitian, positive semi-definite random matrices satisfying
$\lambda_{\max}(\bm{A}_{i})\leq R$ almost surely it holds

$\displaystyle\mathbb{P}\bigg{(}\operatorname{\lambda_{\mathrm{m}in}}\Big{(}\sum_{i=1}^{n}\bm{A}_{i}\Big{)}\leq(1-t)\mu_{\min}\bigg{)}$
$\displaystyle\leq{m}\exp\Big{(}-\frac{\mu_{\min}}{R}(t+(1-t)\log(1-t))\Big{)}$
$\displaystyle\leq{m}\exp\Big{(}-\frac{\mu_{\min}t^{2}}{2R}\Big{)}$

and

$\displaystyle\mathbb{P}\bigg{(}\operatorname{\lambda_{\mathrm{m}ax}}\Big{(}\sum_{i=1}^{n}\bm{A}_{i}\Big{)}\geq(1+t)\mu_{\max}\bigg{)}$
$\displaystyle\leq{m}\exp\Big{(}-\frac{\mu_{\max}}{R}(-t+(1+t)\log(1+t))\Big{)}$
$\displaystyle\leq{m}\exp\Big{(}-\frac{\mu_{\max}t^{2}}{3R}\Big{)}$

for $t\in[0,1]$, where
$\mu_{\min}\coloneqq\lambda_{\min}(\sum_{i=1}^{n}\mathds{E}\bm{A}_{i})$ and
$\mu_{\max}\coloneqq\lambda_{\max}(\sum_{i=1}^{n}\mathds{E}\bm{A}_{i})$.

###### Proof.

The first estimates are provided by [30, Thm. 1.1]. Based on the Taylor
expansion

$\displaystyle(1+t)\log(1+t)=t+\sum_{k=2}^{\infty}\frac{(-1)^{k}}{k(k-1)}t^{k}\,,$

which holds true for $t\in[-1,1]$, we can further derive the inequalities

$\displaystyle t+(1-t)\log(1-t)$
$\displaystyle=\sum_{k=2}^{\infty}\frac{1}{k(k-1)}t^{k}\geq\frac{t^{2}}{2}$
and $\displaystyle-t+(1+t)\log(1+t)$
$\displaystyle=\sum_{k=2}^{\infty}\frac{(-1)^{k}}{k(k-1)}t^{k}\geq\frac{t^{2}}{2}-\frac{t^{3}}{6}\geq\frac{t^{2}}{3}$

for the range $t\in[0,1]$. ∎

A concentration inequality for the case when the vectors $\bm{u}^{i}$ in (B.1)
are infinite dimensional is given in [18, Thm. 1.1]. Here it is assumed that
the $\bm{u}^{i}$ are i.i.d. random sequences from $\ell_{2}(\mathds{N})$. Let
us recite this result.

######  Theorem C.2 ([18, Thm. 1.1]).

Let $\bm{u}^{i},i\in[n],$ be i.i.d. random sequences from
$\ell_{2}(\mathds{N})$. Let further $n\geq 3$, $M>0$ such that
$\|\bm{u}^{i}\|_{2}\leq M$ almost surely and
$\mathbb{E}(\bm{u}^{i}\otimes\bm{u}^{i})={\mathbf{\Lambda}}$ for $i\in[n]$
with $\|\bm{\Lambda}\|_{2\to 2}\leq 1$. Then

$\mathbb{P}\Big{(}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\,\bm{u}^{i}\otimes\bm{u}^{i}-{\mathbf{\Lambda}}\Big{\|}_{2\to
2}\geq t\Big{)}\leq
2^{\frac{3}{4}}n\exp\Big{(}-\frac{t^{2}n}{21M^{2}}\Big{)}\,.$

A useful rephrasing of Theorem C.2 is given by [18, Prop. 3.8]. It is as
follows.

######  Proposition C.3 ([18, Prop. 3.8]).

Let $\bm{u}^{i},i\in[n]$, be i.i.d. random sequences from
$\ell_{2}(\mathds{N})$. Let further $n\geq 3$, $r>1$, $M>0$ such that
$\|\bm{u}^{i}\|_{2}\leq M$ almost surely and
$\mathbb{E}(\bm{u}^{i}\otimes\bm{u}^{i})={\mathbf{\Lambda}}$ for all
$i\in[n]$. Then

$\mathbb{P}\Big{(}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\,\bm{u}^{i}\otimes\bm{u}^{i}-{\mathbf{\Lambda}}\Big{\|}_{2\to
2}\geq F\Big{)}\leq 2^{\frac{3}{4}}\,n^{1-r}\,,$

where $F:=\max\Big{\\{}\frac{8r\log
n}{n}M^{2}\nu^{2},\|{\mathbf{\Lambda}}\|_{2\to 2}\Big{\\}}$ and
$\nu=\frac{1+\sqrt{5}}{2}$ .

##  Appendix C The considered RKHS setting

In Subsection 6.2 we consider functions from a RKHS $H(K)$ on a non-empty
measure space $(D,\nu)$. In the sequel, this setting is analyzed in more
detail. First note that the space $H(K)$, as a RKHS, consists of proper point-
wise defined functions. By definition, it is associated with a positive semi-
definite Hermitian kernel $K:D\times D\to\mathds{C}$ such that the reproducing
property

$\displaystyle f(x)=\langle f,K(\cdot,x)\rangle_{H(K)}$ (C.1)

holds true for all $f\in H(K)$ and $x\in D$. Due to this property, sampling is
not only a well-defined but even continuous operation in $H(K)$ (see e.g.
[11]).

For our analysis of $L_{2}$-approximation, an embedding relation between
$H(K)$ and $L_{2}(D,\nu)$ is crucial. It is guaranteed by the presumed finite
trace of $K$, namely

$\operatorname*{tr}(K):=\int_{D}K(x,x)\,d\nu(x)<\infty\,.$

Under such a condition, see [11] and [26, Lem. 2.3], for every $f\in H(K)$

$\displaystyle\|f\|^{2}_{2}=\int_{D}|\langle
f,K(\cdot,x)\rangle|^{2}\,d\nu(x)\leq\int_{D}\|f\|_{H(K)}^{2}\|K(\cdot,x)\|_{H(K)}^{2}\,d\nu(x)=\|f\|_{H(K)}^{2}\cdot\operatorname*{tr}(K)\,.$

As a consequence, there is a compact embedding

$\mathrm{Id}_{K,\nu}:H(K)\hookrightarrow L_{2}(D,\nu)\,,$

which can be shown to be even Hilbert-Schmidt (see [26, Lem. 2.3]). Here, it
is important to note that, in contrast to $H(K)$, the elements of
$L_{2}(D,\nu)$ are not functions but $\nu$-equivalence classes, with two
functions $f,\tilde{f}:D\to\mathds{C}$ considered $\nu$-equivalent if
$f(x)=\tilde{f}(x)$ for $\nu$-almost every $x\in D$. $\mathrm{Id}_{K,\nu}$ may
hence not be injective. In fact, $\mathrm{Id}_{K,\nu}$ is the restriction of
$\mathrm{Id}_{\nu}$ to $H(K)$, where $\mathrm{Id}_{\nu}$ is the map that
assigns to every $f:D\to\mathds{C}$ the corresponding $\nu$-equivalence class.
Depending on the measure $\nu$, the null-space
$\mathcal{N}(\mathrm{Id}_{K,\nu})$ can thus be non-trivial. The choice $\nu=0$
illustrates this, where $\mathcal{N}(\mathrm{Id}_{K,\nu})=H(K)$.

Without loss of generality, to simplify the considerations in Subsection 6.2,
it is further assumed that the subspace $\mathrm{Id}_{K,\nu}(H(K))$ of
$L_{2}(D,\nu)$ is infinite dimensional (i.e. that $\mathrm{Id}_{K,\nu}$ has
infinite rank). Under this condition, the sequence
$(\sigma_{k})_{k\in\mathds{N}}$ of strictly positive singular numbers
associated to $\mathrm{Id}_{K,\nu}$ is countably infinite. For this, note that
$\mathrm{Id}_{K,\nu}(H(K))$ is a separable subspace of $L_{2}(D,\nu)$ due to
the compactness of $\mathrm{Id}_{K,\nu}$.

We now fix orthonormal systems $(\eta_{k})_{k\in\mathds{N}}\subset
L_{2}(D,\nu)$ and $(e_{k})_{k\in\mathds{N}}\subset H(K)$ of associated left
and right singular functions such that

$\displaystyle e_{k}=\sigma_{k}\eta_{k}\quad\text{for all}\quad
k\in\mathds{N}\,.$ (C.2)

Whereas each $e_{k}$ represents a point-wise function on $D$, the left
singular functions $\eta_{k}$, as elements of $L_{2}(D,\nu)$, refer to
$\nu$-equivalence classes. However, we choose for each $\eta_{k}$ the specific
representative $e_{k}/\sigma_{k}$ so that both systems
$(\eta_{k})_{k\in\mathds{N}}$ and $(e_{k})_{k\in\mathds{N}}$ are comprised of
proper functions satisfying (C.2) in a point-wise sense.

Let us next ask for basis properties of these systems. Clearly,
$(\eta_{k})_{k\in\mathds{N}}$ is a basis for $\mathrm{Id}_{K,\nu}(H(K))$. The
system $(e_{k})_{k\in\mathds{N}}$, on the other hand, is usually not a basis
for $H(K)$ since it only corresponds to the non-trivial singular numbers of
$\mathrm{Id}_{K,\nu}$. Under additional restrictions ensuring
$\mathcal{N}(\mathrm{Id}_{K,\nu})=\\{0\\}$ it would be, e.g. if the kernel $K$
is continuous and bounded (i.e. a Mercer kernel). Generally, $H(K)$ decomposes
in the form

$\displaystyle
H(K)=\overline{\operatorname*{span}}\\{e_{1},e_{2},\ldots\\}\oplus_{\text{orth}}^{H}\mathcal{N}(\mathrm{Id}_{K,\nu})\,.$

A useful representation of $K$ in terms of the functions
$(e_{k})_{k\in\mathds{N}}$ can be obtained as follows. For each $y\in D$,
first expand the function $K(\cdot,y)\in H(K)$ in the form

$\displaystyle K(\cdot,y)=\sum_{k\in\mathds{N}}c_{k}e_{k}+r_{y}$

with an associated function $r_{y}\in\mathcal{N}(\mathrm{Id}_{K,\nu})$ and
convergence of the sum in $H(K)$. For the coefficients calculate with (C.1)

$\displaystyle c_{k}=\langle
K(\cdot,y),e_{k}\rangle_{H(K)}=\overline{e_{k}(y)}\,.$

Since convergence in $H(K)$ entails point-wise convergence, we obtain the
representation

$\displaystyle
K(x,y)=\sum_{k\in\mathds{N}}e_{k}(x)\overline{e_{k}(y)}+r_{y}(x)\,.$

In case that $H(K)$ is separable, which is assumed in Theorem 6.7, it is shown
in [11] and [26, Cor. 3.2] that $r_{x}(x)$ vanishes $\nu$-almost everywhere.
We hence have $K(x,x)=\sum_{k\in\mathds{N}}|e_{k}(x)|^{2}$ for $\nu$-almost
every $x\in D$. This is a crucial ingredient in the proof of Theorem 6.7, see
also [18, Sec. 4] and [12, Sec. 2].