# Random sections of $\ell_{p}$-ellipsoids, optimal recovery and Gelfand
numbers of diagonal operators

Aicke Hinrichs 111Institute of Analysis, University of Linz,
Altenbergerstrasse 69, 4040 Linz, Austria<EMAIL_ADDRESS> , Joscha
Prochno 222Faculty of Computer Science and Mathematics, University of Passau,
Innstrasse 33, 94032 Passau, Germany<EMAIL_ADDRESS>and
Mathias Sonnleitner 333Department of Mathematics and Scientific Computing,
University of Graz, Heinrichstrasse 36, 8010 Graz, Austria.
<EMAIL_ADDRESS>
###### Abstract

We study the circumradius of a random section of an $\ell_{p}$-ellipsoid,
$0<p\leq\infty$, and compare it with the minimal circumradius over all
sections with subspaces of the same codimension. Our main result is an upper
bound for random sections, which we prove using techniques from asymptotic
geometric analysis if $1\leq p\leq\infty$ and compressed sensing if $0<p\leq
1$. This can be interpreted as a bound on the quality of random (Gaussian)
information for the recovery of vectors from an $\ell_{p}$-ellipsoid for which
the radius of optimal information is given by the Gelfand numbers of a
diagonal operator. In the case where the semiaxes decay polynomially and
$1\leq p\leq\infty$, we conjecture that, as the amount of information
increases, the radius of random information either decays like the radius of
optimal information or is bounded from below by a constant, depending on
whether the exponent of decay is larger than the critical value
$1-\frac{1}{p}$ or not. If $1\leq p\leq 2$, we prove this conjecture by
providing a matching lower bound. This extends the recent work of Hinrichs et
al. [Random sections of ellipsoids and the power of random information, Trans.
Amer. Math. Soc., 2021+] for the case $p=2$.

Keywords: Diagonal operator, Gelfand numbers, Grassmannian manifold,
$\ell_{p}$-ellipsoid, optimal recovery, random section. MSC 2020: Primary
52A23, 65Y20, Secondary 60G15.

##  1 Introduction, motivation and main results

The diameter of a section of a symmetric convex body $K\subset\mathbb{R}^{m}$
with a (random) subspace has been an object of interest at least since the
study of Gelfand numbers of operators between finite-dimensional Banach spaces
[6, 9, 10, 15, 17, 18, 29, 30]. These numbers measure the smallest
circumradius of the intersection with a subspace of a fixed (co)dimension.
Often we are not in a position to exhibit optimal subspaces and thus it seems
reasonable to first try to understand intersections with typical subspaces.
Along this way we are led to the study of the diameter of intersections with
random subspaces which are uniformly distributed on the Grassmannian manifold
with respect to the Haar probability measure.

Connected to the field of asymptotic geometric analysis, there is a large body
of work on this topic initiated by Giannopoulos and V. D. Milman in [7, 8]
with particular focus on subspace dimension proportional to the dimension of
the body (see also [26]). In subsequent work Litvak, Pajor and Tomczak-
Jaegermann [22] have shown that on the scale of proportional subspaces typical
intersections are not much larger than minimal intersections. It is important
to note that, as pointed out in [7, Example 2.2], one cannot expect these
bounds to be sharp in full generality, in particular not for ellipsoids with
highly incomparable semi-axes.

Mendelson, Pajor and Tomczak-Jaegermann [23] studied the intimately related
problem of approximate reconstruction of vectors from a symmetric convex body
$K\subset\mathbb{R}^{m}$ using random Gaussian measurements. Approximation
using random information underlies the success of the field of compressed
sensing, dealing with the reconstruction of sparse vectors (see, e.g., [3,
5]). Somewhat related is the approximation of functions using samples at
random points, which is studied in the context of learning theory (see, e.g.,
the book [24]) and information-based complexity [13, 14]. It is the latter,
specifically the work [14], that serves as further motivation for this paper.
There the effectiveness of Gaussian information for recovering vectors in an
ellipsoid in the Euclidean norm has been studied, which is related to the
approximation of functions with decaying generalized Fourier coefficients,
e.g., Korobov spaces [20]. In a more geometric parlance, the main result of
[14] is that the equivalent problem of determining whether the circumradius of
a random section of the ellipsoid is close to minimal has a positive solution
depending on the square-summability of its semiaxes. In a nutshell, we seek to
extend these results and study random sections of generalized
$\ell_{p}$-ellipsoids. Such ellipsoids have also been studied, for instance,
in [16] with focus on the asymptotic volume distribution of sections of such
ellipsoids as the dimension of the underlying space tends to infinity, and in
[32] where it is shown that such ellipsoids are examples where Dudley’s
integral bound for Gaussian processes is not sharp.

###  1.1 Radii of random sections and optimal recovery

We aim at understanding the circumradius, or equivalently the diameter, of
random sections of generalized ellipsoids and, in particular, whether it is
comparable to the minimal circumradius of all sections of the same dimension
or not. Given $0<p\leq\infty$ our object of interest is the
$\ell_{p}$-ellipsoid

$\mathcal{E}_{p,\sigma}^{m}:=\\{x\in\mathbb{R}^{m}:\|(x_{j}/\sigma_{j})_{j=1}^{m}\|_{p}\leq
1\\}\quad\text{with semiaxes}\quad\sigma_{1}\geq\cdots\geq\sigma_{m}>0,$

where $\|x\|_{p}:=(|x_{1}|^{p}+\cdots+|x_{m}|^{p})^{1/p}$ and
$\|x\|_{\infty}:=\max_{1\leq j\leq m}|x_{j}|$ for
$x=(x_{j})_{j=1}^{m}\in\mathbb{R}^{m}$ denote the standard
$\ell_{p}$-(quasi-)norms with unit balls $\mathbb{B}_{p}^{m}$. To be precise,
if $E$ is a linear subspace of $\mathbb{R}^{m}$, we denote the circumradius of
the section $\mathcal{E}_{p,\sigma}^{m}\cap E$ by

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},E):=\sup_{x\in\mathcal{E}_{p,\sigma}^{m}\cap
E}\|x\|_{2}.$

Note that for $0<p<1$ the set $\mathcal{E}_{p,\sigma}^{m}$ is not convex but
still the unit ball of a quasi-normed space. Before we present our results, we
introduce the closely related problem of recovery using linear information.

Assume we want to learn an unknown $x\in\mathbb{R}^{m}$ given the information
that $x\in\mathcal{E}_{p,\sigma}^{m}$, that is, we have some control over the
decay of the coordinates of $x$. Further, suppose we are given the linear
information $N_{n}x\in\mathbb{R}^{n}$, where $N_{n}\in\mathbb{R}^{n\times m}$
and $n\,(<m)$ can be considerably smaller than $m$. The best we can do using
the given knowledge about $x$ can be measured by the worst-case error (also
known as the radius of the information $N_{n}$)

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},N_{n}):=\inf_{\varphi}\sup_{x\in\mathcal{E}_{p,\sigma}^{m}}\|x-\varphi(N_{n}x)\|_{2},$

where the recovery mapping $\varphi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ can be an
arbitrary mapping allowed to depend on $N_{n}$. The abuse of notation will be
justified in a moment. It follows from elementary results (see, e.g., [25,
Lemma 4.3]) that, if $\mathcal{E}_{p,\sigma}^{m}$ is convex, that is, if
$p\geq 1$,

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},N_{n})=\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},\ker
N_{n}),$ (1)

where the kernel $\ker N_{n}$ is an $(m-n)$-dimensional subspace of
$\mathbb{R}^{m}$ and so of codimension $n$, i.e., it belongs to the
Grassmannian manifold $\mathcal{G}_{m,m-n}$, if we assume the rows of $N_{n}$
to be linearly independent. This is the reason we call
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},N_{n})$ the radius of the information
$N_{n}$. If $\mathcal{E}_{p,\sigma}^{m}$ is non-convex, that is, if $0<p<1$,
then (1) holds up to a factor of 2, see, e.g., Lemma 3. Random information
will be given by a random matrix $G_{n,m}\in\mathbb{R}^{n\times m}$ with
i.i.d. standard Gaussian entries. It follows from rotation invariance that the
distribution of $\ker G_{n,m}$ is equal to the Haar probability measure on the
Grassmannian $\mathcal{G}_{m,m-n}$. Thus, we may define the circumradius of
the intersection of $\mathcal{E}_{p,\sigma}^{m}$ with a random subspace of
codimension $n$ via the random quantity

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})=\sup_{x\in\mathcal{E}_{p,\sigma}^{m}\cap
E_{n}}\|x\|_{2},$

where $E_{n}:=\ker G_{n,m}$. Obviously,
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\geq\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)$
for each realization with the minimal radius

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n):=\inf_{E_{n}}\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},E_{n}),\qquad
n\in\mathbb{N},$

the infimum ranging over all subspaces $E_{n}$ of $\mathbb{R}^{m}$ of
codimension $n$. It is natural to ask to what extent the converse inequality
holds true or, in other words, what is the radius of a typical intersection of
$\mathcal{E}_{p,\sigma}^{m}$ by a random subspace?

The special case $p=2$ has been dealt with in [14], where it has been shown
that

$\mathrm{rad}(\mathcal{E}_{2,\sigma}^{m},G_{n,m})\leq
C\frac{1}{\sqrt{n}}\Big{(}\sum_{j\geq\lfloor
n/4\rfloor}\sigma_{j}^{2}\Big{)}^{1/2}$ (2)

holds with exponentially high probability (in $n$), where $C\in(0,\infty)$ is
an absolute constant. Further, if the semiaxes
$\sigma=(\sigma_{j})_{j\in\mathbb{N}}$ satisfy $\|\sigma\|_{2}=\infty$, then,
with an absolute constant $C\in(0,\infty)$,

$\mathrm{rad}(\mathcal{E}_{2,\sigma}^{m},G_{n,m})\geq C\sigma_{1}$

with exponentially high probability, provided that $m\,(>n)$ is large enough
compared to $n$. Since
$\mathrm{rad}(\mathcal{E}_{2,\sigma}^{m},n)=\sigma_{n+1}$, there is a
dichotomy for the usefulness of Gaussian information compared to optimal
information or, in more geometric parlance, the circumradius of a random
section compared to the minimal one. We seek to extend this result to the
class of $\ell_{p}$-ellipsoids $\mathcal{E}_{p,\sigma}^{m}$ with $p\neq 2$.

###  1.2 Radii of random sections – main results

We are not able to answer the above question in full for the general case, in
part due to the fact that the minimal radius
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)$ is not known exactly for $1\leq
p<2$, see the Appendix for more on optimal sections. This is one of the
reasons why, apart from the following two theorems, we also present results
for the important case of polynomially decaying semiaxes.

Here and in what follows, for two non-negative reals $a_{\alpha}$ and
$b_{\alpha}$ depending on some parameter $\alpha$ from an index set $I$, we
write $a_{\alpha}\lesssim b_{\alpha}$, or equivalently $b_{\alpha}\gtrsim
a_{\alpha}$, if there exists a constant $C\in(0,\infty)$ such that
$a_{\alpha}\leq C\,b_{\alpha}$ for all $\alpha\in I$. If both
$a_{\alpha}\lesssim b_{\alpha}$ and $a_{\alpha}\gtrsim b_{\alpha}$ hold, we
write $a_{\alpha}\asymp b_{\alpha}$. If the constant may depend on some
parameter $\beta$, we shall write $a_{\alpha}\lesssim_{\beta}b_{\alpha}$ and
$a_{\alpha}\gtrsim_{\beta}b_{\alpha}$ instead or, if both estimates hold,
$a_{\alpha}\asymp_{\beta}b_{\alpha}$. As usual, given $1\leq p\leq\infty$, we
shall denote the Hölder conjugate of $p$ by $p^{*}$ so that
$\frac{1}{p}+\frac{1}{p^{*}}=1$.

The first result provides an upper bound on the radius of random information
with high probability and is in the spirit of the results obtained in [14].

######  Theorem A.

For all $m\in\mathbb{N}$ and $1\leq n<m$, we have

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\lesssim\begin{cases}n^{-1/2}\sup\limits_{k\leq
j\leq m}\sigma_{j}\sqrt{\log(j)+1}&:\,p=1,\\\
\sqrt{p^{*}}n^{-1/2}\Big{(}\sum\limits_{j=k}^{m}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}}&:\,1<p\leq\infty,\end{cases}$

with probability at least $1-c_{1}\exp(-c_{2}n)$, where
$c_{1},c_{2}\in(0,\infty)$ are absolute constants, and $k\asymp n$ for $p=1$
while $k\asymp\frac{n}{p^{*}}$ for $p>1$.

The proof relies on a famous theorem of Gordon [11] on subspaces escaping
through a mesh, for which we first need to control the mean width of ‘rounded’
versions of our ellipsoids arising from intersections with a Euclidean ball of
a suitable radius. The idea of cutting away the peaky regions of a convex body
in this way to obtain improved bounds on its mean width is well known, see for
example [23, Section 2]. Then, in order to bound this quantity for the
$\ell_{p}$-ellipsoids, we adapt an approach already used in [14]. There the
main approach had been a random matrix one, but it seems this approach cannot
be adapted to our situation without loosing something compared to Theorem A.

######  Remark 1.

Theorem A extends the upper bound (2). It shows that if
$\|\sigma\|_{p^{*}}<\infty$ we can expect the radius of random sections to
decay at least as fast as $n^{-1/2}$. This also gives a bound on the minimal
radius, see Corollary 3 formulated in terms of Gelfand numbers.

######  Remark 2.

In the context of suprema of Gaussian processes we want to mention that
$\ell_{p}$-ellipsoids with slowly decaying semiaxes are examples where
Dudley’s upper bound is loose. This has been observed, for instance, by van
Handel in [32]. For more information, we refer to the discussion at the end of
Section 2, where we exhibit a bound also depending on $p$, which is not
present in [32].

Employing methods commonly used in the field of compressed sensing, e.g., in a
work of Foucart, Pajor, Rauhut and Ullrich [4] on the Gelfand widths of
$\ell_{p}$-balls in the quasi-Banach regime $0<p\leq 1$, we deduce the
following upper bound for the radius of random information when $0<p\leq 1$
and the semiaxes have polynomial decay.

######  Theorem B.

Let $0<p\leq 1$ and $\sigma_{j}=j^{-\lambda}$, $j\in\mathbb{N}$, for some
$\lambda>0$. Then there exist constants $C,D\in(0,\infty)$ such that, for all
$m\in\mathbb{N}$ and all $1\leq n<m$ with

$n\geq D\log({\rm e}m/n),$

we have

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},\ker
G_{n,m})\lesssim_{p}\Big{(}\frac{\log({\rm
e}m/n)}{n}\Big{)}^{\lambda+1/p-1/2}$

with probability at least $1-2\exp(-Cn)$.

In fact, we shall prove a slightly more general result, Theorem C below, which
also yields new bounds on Gelfand numbers of diagonal operators in the quasi-
Banach regime (see Corollary 4 in the Appendix).

###  1.3 The power of random information for polynomial decay – discussion

In the following we discuss the consequences of our results for ellipsoids
with polynomially decaying semiaxes $\sigma_{j}=j^{-\lambda}$,
$j\in\mathbb{N}$, for some $\lambda>0$. It turns out that, at least when
$1\leq p\leq 2$, we can show a dichotomy for the radius of a random section in
comparison to the minimal section. Roughly speaking, we have the following
equivalence, which will be made precise by the conjecture at the end of this
subsection,

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\asymp\begin{cases}\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)&:\lambda>\frac{1}{p^{*}},\\\
\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},0)&:\lambda<\frac{1}{p^{*}}.\end{cases}$

To illustrate this, we first provide known results on the minimal radius
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)$, which we deduce from results on
Gelfand numbers of diagonal operators (see the Appendix for the latter).

Let $1\leq p\leq\infty$. The behavior of the minimal radius is known exactly
when $p\geq 2$ but can only be deduced up to subpolynomial factors when $1\leq
p<2$. To make this precise, we define the rate of polynomial decay (in $n$) of
an infinite array $a=(a_{n,m})_{m\in\mathbb{N},1\leq n<m}$ of real numbers by

$\mathrm{decay}(a):=\sup\\{\varrho\geq 0:\exists C\in(0,\infty)\text{ with
}a_{n,m}\leq Cn^{-\varrho}\text{ for all }m\in\mathbb{N}\text{ and }1\leq
n<m\\}.$

Now, let
$\frac{1}{s}:=(\frac{1}{2}-\frac{1}{p})_{+}:=\max\\{\frac{1}{2}-\frac{1}{p},0\\}$
and $\sigma_{j}=j^{-\lambda}$, $j\in\mathbb{N}$, for some
$\lambda>\frac{1}{s}$. The minimal radius does not decay if
$\lambda\leq\frac{1}{s}$. We have, see Corollary 5,

$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n))=\begin{cases}\lambda\cdot\frac{p^{*}}{2}&:\,1\leq
p<2\text{ and }\lambda<\frac{1}{p^{*}},\\\
\lambda+\frac{1}{p}-\frac{1}{2}&:\,\text{otherwise.}\end{cases}$ (3)

We can now compare this with our bounds on the radii of random sections.
Theorem A gives for the above choice of $\sigma$, for any
$\lambda>\frac{1}{p^{*}}$, $m\in\mathbb{N}$ and $1\leq n<m$,

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\lesssim_{p,\lambda}\begin{cases}n^{-\lambda-1/2}\sqrt{\log
n}:&p=1,\\\ n^{-\lambda+1/2-1/p}:&1<p\leq\infty,\end{cases}$ (4)

with probability $1-c_{1}\exp(-c_{2}n)$. This means, if $1\leq p\leq\infty$
and $\lambda>\frac{1}{p^{*}}$, then the polynomial decay rate of random
information is, by (3), equal to

$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))=\lambda+\frac{1}{p}-\frac{1}{2}=\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)).$
(5)

Similar to the above,
$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))$ is defined
to be the supremum over all $\varrho\geq 0$ such there exist
$C,C_{1},C_{2}\in(0,\infty)$ such that
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\leq Cn^{-\varrho}$ holds
with probability at least $1-C_{1}\exp(-C_{2}n)$ for all $m\in\mathbb{N}$ and
$1\leq n<m$. Thus, the bound of Theorem A on the decay rate is optimal for
$\lambda>\frac{1}{p^{*}}$. If $\lambda\leq\frac{1}{p^{*}}$, however, it does
not yield a useful result. Instead, we have a lower bound on the radius of
random information, Proposition 1 below, which shows that if $1<p\leq 2$ the
radius of random information does not decay if $m$ is large enough.

######  Proposition 1.

Let $1<p\leq 2$ and $\sigma_{j}=j^{-\lambda},j\in\mathbb{N}$, for some
$\lambda$ with $0<\lambda<\frac{1}{p^{*}}$. Then, for any
$\varepsilon\in(0,1),$ $n\in\mathbb{N}$ and $m>n$ large enough, we have

$\mathbb{P}\Big{[}\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\geq\frac{1}{2}\Big{]}\geq
1-\varepsilon.$

In other words, if $1<p\leq 2$ and the semiaxes decay too slowly compared to
$\frac{1}{p^{*}}$, random information is asymptotically as good as no
information at all.

######  Remark 3.

The boundary case $\lambda=\frac{1}{p^{*}}$ is not covered by Proposition 1.
However, its statement remains true if
$\sigma_{j}=j^{-1/p^{*}}a_{j},j\in\mathbb{N},$ with $a_{j}\to\infty$ as
$j\to\infty$. This can be deduced from Proposition 4 in Section 4, from which
Proposition 1 follows.

We obtain the following corollary on the polynomial decay.

######  Corollary 1.

Let $1\leq p\leq 2$ and $\sigma_{j}=j^{-\lambda},j\in\mathbb{N}$, for some
$\lambda$ with $0<\lambda<\frac{1}{p^{*}}$. Then

$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))=0.$

We visualize the
$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))$ for
$0<p,\lambda\leq\infty$ and $\sigma_{j}=j^{-\lambda},j\in\mathbb{N},$ in the
following diagram, where the horizontal-axis displays $\frac{1}{p}$ and the
vertical-axis $\lambda$.

$\frac{1}{2}$$1$$\lambda$$\frac{1}{2}$$1$$\frac{1}{p}$$p=1$$\lambda+\frac{1}{p}-\frac{1}{2}$$?$00

Above the line $\lambda=1-\frac{1}{p}$, where $1\leq p\leq\infty,$ we just
deduced that Theorem A yields that random information is optimal up to an
additional logarithmic factor if $p=1$. The decay rate is equal to
$\lambda+\frac{1}{p}-\frac{1}{2}$, see (5). As noted above, below and
including the line $\lambda=\frac{1}{2}-\frac{1}{p}$, where $2\leq
p\leq\infty,$ optimal information does not decay at all, in other words,
information is useless and does not help to recover vectors. Geometrically,
this corresponds to the fact that, no matter how large the codimension $n(<m)$
of a subspace is, the section with $\mathcal{E}_{p,\sigma}^{m}$ has a radius
bounded from below.

In the square, that is for $p\geq 2$ and $\lambda\leq\frac{1}{2}$, it follows
from Theorem 5 in [14] that, no matter how large we choose $n$, if $m$ is
large enough, then with high probability
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})$ is bounded below by a
constant. That is,
$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))=0$ and so
random information is useless. By Corollary 1 this also holds for the triangle
given by $1<p<2$ and $0<\lambda<1-\frac{1}{p}$.

Finally, on the right-hand side of the dashed line where $p=1$, that is, where
$0<p<1$, Theorem B provides an upper bound with decay rate
$\lambda+\frac{1}{p}-\frac{1}{2}$, which depends on $m$. We do not have a
corresponding lower bound for optimal information in this region.

We pose the following conjecture claiming that there is a threshold of decay
separating regimes of completely different behavior of random information.

######  Conjecture.

Let $1\leq p\leq\infty$ and $\sigma_{j}=j^{-\lambda},j\in\mathbb{N},$ with
$\lambda>\frac{1}{s}=(\frac{1}{2}-\frac{1}{p})_{+}$. Then,

$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))=\begin{cases}\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n))&:\lambda>\frac{1}{p^{*}},\\\
0&:\lambda\leq\frac{1}{p^{*}}.\end{cases}$

By the discussion prior to the conjecture, it is verified except for the two
cases

  1. 1.

$1<p<2$ and $\lambda=\frac{1}{p^{*}}$,

  2. 2.

$p>2$ and $\frac{1}{2}<\lambda\leq\frac{1}{p^{*}}$.

As a matter of fact, it seems reasonable to conjecture that
$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))=\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n))$
as long as $\|(\sigma_{j})_{j\in\mathbb{N}}\|_{p^{*}}<\infty$, while
$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m}))=0$ whenever
$\|(\sigma_{j})_{j\in\mathbb{N}}\|_{p^{*}}=\infty$. We leave this as an open
problem for future investigation.

### Organization of the paper

We end this section with an overview of the remainder of this article. The
proof of Theorem A is carried out in Section 2. Theorem B will be proved in
Section 3, which also contains the necessary background on sparse
approximation. Section 4 provides a proof of Proposition 1. Finally, in the
Appendix we present known results on the optimal radius
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)$ which are deduced via Gelfand
numbers of diagonal operators.

##  2 An upper bound via an $M^{*}$-estimate – the case $1\leq p\leq\infty$

In this section, we will prove Theorem A. Our approach is based on estimates
on the mean width of the intersection of the $\ell_{p}$-ellipsoid
$\mathcal{E}_{p,\sigma}^{m}$ with a Euclidean ball, which we obtain using
Gordon’s $M^{*}$-estimate.

###  2.1 An $M^{*}$-estimate for
$\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}$

Let $K\subset\mathbb{R}^{m}$ be a convex body and
$h_{K}:\mathbb{S}^{m-1}\to\mathbb{R}$, $u\mapsto\sup_{y\in K}\langle
u,y\rangle$ be its support function. The (half) mean width of $K$ is given by

$M^{*}(K):=\int_{\mathbb{S}^{m-1}}h_{K}(u)\,{\rm d}\sigma^{m-1}(u),$

where $\mathbb{S}^{m-1}:=\\{x\in\mathbb{R}^{m}:\left\|x\right\|_{2}=1\\}$ is
the Euclidean unit sphere and $\sigma^{m-1}$ the normalized surface measure on
it. Let $g_{1},g_{2},\ldots$ be independent standard Gaussian random
variables. Then it is known that the mean width can be expressed through the
expected supremum of a suitable Gaussian process (see, e.g., [1, Lemma
9.1.3]), namely,

$M^{*}(K)=\frac{1}{c_{m}}\mathbb{E}\sup_{t\in K}\sum_{j=1}^{m}t_{j}g_{j},$ (6)

where $c_{m}\asymp\sqrt{m}$. We shall use Gordon’s theorem on subspaces
escaping through a mesh [11] in the form stated in [1, Theorem 9.3.8] with
$\gamma=\frac{1}{2}$ there.

######  Proposition 2.

Let $K\subset\mathbb{R}^{m}$ be a convex body containing the origin in its
interior. For any $1\leq n<m$ there exists a subset of the Grassmannian
$\mathcal{G}_{m,m-n}$ with Haar measure at least
$1-\frac{7}{2}\exp(-\frac{1}{72}a_{n}^{2})$ such that for any subspace $E_{n}$
in this set and all $x\in K\cap E_{n}$ we have

$\left\|x\right\|_{2}\leq 2\frac{a_{m}}{a_{n}}M^{*}(K),$

where, for each $k\in\mathbb{N}$,

$a_{k}:=\mathbb{E}\Big{(}\sum_{j=1}^{k}g_{i}^{2}\Big{)}^{1/2}=\frac{\sqrt{2}\Gamma((k+1)/2)}{\Gamma(k/2)}\asymp\sqrt{k}.$
(7)

We first bound
$M^{*}(\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m})$, where
$\varrho>0$ will be chosen suitably later, and then apply Proposition 2 to
$\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}$ and translate the
result to our setting. First, we present an elementary estimate for
$\ell_{q}$-norms of structured Gaussian random vectors.

######  Lemma 1.

Let $k\in\mathbb{N}$ and $1\leq q<\infty$. If
$b=(b_{j})_{j=1}^{k}\in\mathbb{R}^{k}$ and $X=(b_{j}g_{j})_{j=1}^{k}$ with
independent standard Gaussian random variables $g_{1},\dots,g_{k}$, then

$\gamma_{1}\left\|b\right\|_{q}\leq\mathbb{E}\left\|X\right\|_{q}\leq\gamma_{q}\left\|b\right\|_{q},\quad\text{where
}\quad\gamma_{q}:=\big{(}\mathbb{E}\left|g_{1}\right|^{q}\big{)}^{1/q}\asymp\sqrt{q}.$

Further,

$\mathbb{E}\left\|X\right\|_{\infty}\asymp\sup_{1\leq j\leq
k}b_{j}^{*}\sqrt{\log(j)+1},$

where $(b_{j}^{*})_{j=1}^{k}$ is the non-increasing rearrangement of
$(|b_{j}|)_{j=1}^{k}$.

###### Proof.

For $1\leq q<\infty$ the upper bound follows from Jensen’s inequality and the
lower bound follows from
$\left\|\mathbb{E}X^{\prime}\right\|_{\ell_{q}^{k}}\leq\mathbb{E}\left\|X^{\prime}\right\|_{\ell_{q}^{k}}=\mathbb{E}\left\|X\right\|_{\ell_{q}^{k}}$,
where $X^{\prime}=(|b_{j}g_{j}|)_{j=1}^{k}$. The asymptotics for $q=\infty$
are taken from [31, Lemmas 2.3 and 2.4]. ∎

We will combine this with (6) to estimate the mean width of the intersection
as stated in the following proposition. A similar approach was used in [12]
for $\ell_{p}$-balls.

######  Proposition 3.

Let $m\in\mathbb{N}$. For any $0\leq k<m$ and $\varrho>0$,

$M^{*}(\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m})\lesssim\begin{cases}m^{-1/2}\Big{(}\varrho\sqrt{k}+\sup\limits_{k+1\leq
j\leq m}\sigma_{j}\sqrt{\log(j)+1}\Big{)}&:\,p=1,\\\
\sqrt{p^{*}}m^{-1/2}\Big{(}\varrho\sqrt{k}+\big{(}\sum\limits_{j=k+1}^{m}\sigma_{j}^{p^{*}}\big{)}^{1/p^{*}}\Big{)}&:\,1<p\leq\infty.\end{cases}$

###### Proof.

We shall use the representation (6) and first bound the supremum. For all
$x\in\mathbb{R}^{m}$ and
$y\in\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}$, it follows from
Hölder’s inequality that, for every $0\leq k<m$,

$\langle
x,y\rangle\leq\sum_{j=1}^{k}\left|x_{j}y_{j}\right|+\sum_{j=k+1}^{m}\left|x_{j}y_{j}\right|\leq\varrho\Big{(}\sum_{j=1}^{k}x_{j}^{2}\Big{)}^{1/2}+\Big{(}\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\left|x_{j}\right|^{p^{*}}\Big{)}^{1/p^{*}},$

where the first sum is empty if $k=0$. Combining this estimate with Lemma 1,
we obtain that if $p>1$,

$\displaystyle\mathbb{E}\sup_{y\in\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}}\sum_{j=1}^{m}y_{j}g_{j}\leq\varrho\,a_{k}+\gamma_{p^{*}}\Big{(}\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}}.$

By the previously stated asympotics for $a_{k}$ in (7) and $\gamma_{p^{*}}$ in
Lemma 1, we obtain the statement for $p>1$.

If $p=1$, then we deduce from Lemma 1 that, for some suitable
$C\in(0,\infty)$,

$\mathbb{E}\,\sup_{y\in\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}}\sum_{j=1}^{m}y_{j}g_{j}\leq\varrho\sqrt{k}+C\sup_{k+1\leq
j\leq m}\sigma_{j}\sqrt{\log(j)+1}.$

This completes the proof. ∎

###  2.2 The proof of Theorem A

With the $M^{*}$-estimates on rounded versions of our ellipsoids from the
previous subsection, we are now ready to prove the upper bound on the radius
of random information.

###### Proof of Theorem A.

It follows from Gordon’s $M^{*}$-estimate (Proposition 2) applied to the
convex body $\mathcal{E}_{p,\sigma}^{m}\cap\rho\mathbb{B}_{2}^{m}$ that, with
probability as claimed, a random subspace $E_{n}$ of codimension $n$ chosen
uniformly according to the Haar probability on $\mathcal{G}_{m,m-n}$ satisfies

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m},E_{n})=\sup_{x\in\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}\cap
E_{n}}\left\|x\right\|_{2}\leq
2\frac{a_{m}}{a_{n}}M^{*}(\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m}).$

We start with the case $p>1$. Inserting the bound obtained in Proposition 3,
we obtain a constant $C\in(0,\infty)$ such that, for any $0\leq k<m$ and
$1\leq n<m$,

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m},E_{n})\leq
C\frac{\sqrt{p^{*}}}{\sqrt{n}}\Big{(}\varrho\sqrt{k}+\Big{(}\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}}\Big{)}.$

First, let $\frac{n}{p^{*}}>4C^{2}$. Setting
$\varrho:=\frac{1}{\sqrt{k}}\Big{(}\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}}$
with $k:=c\frac{n}{p^{*}}$, where the constant $c\in(0,\infty)$ is chosen
(sufficiently small) such that $k\in\mathbb{N}$ with $1\leq k<m$ and

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m}\cap\varrho\mathbb{B}_{2}^{m},E_{n})<\varrho$

and so in particular that

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},E_{n})<\varrho$

for all $m\in\mathbb{N}$ and $1\leq n<m$. The latter is so because a set which
has circumradius smaller than $\varrho$ when intersected with
$\varrho\mathbb{B}_{2}^{m}$ must necessarily have itself circumradius smaller
than $\varrho$. Noting that the kernel of a Gaussian random matrix in
$\mathbb{R}^{n\times m}$ is uniformly distributed on the Grassmannian
$\mathcal{G}_{m,m-n}$ and that

$\varrho\lesssim\frac{\sqrt{p^{*}}}{\sqrt{n}}\Big{(}\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}},$

proves the result for $p>1$ in this case. If $\frac{n}{p^{*}}\leq 4C^{2}$,
then let $k=0$ and let $\varrho>0$ be large enough such that
$\mathcal{E}_{p,\sigma}^{m}\subset\varrho\mathbb{B}_{2}^{m}$ and thus

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},E_{n})\leq
C\frac{\sqrt{p^{*}}}{\sqrt{n}}\Big{(}\sum_{j=1}^{m}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}}.$

In both cases, $k+1\asymp\frac{n}{p^{*}}$. The proof for $p=1$ is carried out
analogously. ∎

We conclude this section by stating a bound on the supremum of a Gaussian
process indexed by vectors in an $\ell_{p}$-ellipsoid. The result can be read
off from the proof of Proposition 3. In view of the dependence on the
parameter $p$, it improves upon a bound of van Handel in [32].

######  Corollary 2.

For all $m\in\mathbb{N}$, we have

$\mathbb{E}\sup_{y\in\mathcal{E}_{p,\sigma}^{m}}\sum_{j=1}^{m}g_{j}y_{j}\lesssim\begin{cases}\sup\limits_{1\leq
j\leq m}\sigma_{j}\sqrt{\log(j)+1}&:\,p=1,\\\
\sqrt{p^{*}}\big{(}\sum\limits_{j=1}^{m}\sigma_{j}^{p^{*}}\big{)}^{1/p^{*}}&:\,1<p\leq\infty.\end{cases}$

In [32] van Handel deduced this result for $1\leq p<\infty$ with an
unspecified constant from the majorizing measure theorem and noted in [32,
Remark 3.4] that his approach is not sufficiently accurate to recover the
correct behavior in $p$. In Corollary 2, we obtain an upper bound on the
behavior in $p$ and thus complement his result.

Employing estimates for entropy numbers of diagonal operators (see, e.g.,
[32]), it can be deduced from Corollary 2 that the ellipsoid
$\mathcal{E}_{p,\sigma}^{m}$ with semiaxes satisfying

$\sigma\in\ell_{p^{*}}\text{ but }\sigma\not\in\ell_{p^{*},1}\text{ for
}1<p<\infty\quad\text{or}\quad\quad\sup_{j\in\mathbb{N}}\sigma_{j}\sqrt{\log(j)+1}<\infty\text{
but }\sigma\not\in\ell_{\infty,1}$

is an example, where Dudley’s bound fails to be sharp if the dimension becomes
large. Here, $\ell_{p,q}$ is a Lorentz space as defined in the Appendix.

##  3 An upper bound via compressed sensing techniques – the case $0<p<1$

In this section we prove Theorem B using techniques from compressed sensing in
the spirit of Foucart, Pajor, Rauhut and Ullrich [4] who have given upper and
lower bounds for the Gelfand widths of $\ell_{p}$-balls in $\ell_{q}$ with
$0<p\leq 1$ and $p<q\leq 2$. They build upon work by Donoho [3] and others.
Our proof is an extension to $\ell_{p}$-ellipsoids. Before we present it, we
shall explain some of the relevant concepts used in compressed sensing for the
recovery of sparse vectors. We refer the reader to the monograph [5] for more
information.

###  3.1 Elements from compressed sensing and bounds on the best $s$-term
approximation

Let $m,s\in\mathbb{N}$ with $1\leq s\leq m$ and let $0<p\leq 1$. A vector
$z\in\mathbb{R}^{m}$ is called $s$-sparse if at most $s$ of its coordinates
are non-zero. The error of best $s$-term approximation of $x\in\mathbb{R}^{m}$
in the $\ell_{p}$-(quasi-)norm is

$\sigma_{s}(x)_{p}:=\inf\\{\|x-z\|_{p}:z\text{ is }s\text{-sparse}\\}.$

Given the information $N_{n}x=y$, where $N_{n}\in\mathbb{R}^{n\times m}$,
sparse vectors can be reconstructed via $\ell_{p}$-minimization, that is,

$\Delta_{p}(y):=\text{arg min}\|z\|_{p}\quad\text{subject to }N_{n}z=y.$

Note that $\Delta_{p}$ is a mapping from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$
which depends on $N_{n}$. If the matrix $N_{n}$ satisfies the restricted
isometry property with a small restricted isometry constant
$\delta_{2s}(N_{n})$ of order $2s$, which is the smallest $\delta>0$ such that

$(1-\delta)\|x\|_{2}^{2}\leq\|Ax\|_{2}^{2}\leq(1+\delta)\|x\|_{2}^{2}\quad\text{for
all }2s\text{-sparse }x\in\mathbb{R}^{m},$

then $s$-sparse vectors $x\in\mathbb{R}^{m}$ can be recovered exactly, i.e.,
$x=\Delta_{p}(N_{n}x)$. It is widely known that Gaussian matrices satisfy this
with high probability. See, for example, Theorem 9.2 in [5], which we adapt in
the following lemma.

######  Lemma 2.

For every $\delta\in(0,1)$ there exist constants $C_{1},C_{2}>0$ such that
$\delta_{s}(n^{-1/2}G_{n,m})\leq\delta$ with probability at least
$1-2\exp(-C_{2}n)$ provided that $n\geq C_{1}s\log({\rm e}m/s)$ for
$m\in\mathbb{N}$.

We will prove a more general version of Theorem B, where $q$ will be allowed
to be smaller than $2$. To this end, we introduce a notation for the radius of
a section of $\mathcal{E}_{p,\sigma}^{m}$ measured in the
$\ell_{q}$-(quasi-)norm, $0<q\leq\infty$. Given any subspace $E_{n}$ of
$\mathbb{R}^{m}$ with codimension $n$, we define

$\mathrm{rad}_{q}(\mathcal{E}_{p,\sigma}^{m},E_{n}):=\sup_{x\in\mathcal{E}_{p,\sigma}^{m}\cap
E_{n}}\|x\|_{q}.$

The following extension of the equality (1) to the quasi-Banach space setting
will be useful. It is the analogue of [4, Proposition 1.2] for individual
matrices/subspaces. For convenience we provide a short proof.

######  Lemma 3.

Let $n,m\in\mathbb{N}$ and let $K\subset\mathbb{R}^{m}$ be such that $K=-K$
and $K+K\subset C_{K}K$ for some $C_{K}\geq 2$. Further, let $\|\cdot\|_{X}$
be a quasi-norm on $\mathbb{R}^{m}$ such that for some $C_{X}\in(0,\infty)$
and all $x,y\in\mathbb{R}^{m}$ we have $\|x+y\|_{X}\leq
C_{X}(\|x\|_{X}+\|y\|_{X})$. Then

$C_{X}^{-1}\,\mathrm{rad}_{X}(K,\ker N_{n})\leq\inf_{\varphi}\sup_{x\in
K}\|x-\varphi(N_{n}x)\|_{X}\leq C_{K}\,\mathrm{rad}_{X}(K,\ker N_{n})$

for all $N_{n}\in\mathbb{R}^{n\times m}$, where
$\mathrm{rad}_{X}(K,E):=\sup_{x\in K\cap E}\|x\|_{X}$ for any set
$E\subset\mathbb{R}^{m}$ and the infimum runs over all mappings
$\varphi\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ .

###### Proof.

For the lower bound take $\varphi$ arbitrary. For any $x\in K\cap\ker N_{n}$
also $-x\in K\cap\ker N_{n}$ and

$\|x-\varphi(0)\|_{X}\geq C_{X}^{-1}\|x\|_{X}\quad\text{ or
}\quad\|-x-\varphi(0)\|_{X}\geq C_{X}^{-1}\|x\|_{X}$ (8)

holds. Moreover, the symmetry of $K\cap\ker N_{n}$ implies

$\sup_{x\in K}\|x-\varphi(N_{n}x)\|_{X}\geq\sup_{x\in K\cap\ker
N_{n}}\max\\{\|x-\varphi(0)\|_{X},\|-x-\varphi(0)\|_{X}\\}.$

Together with (8) this proves the lower bound.

For the upper bound we specify a map $\varphi$ by $\varphi(y)=z$ for any $y\in
N_{n}(K)$, where $z\in K$ with $N_{n}z=y$ is arbitrary. Then

$\sup_{x\in
K}\|x-\varphi(N_{n}x)\|_{X}\leq\sup_{\begin{subarray}{c}x_{1},x_{2}\in K\\\
N_{n}x_{1}=N_{n}x_{2}\end{subarray}}\|x_{1}-x_{2}\|_{X}\leq\sup_{x\in
C_{K}K\cap\ker N_{n}}\|x\|_{X}$

since $x_{1}-x_{2}\in C_{K}K$ if $x_{1},x_{2}\in K$ and $N_{n}(x_{1}-x_{2})=0$
if $N_{n}x_{1}=N_{n}x_{2}$. The fact that $C_{K}\,\mathrm{rad}_{X}(K,\ker
N_{n})=\mathrm{rad}_{X}(C_{K}\,K,\ker N_{n})$ concludes the proof. ∎

We will use this together with the following lemma on best sparse
approximation of vectors in an $\ell_{p}$-ellipsoid. For
$\ell_{q}$-approximation of vectors in $\ell_{p}$-balls by sparse vectors it
is known that, for $0<p\leq q\leq\infty$,

$\sup_{x\in\mathbb{B}_{p}^{m}}\sigma_{s}(x)_{q}\asymp_{p}s^{1/q-1/p}$

for all $m\in\mathbb{N}$ and $1\leq s\leq m$ (see, e.g., [33]). If $p=q$, the
approximation error cannot be expected to decay, whereas for
$\ell_{p}$-ellipsoids we have the following lemma for the special case of
polynomially decaying $\sigma$. The proof is an adaption of the proof for
$\ell_{p}$-balls.

######  Lemma 4.

Let $m\in\mathbb{N}$, $0<p\leq\infty$ and $\sigma_{j}=j^{-\lambda}$, $1\leq
j\leq m$, for some $\lambda>0$. Then, for all $1\leq s\leq m/2$,

$\sup_{x\in\mathcal{E}_{p,\sigma}^{m}}\sigma_{s}(x)_{p}\asymp_{p,\lambda}s^{-\lambda}$

###### Proof.

Let $x\in\mathcal{E}_{p,\sigma}^{m}$. Then

$\sigma_{s}(x)_{p}\leq\Big{(}\sum_{j=s+1}^{m}(x_{j}^{*})^{p}\Big{)}^{1/p},$

where $(x_{j}^{*})_{j=1}^{m}$ is the non-increasing rearrangement of the
moduli of the coordinates of $x$. We have

$1\geq\sum_{j=1}^{m}\frac{|x_{j}|^{p}}{\sigma_{j}^{p}}=\sum_{j=1}^{m}\frac{(x_{j}^{*})^{p}}{\sigma_{\pi(j)}^{p}}\geq\sum_{j=1}^{k}\frac{(x_{k}^{*})^{p}}{\sigma_{\pi(j)}^{p}},$

for any $1\leq k\leq m$, where $\pi:\\{1,\ldots,m\\}\to\\{1,\ldots,m\\}$ is a
suitable permutation. Thus,

$(x_{k}^{*})^{p}\leq\Big{(}\sum_{j=1}^{k}\frac{1}{\sigma_{\pi(j)}^{p}}\Big{)}^{-1}\leq\Big{(}\sum_{j=1}^{k}\frac{1}{\sigma_{j}^{p}}\Big{)}^{-1}\asymp_{p,\lambda}k^{-\lambda
p-1}.$

Inserting this bound above yields

$\sigma_{s}(x)_{p}\lesssim_{p,\lambda}\Big{(}\sum_{j=s+1}^{m}k^{-\lambda
p-1}\Big{)}^{1/p}\asymp_{p,\lambda}s^{-\lambda}.$

The lower bound is achieved by a vector on the boundary of
$\mathcal{E}_{p,\sigma}^{m}$ having its support on the first $2s$ coordinates
and equal entries on these. ∎

###  3.2 The proof of Theorem B

With the results of the previous subsection at our disposal, we are now
prepared to prove the following generalization of Theorem B.

######  Theorem C.

Let $0<p\leq 1$ and $p<q\leq 2$. Assume that $\sigma_{j}=j^{-\lambda}$,
$j\in\mathbb{N}$, for some $\lambda>0$. Then there exist constants
$C,D\in(0,\infty)$ such that, for all $m\in\mathbb{N}$ and all $1\leq n<m$
with

$n\geq D\log({\rm e}m/n),$

we have

$\mathrm{rad}_{q}(\mathcal{E}_{p,\sigma}^{m},\ker
G_{n,m})\lesssim_{p,q}\Big{(}\frac{\log({\rm
e}m/n)}{n}\Big{)}^{\lambda+1/p-1/q}$

with probability at least $1-2\exp(-Cn)$.

###### Proof.

Let $m\in\mathbb{N}$, $1\leq n<m$ and $N_{n}:=n^{-1/2}G_{n,m}$. By Lemma 3,
for all realizations,

$\mathrm{rad}_{q}(\mathcal{E}_{p,\sigma}^{m},\ker G_{n,m})\leq
2^{1/q}\sup_{x\in\mathcal{E}_{p,\sigma}^{m}}\|x-\Delta_{p}(N_{n}x)\|_{q},$ (9)

where we specified $\varphi(y)=\Delta_{p}(n^{-1/2}y)=$ arg min $\|z\|_{p}$
subject to $N_{n}z=n^{-1/2}y$ for $y=G_{n,m}x$.

We follow the proof of [4, Theorem 3.2] in order to obtain an upper bound. To
this end, let $D\in(0,\infty)$ be large enough such that

$D/2>{\rm e}\quad\text{and}\quad\frac{D/2}{1+\log(D/2)}>C_{1},$

where $C_{1}\in(0,\infty)$ is the constant from Lemma 2 with $\delta=1/3$.
Also choose $s:=\lfloor n/D\log({\rm e}m/n)\rfloor$. Then, if $n\geq
D\log({\rm e}m/n)$ it holds that $n>C_{1}(2s)\log({\rm e}m/2s)$. By Lemma 2
the matrix $N_{n}$ satisfies $\delta_{2s}(N_{n})\leq 1/3$ with probability at
least $1-2\exp(-C_{2}n)$. It follows, see (3.5) and (3.6) in [4], that there
exists a constant $C\in(0,\infty)$ such that with the same probability,

$\sup_{x\in\mathcal{E}_{p,\sigma}^{m}}\|x-\Delta_{p}(N_{n}x)\|_{q}\leq
C\Big{(}\frac{\log({\rm
e}m/n)}{n}\Big{)}^{1/p-1/q}\sup_{x\in\mathcal{E}_{p,\sigma}^{m}}\sigma_{s}(x)_{p}.$

With Lemma 4 the proof is complete if we can show that $s\leq m/2$. Indeed,
since the function $n\mapsto n/\log({\rm e}m/n)$ is increasing for $1\leq
n\leq m$, we have $s\leq m/D<m/2{\rm e}$.

∎

If $n$ is too small for Theorem C to apply, that is, $n<D\log({\rm e}m/n)$, we
only have the trivial pointwise bound

$\mathrm{rad}_{q}(\mathcal{E}_{p,\sigma}^{m},\ker
G_{n,m})\leq\mathrm{rad}_{q}(\mathcal{E}_{p,\sigma}^{m},\mathbb{R}^{m})\leq\sigma_{1}$

by means of $\|\cdot\|_{q}\leq\|\cdot\|_{p}$.

######  Remark 4.

Let us note that the proof does not work in the case where $p>1$ as can
already be seen in [4, Theorem 3.2]. Moreover, in the case $p=1$ the bound
derived from Theorem C is worse than the bound given by Theorem A already for
$m\gtrsim n^{2}$, i.e., for small codimension. Nonetheless, if $m$ is
proportional to $n$, the bound from Theorem C improves upon (4) obtained from
Theorem A.

######  Remark 5.

Theorem C provides a bound on Gelfand numbers of diagonal operators in the
quasi-Banach regime, see Corollary 4 in the Appendix.

##  4 A lower bound – the case $1<p\leq 2$

We use the following lemma from [14, Lemma 25] to prove the lower bound of
Proposition 1 for slowly decaying semiaxes in the case of $1<p\leq 2$.

######  Lemma 5.

For any $\varepsilon\in(0,1)$ it holds that, for all $m\in\mathbb{N}$ and
$1\leq n<m$,

$\mathbb{P}\Big{[}\sup\big{\\{}x_{1}^{2}:\left\|x\right\|_{2}=1,G_{n,m}x=0\big{\\}}\geq
1-\frac{n}{\varepsilon m}\Big{]}\geq 1-\varepsilon.$

From this we can now deduce the lower bound as presented in Proposition 1. We
prove a slightly more general bound holding not just for polynomially decaying
semiaxes. Plugging in semiaxes of polynomial decay then proves Proposition 1.

######  Proposition 4.

Let $1<p\leq 2$. Then, for any $\varepsilon\in(0,1)$ and all $m\in\mathbb{N}$
and $1\leq n<m$ with $n\leq\varepsilon\sigma_{m}^{2}m^{2/p^{*}}$, we have

$\mathbb{P}\Big{[}\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},G_{n,m})\geq\frac{\sigma_{1}}{1+\sigma_{1}}\Big{]}\geq
1-\varepsilon.$

###### Proof.

By Lemma 5, with probability at least $1-\varepsilon$, we find
$x\in\mathbb{R}^{m}$ with

$x_{1}^{2}\geq 1-\frac{n}{\varepsilon
m},\quad\left\|x\right\|_{2}=1,\quad\text{and}\quad G_{n,m}x=0.$

We estimate

$\Big{(}\sum_{j=1}^{m}\frac{\left|x_{j}\right|^{p}}{\sigma_{j}^{p}}\Big{)}^{1/p}\leq\frac{1}{\sigma_{1}}+\Big{(}\sum_{j=2}^{m}\frac{\left|x_{j}\right|^{p}}{\sigma_{j}^{p}}\Big{)}^{1/p}\leq\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{m}}\Big{(}\sum_{j=2}^{m}\left|x_{j}\right|^{p}\Big{)}^{1/p}$

and by means of Hölder’s inequality, we obtain

$\frac{1}{\sigma_{m}}\Big{(}\sum_{j=2}^{m}\left|x_{j}\right|^{p}\Big{)}^{1/p}\leq\frac{m^{1/p-1/2}}{\sigma_{m}}\Big{(}\sum_{j=2}^{m}x_{j}^{2}\Big{)}^{1/2}=\frac{m^{1/p-1/2}}{\sigma_{m}}\big{(}1-x_{1}^{2}\big{)}^{1/2}.$

Since $1-x_{1}^{2}\leq\frac{n}{\varepsilon m}$, we have

$\Big{(}\sum_{j=1}^{m}\frac{\left|x_{j}\right|^{p}}{\sigma_{j}^{p}}\Big{)}^{1/p}\leq\frac{1}{\sigma_{1}}+1$

if $n\leq\varepsilon m^{2p^{*}}\sigma_{m}^{2}$. In this case, we can normalize
such that $\tilde{x}:=x/(1+\frac{1}{\sigma_{1}})$ satisfies

$\tilde{x}\in\mathcal{E}_{p,\sigma}^{m},\quad
G_{n,m}\tilde{x}=0,\quad\text{and}\quad\left\|\tilde{x}\right\|_{2}=\frac{\sigma_{1}}{1+\sigma_{1}},$

which completes the proof. ∎

## Appendix – Gelfand numbers of diagonal operators, optimal radius, and
polynomial semiaxes

Let $0<p\leq\infty$. We write $\ell_{p}$ for the space of $p$-summable
sequences and denote its (quasi-)norm by $\|\cdot\|_{p}$. For
$0<p,t\leq\infty$, we define a Lorentz (quasi-)norm by

$\left\|x\right\|_{p,t}:=\left\|j^{1/p-1/t}x_{j}^{*}\right\|_{t},$

where $(x_{j}^{*})_{j\in\mathbb{N}}$ is the non-increasing rearrangement of
$(\left|x_{j}\right|)_{j\in\mathbb{N}}$ with the convention that
$1/\infty:=0$. We write $\ell_{p,t}$ for the space of sequences with finite
Lorentz (quasi-)norm $\|\cdot\|_{p,t}$. Note that $\ell_{p,p}=\ell_{p}$ and
$\ell_{p,t}\subset\ell_{r,t}$ for every $0<p<r\leq\infty$.

Let $0<q\leq\infty$ and $\sigma=(\sigma_{j})_{j\in\mathbb{N}}$ be a non-
increasing non-negative sequence, i.e.,
$\sigma_{1}\geq\sigma_{2}\geq\cdots\geq 0$. To $\sigma$ we can associate the
diagonal operator

$D_{\sigma}\colon\ell_{p}\to\ell_{q},\quad
x=(x_{j})_{j\in\mathbb{N}}\mapsto(\sigma_{j}x_{j})_{j\in\mathbb{N}},$

which, for any $m\in\mathbb{N}$, can be considered as an operator from
$\ell_{p}^{m}$ to $\ell_{q}^{m}$. Then the image
$D_{\sigma}(\mathbb{B}_{p}^{m})=\mathcal{E}_{p,\sigma}^{m}$ is an
$\ell_{p}$-ellipsoid.

Let $1\leq n<m$ and consider an information mapping
$N_{n}\in\mathbb{R}^{n\times m}$ with kernel $E_{n}$. A change of variables
shows that

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},N_{n})=\sup_{x\in\mathbb{B}_{p}^{m}\cap\ker
N_{n}}\left\|D_{\sigma}x\right\|_{2}.$

We have that

$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)=c_{n+1}(D_{\sigma}:\ell_{p}^{m}\to\ell_{2}^{m})\quad\text{for
all }n\in\mathbb{N},$ (10)

where

$c_{n+1}(D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m}):=\inf_{E_{n}}\sup_{x\in\mathbb{B}_{p}^{m}\cap
E_{n}}\left\|D_{\sigma}x\right\|_{q}$

is the $(n+1)$-st Gelfand number of $D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m}$.
Here, the infimum ranges over all subspaces of $\mathbb{R}^{m}$ with
codimension at most $n$. For general background on Gelfand numbers and other
$s$-numbers, we refer the reader to [19] and [27].

Although we will need only the case $q=2$, it is natural to state the
following result in a more general form, which can be found in [27, Section
11.11] for $q\geq 1$ but the proof is in fact also valid for all $q>0$.

######  Proposition 5.

Let $0<q\leq p\leq\infty$ and $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq 0$.
Then, for any $1\leq n\leq m$, we have

$c_{n}(D_{\sigma}\colon\ell_{p}^{m}\to\ell_{q}^{m})=\Big{(}\sum_{j=n}^{m}\sigma_{j}^{r}\Big{)}^{1/r},$

where $\frac{1}{r}=\frac{1}{q}-\frac{1}{p}$ if $q<p$ and $r=\infty$ if $q=p$.

In addition to Proposition 5, we have for all $0<p,q\leq\infty$ that

$c_{1}(D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m})=\left\|D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m}\right\|=\Big{(}\sum_{j=1}^{m}\sigma_{j}^{r}\Big{)}^{1/r},$

where $\frac{1}{r}=(\frac{1}{q}-\frac{1}{p})_{+}$. This shows that
$\left\|\sigma\right\|_{r}<\infty$ is necessary to ensure that the operators
$D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m},m\in\mathbb{N},$ are uniformly
bounded. All of the above extends to the infinite-dimensional case in a
canonical way. We state a result taken from Buchmann [2], where one
implication goes back to Linde [21, Theorem 5].

######  Proposition 6.

Let $1\leq p,q\leq\infty$ and $r>0$ with
$\frac{1}{r}>(\frac{1}{q}-\frac{1}{p})_{+}$ as well as $0<t\leq\infty$. Then

$\sigma\in\ell_{r,t}\quad\Leftrightarrow\quad\big{(}c_{n}(D_{\sigma}:\ell_{p}\to\ell_{q})\big{)}_{n\in\mathbb{N}}\in\ell_{u,t},$

where

  1. 1.

if $1\leq q\leq p\leq\infty$, then
$\frac{1}{u}=\frac{1}{r}+\frac{1}{p}-\frac{1}{q}$,

  2. 2.

if $1\leq p<q\leq 2$, then
$\frac{1}{u}=\begin{cases}\frac{p^{*}}{2r}&:\frac{1}{r}<\frac{1}{p^{*}}\frac{1/p-1/q}{1/p-1/2},\\\
\frac{1}{r}+\frac{1}{p}-\frac{1}{q}&:\frac{1}{r}>\frac{1}{p^{*}}\frac{1/p-1/q}{1/p-1/2},\end{cases}$

  3. 3.

if $1\leq p<2<q\leq\infty$, then
$\frac{1}{u}=\begin{cases}\frac{p^{*}}{2r}&:\frac{1}{r}<\frac{1}{p^{*}},\\\
\frac{1}{r}+\frac{1}{p}-\frac{1}{q}&:\frac{1}{r}>\frac{1}{p^{*}},\end{cases}$

  4. 4.

if $2\leq p<q\leq\infty$, then $\frac{1}{u}=\frac{1}{r}$.

By means of (10), Propositions 5 and 6 apply to the radius of optimal
information. Note that some cases are missing, for example if $q=2$, there is
a gap for $\frac{1}{r}=\frac{1}{p^{*}}$. In this case, we can deduce from an
infinite-dimensional version of Theorem A the following corollary.

######  Corollary 3.

For all $n\in\mathbb{N}$,

$c_{n}(D_{\sigma}:\ell_{p}\to\ell_{2})\lesssim\begin{cases}n^{-1/2}\sup\limits_{k\leq
j\leq\infty}\sigma_{j}\sqrt{\log(j)+1}&:\,p=1\\\
\sqrt{p^{*}}n^{-1/2}\Big{(}\sum\limits_{j=k}^{\infty}\sigma_{j}^{p^{*}}\Big{)}^{1/p^{*}}&:\,1<p\leq\infty,\end{cases}$

where $k\asymp\frac{n}{p^{*}}$ for $p>1$, while $k\asymp n$ for $p=1$. In
particular, $c_{n}(D_{\sigma}:\ell_{p}\to\ell_{2})\in\ell_{2,\infty}$ if
$1<p\leq\infty$ and $\sigma\in\ell_{p^{*}}$.

###### Proof.

We use (10) to state Theorem A for Gelfand numbers. Then, for each
$m\in\mathbb{N}$, let $D_{\sigma}^{m}$ be the restriction of the operator
$D_{\sigma}$ to the first $m$ coordinates. This gives

$c_{n}(D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m})=c_{n}(D_{\sigma}^{m}:\ell_{p}\to\ell_{q}),$

and further, by continuity and Hölder’s inequality,

$|c_{n}(D_{\sigma}^{m}:\ell_{p}\to\ell_{q})-c_{n}(D_{\sigma}:\ell_{p}\to\ell_{q})|\leq\Big{(}\sum_{j=m+1}^{\infty}\sigma_{j}^{s}\Big{)}^{1/s},$

with $\frac{1}{s}=(\frac{1}{2}-\frac{1}{p})_{+}$. Letting $m\to\infty$ for
each $n\in\mathbb{N}$ completes the proof. ∎

Let us note that bounding the Gelfand numbers of operators into $\ell_{2}$ via
$M^{*}$-estimates has been done before, e.g., in [26].

To the best of our knowledge, for $0<p<1$ or $0<q<1$ the asymptotic behavior
of Gelfand numbers of diagonal operators is unknown. At least for the case of
polynomial sequences, we can deduce the following result from Theorem C and
the analogue of (10) for $0<q<2$.

######  Corollary 4.

Let $0<p\leq 1$ and $p<q\leq 2$. Assume that $\sigma_{j}=j^{-\lambda}$,
$j\in\mathbb{N}$, for some $\lambda>0$. Then there exist constants
$C,D\in(0,\infty)$ such that, for all $m\in\mathbb{N}$ and all $1\leq n<m$
with

$n\geq D\log({\rm e}m/n),$

we have

$c_{n}(D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m})\lesssim_{p,q}\Big{(}\frac{\log({\rm
e}m/n)}{n}\Big{)}^{\lambda+1/p-1/q}.$

To study the decay of Gelfand numbers of diagonal operators arising from a
polynomially decaying sequence, the concept of a diagonal limit order has been
introduced by Pietsch (see, e.g., [28, 6.2.5.3]). The definition of decay
given in Section 1.3 is basically a finite-dimensional analogue of it. As a
corollary to Proposition 6, we have the following result.

######  Corollary 5.

Let $1\leq p\leq\infty$. If $\sigma_{j}=j^{-\lambda}$, $j\in\mathbb{N}$, for
some $\lambda>(\frac{1}{2}-\frac{1}{p})_{+}$, then

$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n))=\begin{cases}\lambda\cdot\frac{p^{*}}{2}&:\,1\leq
p<2\text{ and }\lambda<\frac{1}{p^{*}},\\\
\lambda+\frac{1}{p}-\frac{1}{2}&:\,\text{otherwise.}\end{cases}$

For $p\geq 2$ this also follows from Proposition 5 showing that
$\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n)\lesssim_{p,\lambda}n^{-\lambda+1/2-1/p}$
for all $m>n$ with a matching lower bound for $m$, say, larger than $2n$.

###### Proof.

We only prove the first case since the other case is analogous. To show that
$\mathrm{decay}(\mathrm{rad}(\mathcal{E}_{p,\sigma}^{m},n))\geq\lambda
p^{*}/2$, it is sufficient by (10) to find $C\in(0,\infty)$ such that, for all
$\varrho<\lambda p^{*}/2$ large enough,

$c_{n,m}:=c_{n}(D_{\sigma}:\ell_{p}^{m}\to\ell_{q}^{m})\leq
Cn^{-\varrho}\quad\text{for all }m\in\mathbb{N}\text{ and }1\leq n\leq m.$
(11)

This is satisfied if the sequence of Gelfand numbers
$c_{n}(D_{\sigma}:\ell_{p}\to\ell_{q})\geq c_{n,m}$ ($n\in\mathbb{N}$) belongs
to $\ell_{u,\infty}$ with $u=1/\varrho$. By Proposition 6, this holds if
$\sigma\in\ell_{r,\infty}$ with a certain $r>1/\lambda$, which is true by
assumption.

For the other inequality we assume that (11) holds for some $\varrho>\lambda
p^{*}/2$. Choosing $m$ large enough compared to $n$, see the proof of
Corollary 3, we deduce from (11) that for some $\varrho>\lambda p^{*}/2$ and
every $n\in\mathbb{N}$,

$c_{n}:=c_{n}(D_{\sigma}:\ell_{p}\to\ell_{q})\leq 2Cn^{-\varrho}.$ (12)

For every $r<1/\lambda$ and $0<t<\infty$, it follows from
$\sigma\not\in\ell_{r,t}$ and Proposition 6 that

$\sum_{n=1}^{\infty}\frac{1}{n}c_{n}^{t}n^{tp^{*}/2r}=\infty,$

which implies $c_{n}n^{p^{*}/2r}\log^{2/t}n\to\infty$, contradicting (12). ∎

### Acknowledgement

AH and MS were supported by the Austrian Science Fund (FWF) through project
F5513-N26, which is part of the Special Research Program _Quasi-Monte Carlo
Methods: Theory and Applications_. This research was funded in whole, or in
part, by the Austrian Science Fund (FWF), Project P34808. JP is supported by
the Austrian Science Fund (FWF) Project P32405 Asymptotic Geometric Analysis
and Applications. For the purpose of open access, the authors have applied a
CC BY public copyright license to any Author Accepted Manuscript arising from
this submission.

## References

  * [1] S. Artstein-Avidan, A. Giannopoulos, and V. D. Milman.  Asymptotic geometric analysis. Part I, volume 202 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2015.
  * [2] N. Buchmann.  Fehlerabschätzungen von Näherungslösungen unendlicher Glei-chungssysteme durch Gelfandzahlen von Tensorproduktoperatoren.  PhD thesis, Carl-von-Ossietzky-Universität Oldenburg, 1999.
  * [3] D. L. Donoho.  Compressed sensing.  IEEE Trans. Inform. Theory, 52(4):1289–1306, 2006.
  * [4] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich.  The Gelfand widths of $\ell_{p}$-balls for $0<p\leq 1$.  J. Complexity, 26(6):629–640, 2010.
  * [5] S. Foucart and H. Rauhut.  A mathematical introduction to compressive sensing.  Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013.
  * [6] A. Y. Garnaev and E. D. Gluskin.  The widths of a Euclidean ball.  Soviet Math. Dokl., 30:200–204, 1984.
  * [7] A. A. Giannopoulos and V. D. Milman.  On the diameter of proportional sections of a symmetric convex body.  Internat. Math. Res. Notices, (1):5–19, 1997.
  * [8] A. A. Giannopoulos and V. D. Milman.  Mean width and diameter of proportional sections of a symmetric convex body.  J. Reine Angew. Math., 497:113–139, 1998.
  * [9] E. D. Gluskin.  On some finite-dimensional problems of width theory.  Physis—Riv. Internaz. Storia Sci., 23(2):5–10, 124, 1981.
  * [10] E. D. Gluskin.  Norms of random matrices and diameters of finite-dimensional sets.  Mat. Sb. (N.S.), 120(162)(2):180–189, 286, 1983.
  * [11] Y. Gordon.  On Milman’s inequality and random subspaces which escape through a mesh in ${\bf R}^{n}$.  In Geometric aspects of functional analysis (1986/87), volume 1317 of Lecture Notes in Math., pages 84–106. Springer, Berlin, 1988.
  * [12] Y. Gordon, A. E. Litvak, S. Mendelson, and A. Pajor.  Gaussian averages of interpolated bodies and applications to approximate reconstruction.  J. Approx. Theory, 149(1):59–73, 2007.
  * [13] 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, pages 43–64. De Gruyter, Berlin/Boston, 1994.
  * [14] A. Hinrichs, D. Krieg, E. Novak, J. Prochno, and M. Ullrich.  Random sections of ellipsoids and the power of random information.  Trans. Amer. Math. Soc. (to appear), 2021.
  * [15] R. S. Ismagilov.  Widths of sets in normed linear spaces and approximation of functions by trigonometric polynomials.  Uspekhi Mat. Nauk, 29(3):161–178, 1974.
  * [16] M. Juhos and J. Prochno.  Spectral flatness and the volume of intersections of $p$-ellipsoids.  arXiv e-prints, page arXiv:2107.01097, July 2021.
  * [17] B. S. Kashin.  On Kolmogorov widths of octahedra.  Dokl. Akad. Nauk SSSR, 214:1024–1026, 1974.
  * [18] B. S. Kashin.  Widths of some finite-dimensional sets and classes of smooth functions.  Izv. Akad. Nauk SSSR Ser. Mat., 41:334–351, 1977.
  * [19] H. König.  Eigenvalue distribution of compact operators, volume 16 of Operator Theory: Advances and Applications.  Birkhäuser Verlag, Basel, 1986.
  * [20] N. M. Korobov.  Approximate calculation of repeated integrals by number-theoretical methods.  Dokl. Akad. Nauk SSSR (N.S.), 115:1062–1065, 1957.
  * [21] R. Linde.  $s$-numbers of diagonal operators and Besov embeddings.  In Z. Frolík, V. Souček, and J. Vinárek, editors, Proceedings of the 13th winter school on abstract analysis, number 10, pages 83–110, 1985.
  * [22] A. E. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  Diameters of sections and coverings of convex bodies.  J. Funct. Anal., 231(2):438–457, 2006.
  * [23] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann.  Reconstruction and subgaussian operators in asymptotic geometric analysis.  Geom. Funct. Anal., 17(4):1248–1282, 2007.
  * [24] M. Mohri, A. Rostamizadeh, and A. Talwalkar.  Foundations of machine learning.  Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2012\.
  * [25] E. Novak and H. Woźniakowski.  Tractability of multivariate problems. Vol. 1: Linear information, volume 6 of EMS Tracts in Mathematics.  European Mathematical Society (EMS), Zürich, 2008.
  * [26] A. Pajor and N. Tomczak-Jaegermann.  Subspaces of small codimension of finite-dimensional Banach spaces.  Proc. Amer. Math. Soc., 97(4):637–642, 1986.
  * [27] A. Pietsch.  Operator ideals, volume 20 of North-Holland Mathematical Library.  North-Holland Publishing Co., Amsterdam-New York, 1980.
  * [28] A. Pietsch.  History of Banach spaces and linear operators.  Birkhäuser Boston, Inc., Boston, MA, 2007.
  * [29] S. B. Stechkin.  On the best approximation of given classes of functions by arbitrary polynomials.  Uspekhi Math. Nauk., (9):133–134, 1954.
  * [30] M. I. Stesin.  Aleksandrov widths of finite dimensional set and of classes of smooth functions.  Dokl. Akad. Nauk USSR, (220):1278–1281, 1975.
  * [31] R. van Handel.  On the spectral norm of Gaussian random matrices.  Trans. Amer. Math. Soc., 369(11):8161–8178, 2017.
  * [32] R. van Handel.  Chaining, interpolation, and convexity.  J. Eur. Math. Soc. (JEMS), 20(10):2413–2435, 2018.
  * [33] J. Vybíral.  Average best $m$-term approximation.  Constr. Approx., 36(1):83–115, 2012.