The power of random information for numerical approximation

and integration

Dipl.-Ing. Mathias Sonnleitner

A dissertation submitted to the
faculty of computer science and mathematics
in partial fulfillment of the requirements for the degree of
doctor of natural sciences

Advisors:     Prof. Dr. Joscha Prochno

Univ.-Prof. Dr. Aicke Hinrichs

Reviewers:     Prof. Dr. Joscha Prochno

Univ.-Prof. Dr. Aicke Hinrichs

Prof. Dr. Alexander Litvak

Date of oral exam:     2022-05-18

This thesis investigates the quality of randomly collected data by employing a framework built on information-based complexity, a field related to the numerical analysis of abstract problems. The quality or power of gathered information is measured by its radius which is the uniform error obtainable by the best possible algorithm using it. The main aim is to present progress towards understanding the power of random information for approximation and integration problems.

In the first problem considered, information given by linear functionals is used to recover vectors, in particular from generalized ellipsoids. This is related to the approximation of diagonal operators which are important objects of study in the theory of function spaces. We obtain upper bounds on the radius of random information both in a convex and a quasi-normed setting, which extend and, in some cases, improve  existing results. We conjecture and partially establish that the power of random information is subject to a dichotomy determined by the decay of the length of the semiaxes of the generalized ellipsoid.

Second, we study multivariate approximation and integration using information given by function values at sampling point sets. We obtain an asymptotic characterization of the radius of information in terms of a geometric measure of equidistribution, the distortion, which is well known in the theory of quantization of measures. This holds for isotropic Sobolev as well as Hölder and Triebel-Lizorkin spaces on bounded convex domains. We obtain that for these spaces, depending on the parameters involved, typical point sets are either asymptotically optimal or worse by a logarithmic factor, again extending and improving existing results.

Further, we study isotropic discrepancy which is related to numerical integration using linear algorithms with equal weights. In particular, we analyze the quality of lattice point sets with respect to this criterion and obtain that they are suboptimal compared to uniform random points. This is in contrast to the approximation of Sobolev functions and resolves an open question raised in the context of a possible low discrepancy construction on the two-dimensional sphere.

At this point, I want to acknowledge that this work would not have been created without the support of several important people.

First, I want to express my gratitude to my supervisors Aicke Hinrichs and Joscha Prochno who provided me with the opportunity to conduct my own research and supported me in the process.

This thesis relies on joint publications with kind colleagues. In addition to my supervisors, these are David Krieg, with whom I exchanged innummerable e-mails about our joint projects and whose comments improved the presentation of our joint work in this thesis, and  Friedrich Pillichshammer, who guided me during my first publication.

Special thanks go to Mario Ullrich, who served as a mentor during my time in Linz, for many (non-)mathematical discussions and helpful advice.

I was fortunate to have met many people during my studies, especially at the Institute of Analysis and the neighboring Institute of Financial Mathematics and Applied Number Theory at Johannes Kepler University (JKU) Linz and the Institute of Mathematics and Computer Science at the University of Graz. The conversations with them enriched my life and made it easy to take short (and also longer) breaks from mathematics.

Even more so, I am glad to have friends who provided most welcome distraction from symbols and formulas.

Many of my teachers deserve my gratitude for increasing my joy in learning which made composing this thesis an overall satisfying experience.

Finally, let me state the obvious fact that I would not exist without my parents. They provided me with much more than mere existence and I want to thank them for their unfailing support. Returning home always has been a source of strength because of them and my brother.

The support by the Austrian Science Fund (FWF) through the project grants FF5513-N26, which is part of the Special Research Program “ Quasi-Monte Carlo Methods: Theory and Applications”, P32405 “Asymptotic geometric analysis and applications”, and P34808 “Information-Based Complexity: Beyond the standard settings” is gratefully acknowledged.

CHAPTER: PREFACE

This thesis is the result of several projects conducted at the Institute of Analysis at JKU Linz and the Institute of Mathematics and Scientific Computing at the University of Graz. It is based on the following four research works (ordered chronologically by first-announcement date) and aims to put them into a common framework.

with A. Hinrichs and J. Prochno: Random sections of $\ell_p$-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators, 2021. (submitted) <cit.> (see Chapter <ref>)

with F. Pillichshammer: On the relation of the spectral test to isotropic discrepancy and $L_q$-approximation in Sobolev spaces. J. Complex., 67, Article 101576, 2021. <cit.> (see Chapter <ref>)

with D. Krieg: Random points are optimal for the approximation of Sobolev functions, 2020.  (submitted) <cit.> (see Chapter <ref>)

with F. Pillichshammer: A note on isotropic discrepancy and spectral test of lattice point sets. J. Complex., 58, Article 101441, 2020. <cit.> (see Chapter <ref>)

The following additional research articles by the author are not included in this thesis.

with D. Krieg: Function recovery on manifolds using scattered data, 2021. <cit.>

with D. Krieg and E. Novak: Recovery of Sobolev functions restricted to iid sampling. Math. Comp., 91(338):2715-2738, 2022. <cit.>

with A. Baci, Z. Kabluchko, J. Prochno and C. Thäle: Limit theorems for random points in a simplex. J. Appl. Probab. (accepted), 2021+. <cit.>

CHAPTER: INTRODUCTION

One could say that mathematics is an endless process in which the following sequence repeats itself indefinitely. Asking a question, searching for an answer which is often (to the possible discomfort of non-mathematicians) understood as a proof of the mere existence of a solution, discovering the structures behind and raising questions about them. It may come as no surprise that this work is no different as it is guided by a question which arose in previous research and in turn triggers new open problems. In order to give more details, let us introduce the setting and give the motivation behind. The subject of study belongs to theoretical numerical analysis, which deals less with the numerics behind implementable algorithms than with the analysis of the given numerical problem itself. As we understand it, this branch of mathematics lies at a crossroads between approximation theory, functional analysis, geometry, information-based complexity (IBC) and probability. In what follows, we draw upon these fields to set the stage, and fill in details in Chapter <ref>.

Consider the abstract numerical problem of finding a solution $S(f)$ for each object $f$ (or problem instance) in a class $F$. For one reason or another, it might be the case that we cannot solve the problem exactly for each problem instance. For one, the quantity $S(f)$ might be difficult to compute, say it is the integral of a complicated function $f$ belonging to some class of functions $F$. Second, we may only have incomplete knowledge about $f$, meaning it cannot be described through the finite amount of available data.

In either case, we might try to use finitely many observations of any particular $f\in F$ to approximate the solution $S(f)$. Let $L_1(f),\dots,L_n(f)$ be real numbers denoting the $n\in\IN$ observations we collect about $f$, where the measurements $L_1,\dots,L_n\colon F\to \IR$ are known and may be applied to any $f\in F$ to produce observations. To avoid writing them in full, we use the notation $N_n(f)=\big(L_1(f),\ldots,L_n(f)\big)$ for information about $f$, which we shall use to construct an approximation $A(f)$ to the true solution $S(f)$. Necessarily, if we are only to use this information, the approximation has to be of the form $A(f)=\varphi\big(N_n(f)\big)$, where $\varphi$ takes $n$ real numbers as input.

To illustrate, let us give two examples which will accompany us throughout this work. In the integration problem, the object $f$ is a function belonging to a class $F$ of functions and has integral $S(f)$ (with respect to some fixed measure). In this case, information may be given for example by function evaluations $N_n(f)=\big(f(x_1),\ldots, f(x_n)\big)$ and $\varphi\big(N_n(f)\big)$ should approximate the integral of $f$. In the approximation problem, the object $S(f)=f$ is to be approximated itself from information $N_n(f)$ given by function evaluations or from linear measurements such as Fourier coefficients.

We view $N_n$ as a map from $F$ to $\IR^n$, returning for each $f$ information $N_n(f)$ about $f$. We then speak of the information map $N_n$. Similarly, we can interpret $\varphi$ as a map from $\IR^n$ to the set of possible approximants and call it the reconstruction map. The composition $A=\varphi\circ N_n$ is then an algorithm using the information map $N_n$. In practice, such an algorithm may represent an actual (future) implementation which runs on a computer (or any other Turing machine) and handles finitely many inputs to produce an output in finite time.

In general, finite information $N_n(f)$ is insufficient to determine $f\in F$ and, even though we may know $f$ itself, we assume it is an unknown element of $F$ except for information $N_n(f)$. Therefore, any, even the best,  algorithm using the information map $N_n$ is bound to incur a non-zero error on some $f\in F$. The minimal worst-case error over all possible algorithms using the information map $N_n$ is called the radius of information $N_n$ and measures its quality or power. The smaller its radius, the better the information map.

Naturally, one is interested in solving the given numerical problem of approximating $S(f)$ with an error as small as possible by using $n$ measurements. A lower bound on this error is given by the smallest possible radius over all information maps using at most $n$ measurements. This quantity is called the $n$-th minimal radius of information. Then our main aim is to understand whether (near-)optimal information, whose radius is close to this lower bound (in an asymptotic sense), has to be something singular, arcanely constructed, or rather is typical in the sense that most information maps using $n$ measurements have a radius comparable to the $n$-th minimal radius of information. We phrase this as two related questions.

How typical is optimal information? How optimal is typical information?

As a shortcoming of our rather abstract approach this pair of questions is not yet well-posed. Although we shall make it more precise in Chapter <ref>, we understand it rather as a theme with many facets and do not expect a definite answer but a whole spectrum of them. In the following, we wish to give some idea how possible solutions may look like.

First, we need to clarify what “typical” and “most” mean in this context. This can be resolved by putting a measure on the set of allowed measurements and thus considering random measurements. In many situations, a canonical choice of measure suggests itself but it may be specific to the problem. The random measurements can be collected to form random information. Then, determining the optimality of typical information amounts to studying the radius of random information and therefore we will use the terms “typical” and “random” interchangeably.

From a practical point of view, there are several issues we will ignore in this work. We are interested in the radius of information as a theoretical quantity and are not so much concerned with explicit algorithms. Also, we do not consider the often non-trivial process of generating the required random objects. Further, in most cases, we will not be interested in constants but only asymptotic behaviour. Instead, we wish to gain insight into the qualititative behaviour of the typical radius compared to the minimal radius. In this way, we hope to increase our understanding of the problems themselves. For further motivation we draw in the following from previous work in this direction.

To the best of our knowledge, the pair of questions above has not been studied in the literature in such a general context except by Hinrichs, Krieg, Novak, Prochno and M. Ullrich in the articles <cit.> and <cit.> which initiated part of the research presented in this thesis. The work <cit.> asks about the power of random information, that is, the typical quality of random information coming in by independent and identically distributed (i.i.d.) observations for various numerical problems. The mentioned works contain results on integration and approximation in Sobolev spaces as well as recovery in ellipsoids and associated Hilbert spaces. This thesis extends these insights about the power of random information and gives possible answers to the two questions above.

In <cit.> at least two arguments were put forward to justify the use, and consequently the study, of random instead of optimal information.  First, one can easily increase the number of measurements and thus decrease the error without problem if there is a method of sampling random measurements. This allows for some flexibility compared to specifically chosen information which may need to be re-computed if one adds an additional measurement. Second, optimal information is often tailored to the specific problem, whereas typical information can be used for many different problems. This behaviour reflects a kind of universitality.

To mention potential applications, the assumption of i.i.d. observations is common in (statistical) learning theory, which infers functional dependencies from empirical data from real-world applications, see, e.g., Vapnik <cit.>. This field is behind many developments associated with the nowadays popular concept of a neural network which should replace the object it is modeled on, the (human) brain, in modern applications such as pattern recognition or autonomous driving. Therefore, the study of the power of random information may contribute to the understanding of the effectiveness of algorithms used in these fields.

As mentioned, we expect a spectrum of possible ways how random information might compare to optimal information. Essentially, we distinguish the following ends of the spectrum. Random information may either be close to optimal or completely useless. In fact, these are the only two possibilities appearing in a problem treated in Chapter <ref>. Let us describe what we can conclude from either one.

If typical information is close to optimal or, equivalently, the power of random information is best possible with high probability, then one might use random information if optimal information is not available or costly to obtain. Sometimes it is even the case that the best known information is a realization of random information. This is related to the Probabilistic method using which one proves the existence of an object with a desired property by establishing it with positive probability for a randomly chosen object from a suitably constructed probability space. For an illustration and examples ranging from random graphs to combinatorial discrepancy we refer to the book of the same name <cit.> by Alon and Spencer. Let us add here that this approach is behind the construction of suitable point sets for numerical integration or the use of random matrices in the field of compressed sensing. The latter is a toolbox to efficiently process signals from applications such as facial recognition or magnetic resonance imaging, where only a few large wavelet coefficients are necessary to obtain a good approximation.

On the other hand, a large gap between the power of random information and the optimal behaviour may suggest that measurements have to be carefully selected in order to obtain good algorithms. On a practical note, we may deduce from this how not to gather information. It appears that the required lower bounds on the power of random or typical information, which also exhibit the limitations of the Probabilistic method, are far and few in between. Although it is sensible to focus on upper bounds as guarantees for random algorithms, we believe that the other side of the coin deserves attention too.

Apart from its contribution to solving numerical problems, the study of random information combines different fields of mathematics and may increase our knowledge about random structures. For example, if information is collected via function samples, then the radius of information is related to geometric features of the point set such as the distortion or the discrepancy, see Chapters <ref> and <ref>, respectively. If the point set is drawn randomly, this is connected to the study of Voronoi tessellations induced by a Poisson point process, see, e.g., Yukich <cit.>. Further, if the underlying set is a sphere, the radius of the largest hole in a random point set determines the Hausdorff distance between the ball and its approximation by the convex hull of the points. These topics belong to stochastic geometry as described for example in the book by Schneider and Weil <cit.>.

As an example of the power of random information, we would like to mention the famous result on the polynomial tractability of star-discrepancy by Heinrich, Novak, Wasilkowski and Woźniakowski <cit.> drawing from progress in empirical process theory due to Talagrand <cit.>, see also Novak and Woźniakowski <cit.>. The concept of tractability quantifies high-dimensional behaviour and this example shows that random information can be an antidote to the so-called curse of dimensionality, which occurs if the problem complexity depends exponentially on the dimension.

In fact, random information is part of the blessing of dimensionality as observed for example by Kainen <cit.>. Put briefly, this term summarizes regularizing effects as the dimension increases such as the concentration of measure phenomenon for which we refer to the book by Ledoux <cit.> of the same name.

Concentration of measure has been extensively used in the local theory of Banach spaces which evolved the field of asymptotic geometric analysis at the midpoint between geometry and functional analysis. There, properties of normed spaces as the dimension tends to infinity are studied. Famous questions like the thin-shell or the hyperplane conjecture are still open and the progress towards their solution shows how unintuitive high-dimensional objects may be to the imagination of us three-dimensional beings, see the books by Artstein-Avidan, Giannopoulos and V. D. Milman <cit.> as well as V. D. Milman and Schechtman <cit.> for an extensive overview of the subject.

A related phenomenon specific to high dimensions has been called existence versus prevalence by Vershynin <cit.>, see also Giannopoulos, V. D. Milman and Tsolomitis <cit.>, Litvak, Pajor and Tomczak-Jaegermann <cit.> as well as the references given there. Roughly speaking, it claims that the existence of one structure with a certain desired property implies that actually most structures satisfy this property. In the works mentioned, the diameter of a random sections of convex bodies has been considered but this also occurs also in related situations. This is a further example of the power of random information and will be discussed in Chapter <ref>.

We give an overview of the structure of the remainder of this thesis. First, Chapter <ref> gives definitions of the concepts introduced above and lays the foundation for the remaining chapters. In particular, the notion of random information is discussed for linear information given by functionals (Section <ref>) and standard information given by function evaluations (Section <ref>).

The main body is composed of three Chapters <ref>, <ref> and <ref> which are modeled onto published research during work on this thesis, plus an interlude Chapter <ref> connecting Chapters <ref> and <ref>. Let us first describe the common structure of the triple (<ref>, <ref>, <ref>). Each opens with a detailed introduction which embeds the related publication(s) into a wider context and serves as a motivation. This is followed by a discussion of the results together with existing work. Afterwards, concepts of the proofs behind the results are highlighted in order to make the proofs more accessible and to prepare for follow-up work. Remaining open questions will be posed and discussed at the end in order to provide points of departure for subsequent research and to continue the mathematical process. Throughout these chapters, we will use the optional notation “Theorem X.x ([XYZ00, Thm. X])” to clarify where the corresponding result is derived from.

Chapter <ref> treats linear information for the recovery of vectors belonging to general convex bodies and also to generalized ellipsoids. The results obtained there extend the work from the Hilbert space case in <cit.> and are related to Gelfand numbers of diagonal operators. We present two upper bounds on the radius of random information, one relying on asymptotic geometric analysis, and another relying on compressed sensing. Then we discuss implications for the important special case of polynomial semiaxes, where we conjecture a dichotomy for the power of random information. This is based on the joint work <cit.> with Hinrichs and Prochno.

In Chapter <ref> we study standard information for the approximation and integration of functions, mainly from Sobolev but also from Hölder and Triebel-Lizorkin spaces. Motivated by the study of the power of random information, we derive a characterization of the radius of information given by a point set in terms of the distortion, which measures the size of an average or the largest hole. As a consequence, this yields the optimality of random information for a certain range of parameters including integration. We discuss connections to quantization theory which we use to deduce our result. This chapter is derived from the joint work <cit.> with Krieg.

The subsequent Chapter <ref> does not contain any new results but instead collects material on optimal transport and quantization theory with the aim of discussing the weights used by (near-)optimal algorithms for integration problems. We find that these weights can be given explicitly in terms of the Voronoi cells of the underlying point set. Further, we argue why in some cases weights can be assumed to be normalized and sometimes even of equal size, which yields a (somewhat improvised) connection to the geometrical concept of discrepancy.

Finally, in Chapter <ref> standard information is discussed in the context of equal weight cubature rules for numerical integration and discrepancy, which is introduced in a general fashion. The main result is a lower bound on the isotropic discrepancy of lattice point sets which answers a question raised by Aistleitner, Brauchart and Dick <cit.> and shows that structured point sets may be at a disadvantage compared to random ones. We derive this from a characterization of the isotropic discrepancy of a lattice point set in terms of the so-called spectral test and derive an asymptotic equivalence for the radius of information given by a lattice point set. The results are taken from joint work with Pillichshammer, namely, <cit.> and the follow-up work <cit.>.

Almost all of the proofs are outsourced to the Appendices <ref> - <ref> at the end of this thesis, which mirror Chapters <ref> - <ref>.

Notation.  At this point we wish to clarify some notation. The positive integers are denoted by $\IN=\{1,2,\ldots\}$ and we write $\IN_0=\IN\cup \{0\}$. Given a sequence $x=(x_i)_{i\in\IN}$ and $0<p\le\infty$, write $\|x\|_p:=(\sum_{i=1}^{\infty}|x_i|^p)^{1/p}$ for $p<\infty$ and $\|x\|_{\infty}:=\sup_{i\in\IN}|x_i|$ for $p=\infty$. The unit ball of $\ell_p$, the space of sequences $x$ with $\|x\|_p<\infty$, is $\IB_p:=\{x\colon \|x\|_p\le 1\}$. We write $\ell_p^m$ for the $m$-dimensional subspace spanned by the first $m\in\IN$ coordinates and $\IB_p^m$ for its (closed) unit ball. If $1\le p\le\infty$, then $p^*$ is the Hölder conjugate with $\frac{1}{p}+\frac{1}{p^*}=1$, where $a/\infty:=0$ for any $a\in\IR$. If $p=2$, the space $\ell_2^m$ is equipped with the standard inner product $\langle\cdot,\cdot\rangle$ and $\IS^{m-1}:=\partial \IB_2^m$ is the sphere bounding the unit ball.

For any real $a\in \IR$ we use the notation $(a)_+:=\max\{a,0\}$ and $a=\lfloor a\rfloor+\{a\}$, where $\lfloor a\rfloor\in \ZZ$ is the integral and $0\le \{a\}<1$ the fractional part of $a$. Logarithms are always taken to basis ${\rm e}=2.71828\dots$.

If $A$ is any set, then $\bfone_A$ denotes the indicator function of $A$ with $\bfone_A(x)=1$ if $x\in A$ and zero else. If $B$ is another set, we do not exclude the case of equality in the notation $A\subset B$. If $A$ is finite, we use $\#A$ to denote its cardinality.

We assume that all random variables are defined on a common probability space and use $\IP$ and $\IE$ for probability and expectation, respectively. The asymptotic notations $\asymp,\lesssim,\gtrsim$ are explained in Definitions <ref> and <ref>. Other notation is explained at its first point of appearance and collected in the [ch:los]List of symbols.

CHAPTER: PRELIMINARIES

In this chapter, we introduce the framework supporting the remainder of the thesis. We wish to clarify the notions used in the introduction and for the sake of completeness allow for some redudance. First, in Section <ref>, we explain fundamental concepts such as the radius or minimal radius of information. Section <ref> introduces the setting of recovery using linear information on which Chapter <ref> is based. In Section <ref> we discuss standard information which is obtained by function samples and a special case of linear information. This is the basis for Chapter <ref>, and in parts also Chapters <ref> and <ref>.

§ THE RADIUS OF INFORMATION

Recall that for each $f$ in a class of objects $F$ we want to compute a solution $S(f)$ to a numerical problem. Here, the solution operator $S\colon F\to G$ maps into a set $G$ containing the set of possible outcomes $S(F):=\{S(f)\colon f\in F\}$. We use $n$ measurements $L_1(f),\ldots,L_n(f)\in\IR$, where $L_i\colon F\to \IR$ for $i=1,\ldots,n$, and combine them into information $N_n:=(L_1,\ldots,L_n)\colon F\to\IR^n$. Using a reconstruction map $\varphi\colon \IR^n\to G$, we construct from the given information $N_n(f)$ an approximation $\varphi\big(N_n(f)\big)\approx S(f)$. Note that we assume the knowledge of the information map $N_n$, and the map $\varphi$ may (and will) depend on the information map $N_n$. The following diagram illustrates the situation.

\[
\xymatrix{
F\ar[rr]^{S}\ar[rd]_{N_n} & & G\\
& \mathbb{R}^n \ar[ur]_{\varphi}  & }
\]

We impose additional structure and assume that $F$ and $G$ are normed vector spaces equipped with norms $\|\cdot\|_F$ and $\|\cdot\|_G$, respectively. In this way, we arrive at the setting of information-based complexity, as treated for example by Traub, Wasilkowski and Woźniakowski <cit.> and in the book series by Novak and Woźniakowski <cit.>.

The problem formulation suggests measuring the closeness $\approx$ between the approximation $A(f)=\varphi\big(N_n(f)\big)$ and the true value $S(f)$ with $\|S(f)-A(f)\|_G$, which is called the error of the algorithm $A$ at $f\in F$. It is useful to have a uniform error guarantee for the algorithm $A$ as the instance $f\in F$ producing information $N_n(f)$ may be unknown. Therefore, consider the worst-case error

\begin{equation} \label{eq:wce}
e(S\colon F\to G,A)
:=\sup_{f\in F_0} \|S(f)-A(f)\|_G
\end{equation}

of $A$ over the unit ball $F_0:=\{f\colon \|f\|_F\le 1\}$ of $F$. Abusing notation, we frequently replace the supremum by $\sup_{\|f\|_F\le 1}$.

One reason to consider the worst-case error over the unit ball is that the norm $\|\cdot\|_F$ measures the size or complexity of the input and elements with larger norm may be more difficult to approximate. More precisely, if both $A$ and $S$ are linear maps, we can use the worst-case error to obtain a bound on the error of $A$ at an arbitrary $f\in F$ by normalizing it. This provides some motivation to consider this error criterion and results from

\begin{align*}
\|S(f)-A(f)\|_G
\le \|f\|_F\, e(S\colon F\to G,A).
\end{align*}

To ensure a finite worst-case error, it is convenient to suppose that $S$ is bounded, that is,

\[
\sup_{\|f\|_F\le 1}\|S(f)\|_G
=e(S\colon F\to G,0)<\infty.
\]

In other words, when we do not have any information, we take the algorithm equal to zero and the resulting initial error is supposed to be finite.

Formally, the radius of information is defined as follows.

The radius of an information map $N_n\colon F\to \IR^n$, where $n\in\IN$, is

\begin{equation} \label{eq:radius-info}
r(S\colon F\to G,N_n)
:=\inf_{\varphi}e(\chg{S\colon F\to G},\varphi\circ N_n),
\end{equation}

where the infimum is taken over all reconstruction maps $\varphi\colon\IR^n\to G$.

Equivalently, the radius $r(S\colon F\to G,N_n)$ is the minimal worst-case error over all algorithms $A=\varphi\circ N_n$ using the information map $N_n$. The term “radius” is of geometric origin and is related to the fact that the algorithm which chooses a center of the set of elements of equal information has minimal worst-case error. The concept of a Chebyshev radius from numerical analysis is similar, see, e.g., Novak <cit.>.

In the following, we shall consider only continuous and linear measurements belonging to a class $\Lambda\subset \lall:=F'$, where $F'$ is the dual space of $F$ and contains all continuous and linear functionals from $F$ to $\IR$. Sections <ref> and <ref> will discuss the two choices of $\Lambda$ considered in this thesis, namely the case of linear information $\Lambda=\lall$ and the case of standard information $\Lambda=\lstd$ consisting of function evaluations.

In general, the class $\Lambda$ gives rise to information maps $N_n$ of the form

\begin{equation} \label{eq:info-lambda}
\text{where }L_i\in \Lambda \text{ for all }i=1,\dots,n,
\end{equation}

where $n\in\IN$ is the cardinality of $N_n$. The minimal radius is a benchmark for the quality of any information $N_n$ of the form (<ref>) and is given as follows.

The $n$-th minimal radius of information with respect to $\Lambda$ is

\begin{equation} \label{eq:def-min-info}
r(S\colon F\to G,\Lambda,n)
:=\inf_{N_n}r(S\colon F\to G,N_n),\quad n\in\IN,
\end{equation}

where the infimum is over all information maps $N_n\colon F\to \IR^n$ of the form (<ref>).

This is the best we can do using $n$ optimal measurements from the class $\Lambda$. By definition, the $n$-th minimal radius will be a non-increasing function of $n$ and, under suitable conditions, will tend to zero as the amount of information increases. This means that we can obtain arbitrarily good approximations using finite information, see also Remark <ref> below. Further, for any $n\in\IN$ and $N_n$ as in (<ref>), we have

\begin{equation} \label{eq:min-info}
r(S\colon F\to G,N_n)
\ge r(S\colon F\to G,\Lambda,n).
\end{equation}

We shall be interested in the question whether (<ref>) can be reversed up to a constant for most information maps.

Does it hold that for most information maps $N_n$ with measurements from $\Lambda$ that

\[
r(S\colon F\to G,N_n)
\lesssim r(S\colon F\to G,\Lambda,n)?
\]

This is a very general formulation of the problem studied in this thesis. In order to make sense of it, it is necessary to clarify what “most” shall mean. This shall be done in the remaining sections of this chapter. For now, we shall be concerned with explaining the notation $\lesssim$.

Given two sequences $(a_n)_{n\in\IN}$ and $(b_n)_{n\in\IN}$ of non-negative real numbers, we write $a_n\lesssim b_n$ if there exists a constant $C>0$ such that $a_n \le C\,b_n$ for all $n\in\IN$. In this case, we may also write $b_n\gtrsim a_n$. If there exists another constant $c>0$ such that also $a_n \ge c\, b_n$ for all $n\in\IN$ ($a_n\gtrsim b_n$) holds, then we write $a_n\asymp b_n$ and speak of asymptotic equivalence. We shall use this notation also for non-negative real numbers indexed for example by $(n,m)$ instead of $n$ and then demand that the implicit constants are independent of $n$ and $m$. Further we may use subindices as in $\lesssim_p$ to indicate that the implicit constant may depend on an additional parameter $p$.

The notation makes clear that we are mainly interested in the asymptotic behaviour, that is, in $n$ tending to $\infty$. If Question <ref> were true, then the asymptotic equivalence

\[
r(S\colon F\to G,N_n)
\asymp r(S\colon F\to G,\Lambda,n)
\]

would hold for “most” information maps $N_n$ with measurements belonging to $\Lambda$. In this case we say that the radius of typical information is asymptotically equivalent to the minimal radius. As we are mostly concerned only with this asymptotic formulation, we will often be careless about constants, which may be deduced from our proofs.

At the end of this section, we define the numerical problems central to this thesis.

In the approximation problem, the map $S$ is equal to the embedding $\id\colon F\to G$ which takes $f\in F$ to $\id(f)=f$ itself. We assume that $F\subset G$ and further that the embedding $\id\colon F\to G$ is bounded, i.e., there exists a constant $C$ such that $\|f\|_G\le C\|f\|_F$ for all $f\in F$. In this case we speak of a continuous embedding of $F$ into $G$ and write $F\hookrightarrow G$. We then use the notation

\[
r(F\hookrightarrow G, N_n):=r(\id\colon F\to G, N_n)
\]

and analogously for the minimal radius. The upcoming section will introduce random linear information for approximation as a preparation for Chapter <ref> and Section <ref> will introduce standard information used in Chapter <ref> for the approximation problem.

In the integration problem, the space $F$ is a space of real-valued functions on some measure space and $S$ takes a function $f\in F$ to its integral, so that $G=\IR$. Here, we assume that that $F$ is continuously embedded into the space of integrable functions. Then $S$ is a continuous linear functional itself and therefore it does not make sense to consider linear information but only standard information for this problem which will be treated in Chapters <ref>, <ref> and <ref> in various guises.

In this thesis, we consider only non-adaptive information maps of the form (<ref>) and use the same measurements for every $f\in F$. This is in contrast to adaptive information, where one may use the measurement $L_n(f)$ to select a suitable $L_{n+1}\in\Lambda$. Note that if $S$ is linear between normed spaces $F$ and $G$, as in the majority of the problems we will consider, then adaption can only yield an improvement of at most a constant factor, see, e.g., <cit.>. This justifies our assumption.

§ LINEAR INFORMATION AND GELFAND WIDTHS

In this section, we consider linear information $N_n$, which is of the form

\begin{equation} \label{eq:info-lin}
\text{where }L_i\in \lall \text{ for all }i=1,\dots,n,
\end{equation}

with $n\in\IN$. Recall that $\lall$ is the set of all continuous linear functionals on $F$. In the following, we shall assume that $S$ is linear and bounded as this is the case for the approximation and the integration problems we consider. Then the radius of information (Definition <ref>) satisfies the following well-known relation.

Let $S\colon F\to G$ be a bounded linear map between normed spaces. Then we have, for all linear information maps $N_n$ as in (<ref>),

\[
\sup_{f\in F_0\cap \ker N_n} \|S(f)\|_G
\le r(S\colon F\to G,N_n)
\le 2\, \sup_{f\in F_0\cap \ker N_n} \|S(f)\|_G,
\]

where $\ker N_n:=\{f\in F\colon N_n(f)=0\}$ is the kernel of $N_n$.

This states that the radius of any linear information $N_n$ is equivalent to the radius of the smallest ball in $G$ containing the symmetric set $\{S(f)\colon f\in F_0\cap \ker N_n\}$ of possible solutions having zero information. For convenience a proof of Proposition <ref> will be provided at the end of this section. Before we apply it to random information, we discuss its implications for the minimal radius.

Derived from Definition <ref>, the $n$-th minimal radius of linear information is given by

\begin{equation}
r(S\colon F\to G,\lall,n)
:=\inf_{N_n}r(S\colon F\to G,N_n),\quad n\in\IN,
\end{equation}

where the infimum is over all linear information maps $N_n$ of the form (<ref>). This is closely related to the following concept.

The $n$-th Gelfand number of $S\colon F\to G$ is given by

\[
c_{n}(S\colon F\to G)
:= \inf_{E_{n-1}} \sup_{f\in F_0\cap E_{n-1}}\|S(f)\|_G,
\]

where the infimum is over all linear subspaces $E_{n-1}\subset F$ of codimension $n-1$ and  for convenience we set $c_n(S\colon F\to G)=0$ if $n\ge \dim(F)$.

It is well known that the Gelfand numbers are comparable to the minimal radius in the sense of

\begin{equation}\label{eq:gelfand-radius}
c_{n+1}(S\colon F\to G)
\le r(S\colon F\to G,\lall,n)
\le 2\, c_{n+1}(S\colon F\to G),\quad
\end{equation}

A proof can be found for example in <cit.> by Heinrich but may deduced also from Proposition <ref> by taking the infimum over all linear information maps $N_n$ of cardinality $n$, since continuity implies that a subspace $E_n$ of $F$ is of codimension $n$ precisely when it is the kernel of such an $N_n$.

In the following, let us consider the approximation problem introduced at the end of the previous section. Our assumptions imply that Proposition <ref> applies to the embedding $F\hookrightarrow G$ which we deal with for the approximation problem. In view of this, we may also define, for every linear subspace $E\subset F$,

\begin{equation} \label{eq:radius-def}
\rad_G(F_0,E)
:= \sup_{f\in \chg{F_0\cap E}}\|f\|_G,
\end{equation}

which is the radius of the section of the unit ball $F_0$ with the subspace $E$ measured in the norm of $G$. Then, for all linear information maps $N_n$ we have

\begin{equation} \label{eq:radius-radius}
\rad_G(F_0,\ker N_n)
\le r(F\hookrightarrow G,N_n)
\le 2\,\rad_G(F_0,\ker N_n).
\end{equation}

To lay the foundation for Chapter <ref>, let us consider now the finite-dimensional case with $F=(\IR^m,\|\cdot\|_K)$ and $G=(\IR^m,\|\cdot\|_G)$ of dimension $m\in\IN$ and equipped with norms $\|\cdot\|_K$ and $\|\cdot\|_G$, respectively. The unit ball $K:=\{x\in\IR^m\colon \|x\|_K\le 1\}\subset \IR^m$ is a convex body, that is a compact convex set with non-empty interior. We will focus mainly on the special case of $\|\cdot\|_G=\|\cdot\|_2$ such that $G=(\IR^m,\|\cdot\|_2)=\ell_2^m$ becomes the Euclidean space equipped with its usual distance. In this case, we drop $G$ from the notation and replace (<ref>) by

\begin{equation} \label{eq:rad-r-finite}
\rad(K,\ker N_n)
\le r(K,N_n)
\le 2\,\rad(K,\ker N_n),
\end{equation}

where $r(K,N_n):=r\big((\IR^m,\|\cdot\|_K)\hookrightarrow \ell_2^m,N_n\big)$. This yields the equivalence between the radius of any linear information to the radius of the section of $K$ with the subspace $\ker N_n$. Most of the time, we shall assume that $n<m$ as otherwise vectors may be reconstructed exactly by simply measuring their coordinates.

By means of (<ref>), the minimal radius of information is then up to a constant of two equivalent to the Gelfand numbers of id$\colon (\IR^m,\|\cdot\|_K)\to \ell_2^m$, which we denote by

\begin{equation} \label{eq:gelfand-width}
:= \inf_{E_{n-1}} \sup_{f\in K\cap E_{n-1}}\|x\|_2,\quad n\in \IN,
\end{equation}

where the infimum is again over all linear subspaces $E_{n-1}\subset \IR^m$ of codimension $n-1$. The number $c_n(K)$ is also called the $n$-th Gelfand width of $K$ in $\ell_2$.

Generally speaking, the Gelfand numbers/widths quantify the degree of compactness and are studied as part of the theory of $s$-numbers and $n$-widths, see Pietsch <cit.> and Pinkus <cit.> for further information. It is known (see <cit.>) that a bounded linear map $S$ is compact if and only if the sequence of Gelfand numbers $(c_n(S\colon F\to G)\big)_{n\in\IN}$ decays to zero. By Proposition <ref> this transfers to the sequence of minimal radii and justifies assuming compactness of embeddings.

Now that we have elaborated sufficiently on the minimal radius and thus optimal linear information we would like to consider random linear information in this finite-dimensional setting. To this end, let us note that any linear functional $L\colon F\to \IR$ is automatically continuous and of the form $L(x)=\langle y,x\rangle,x\in \IR^m$, for some $y\in \IR^m$, where $\langle y,x\rangle = \chg{\sum_{i=1}^{m}y_i x_i}$ is the standard inner product. In this case, we say that $L$ is represented by the vector $y$. In this way, a linear information map $N_n=(L_1,\ldots,L_n)\colon \IR^m\to \IR^n$ can be identified with a $n\times m$-matrix with the representer of $L_i$ forming the $i$-th row.

Via the correspondence between linear functionals and their representers, a random measurement amounts to a random vector $X$ in $\IR^m$. Arguably, random information should not give priority to some particular direction. This amounts to supposing that the direction $X/\|X\|_2$ is uniformly distributed on the sphere $\IS^{m-1}:=\{x\in\IR^m\colon \|x\|_2=1\}$. To explain, the sphere $\IS^{m-1}$ can be equipped with a unique normalized rotation invariant measure $\sigma^{(m-1)}$ and we call a random vector $X'$ uniformly distributed on it if $\IP(X'\in A)=\sigma^{(m-1)}(A)$ for all Borel sets $A\subset \IS^{m-1}$. There is a simple and elegant way to construct such an object.

Take $g_1,\ldots,g_m$ independent standard Gaussians, that is random variables with density $(2\pi)^{-1/2}\exp(-x^2/2)$, and form the random vector $G_1:=(g_1,\ldots,g_m)$. Then the rotation invariance of $G_1$ implies that its direction $G_1/\|G_1\|_2$ is uniformly distributed on the unit sphere. This motivates the following definition of random linear information.

A random linear measurement is given by $x\mapsto \langle G_1,x\rangle$ and random linear information of cardinality $n$ consists of the measurements represented by $G_1,\dots,G_n$, where $G_2,\dots,G_n$ are i.i.d. copies of $G_1$. It can be identified with the $n\times m$-matrix $G_{n,m}$ filled with independent standard Gaussian entries and acts by mapping $x\in\IR^m$ to $(\sum_{j=1}^{m}g_{ij} x_j)_{i=1}^{n}\in \IR^n$. Here and in the following, we simplify notation by dropping the arguments of random variables.

The radius of such random (Gaussian) information is the random variable $r(K,G_{n,m})$. By relation (<ref>), we have, for all realizations,

\[
\rad\big(K,\ker(G_{n,m})\big)
\le r(K,G_{n,m})
\le 2\, \rad\big(K,\ker(G_{n,m})\big).
\]

Here, the kernel $\enran:=\ker(G_{n,m})$ is a random subspace of $\IR^m$ of codimension $n$ in the following sense, see for example Mattila <cit.> and Meckes <cit.>. Let $\mathcal{G}_{m,m-n}$ be the Grassmannian parametrizing all subspaces of $\IR^m$ which are of dimension $m-n$ and thus of codimension $n$. There is a unique probability measure on $\mathcal{G}_{m,m-n}$ which is invariant under rotation and $\enran$ is distributed according to this measure. Note that the probability that $\enran$ has codimension smaller than $n$ is zero.

In analogy to the radius of information, the radius of any section is at least the radius of a minimal section and thus, for every realization,

\[
\rad(K,n):=c_{n+1}(K)\le \rad(K,\enran),\quad 1\le n < m.
\]

The equivalence (<ref>) between the power of random (Gaussian) information for the recovery of vectors from an $m$-dimensional normed space with unit ball $K\subset \IR^m$ and the radius of its intersection with a random subspace allows to pose Question <ref> as follows.

What is the power of random standard information?

Do we have for random sections that
\rad(K,\enran) \lesssim \rad(K,n)
or equivalently
for Gaussian information that
r(K,G_{n,m}) \lesssim r(K,n)
with high probability?

This question will be taken up again in Chapter <ref> where we present results for a special class of sets, the $\ell_p$-ellipsoids and study the asymptotics as $n$ becomes large but remains much smaller than $m$. As we shall also consider unit balls of quasi-normed spaces, we conclude this section by commenting on them.

A quasi-normed space $F$ is a linear space equipped with a quasi-norm $\|\cdot\|_F$ instead of a norm. In replacement of the triangle inequality it satisfies

\[
\|f_1+f_2\|_F
\le C_F\big(\|f_1\|_F+\|f_2\|_F\big)\quad \text{for some constant }C_F\ge 1 \text{ and all }f_1,f_2\in F.
\]

If norms are replaced by quasi-norms, Proposition <ref> and relation (<ref>) remain valid with changed constants. For the convenience of the reader we state this in the following proposition and provide a proof.

Let $S\colon F\to G$ be a bounded linear operator between quasi-normed spaces, that is, $F$ and $G$ are equipped with quasi-norms with constant $C_F,C_G\ge 1$, respectively.  Then we have, for all linear information maps $N_n$ as in (<ref>),

\[
C_G^{-1}\sup_{f\in F_0\cap \ker N_n} \|S(f)\|_G
\le r(S\colon F\to G,N_n)
\le 2\, C_F\, \sup_{f\in F_0\cap \ker N_n} \|S(f)\|_G,
\]

where $\chg{\ker N_n=}\{f\in F\colon N_n(f)=0\}$.

For the lower bound on the radius of information we have to prove that

\[
\inf_{\varphi}\sup_{f\in F_0} \big\|S(f)-\varphi\big(N_n(f)\big)\big\|_G
\ge C_G^{-1}\sup_{f\in F_0\cap\ker N_n}\|S(f)\|_G
\]

where $F_0=\{f\in F\colon \|f\|_F\le 1\}$ and the infimum is over all $\varphi\colon \IR^n\to G$. Thus fix an arbitrary $\varphi\colon \IR^n\to G$. For every $f\in F_0\cap \ker N_n$ also $-f\in F_0\cap \ker N_n$ and, since $S$ is linear,

\begin{equation}\label{eq:radzero}
\|S(f)-\varphi(0)\|_G \ge C_G^{-1}\|S(f)\|_G \quad\text{ or }\quad \|S(-f)-\varphi(0)\|_G \ge C_G^{-1}\|S(f)\|_G
\end{equation}

holds. Moreover, the symmetry of $F_0\cap \ker N_n$ implies

\[
\sup_{f\in F_0}\|S(f)-\varphi(N_n f)\|_G
\ge \sup_{f\in F_0\cap \ker N_n}\max\big\{\|S(f)-\varphi(0)\|_G,\|S(-f)-\varphi(0)\|_G\big\}.
\]

Together with (<ref>) this proves the lower bound.

For the upper bound we specify a map $\varphi$ by $\varphi(y)=S(g)$ for any $y\in N_n(F_0)$, where $g\in F_0$ with $N_n g=y$ is arbitrary. Then

\[
\sup_{f\in F_0}\|S(f)-\varphi(N_n f)\|_G
\le \sup_{\substack{f_1,f_2\in F_0\\ N_n f_1 =N_n f_2}}\|S(f_1)-S(f_2)\|_G
\le \sup_{f\in 2C_F F_0 \cap \ker N_n}\|S(f)\|_G
\]

since $f_1-f_2\in 2 C_{F} F_0$ if $f_1,f_2\in F_0$ and $N_n (f_1-f_2)=0$ if $N_nf_1 = N_nf_2$. Since $S$ is linear, a rescaling concludes the proof.

Note that Proposition <ref> may be seen as a replacement for <cit.> which applies even to sets not necessarily being unit balls of quasi-normed spaces and is more general than what we shall need. The proof of <cit.> is very similar to the one of Proposition <ref>.

One might also consider other distributions on the space of linear functionals giving rise to other notions of typical information. For example, Mendelson, Pajor and Tomczak-Jaegermann <cit.> studied recovery of vectors using information given by i.i.d. copies of a linear measurement $x\mapsto \langle X,x\rangle$, where $X$ is an isotropic and subgaussian random vector, that is, for some $\alpha\ge 1$,

\[
\chg{\IE X =0,\quad }\IE |\langle X,x\rangle|^2 = \|x\|_2^2 \quad \text{and}\quad \|\langle X,x\rangle \|_{\psi_2}\le \alpha \|x\|_2, \quad x\in \IR^m,
\]

where $\|\cdot\|_{\psi_2}$ is an Orlicz norm with function $\psi_2(t)=e^{t^2}-1$, see, e.g., <cit.>. This includes, aside from the Gaussian measure, the uniform measure on $\{-1,1\}^m$ and the normalized volume on various symmetric convex bodies such as $\ell_p$-balls, $2\le p\le \infty$.

§ STANDARD INFORMATION AND SAMPLING ALGORITHMS

In the following, we will discuss standard information where the measurements correspond to function evaluations at a point set. In particular, the objects of study will be functions and $F$ will be a normed space of functions $f\colon D\to \IR$ on some (infinite) set $D$, which may be a subset of $\IR^d$, a manifold or an even more general space. As in Section <ref>, let $S\colon F\to G$, where $G$ is a normed space.

The class of standard information is $\lstd:=\{\delta_x\colon x\in D\}$, where for all $x\in D$ the delta functional $\delta_x$ is the point evaluation $f\mapsto \delta_{x}(f):=f(x)$ for all $f\in F$. Then a standard information map is given by

\begin{equation} \label{eq:info-std}
\text{where }x_i\in D \text{ for all }i=1,\dots,n.
\end{equation}

We can identify such an information map $N_n$ with the point set $\Pn=\{x_1,\ldots,x_n\}$ it relies on and write $N_n(f)=\big( f(x_1),\ldots,f(x_n)\big)$. Here and in the following, we always assume that such point sets are non-empty and finite, and that their points are pairwise distinct. For every $x\in D$ the evaluation functional $\delta_x$ is linear and we shall also assume that it is continuous or bounded, that is, there is a constant $C>0$ such that, for every $f\in F$, we have $|f(x)|\le C\|f\|_F$. Then $\lstd\subset \lall$ holds.

The definition of the radius of the information map $N_n=(\delta_{x_1},\ldots,\delta_{x_n})$ can be written in terms of the point set $\Pn=\{x_1,\ldots,x_n\}$ and we use the notation

\[
r(S\colon F\to G,\Pn)
:=r(S\colon F\to G,N_n)
\]

where the infimum is over all maps $\varphi:\IR^n\to G$. From now on we shall always replace standard information $N_n$ as in (<ref>) by its underlying point set and refer to the radius of information given by a point set also as the quality of the point set itself.

A special case of (<ref>), the $n$-th minimal radius of standard information is

\[
r(S\colon F\to G,\lstd,n)
=\inf_{\#\Pn= n}
r(S\colon F\to G,\Pn), \quad n\in\IN,
\]

where the infimum is over all $n$-point sets $\Pn\subset D$. Here, the number $\#\Pn=n$ denotes the cardinality of $\Pn$. The $n$-th minimal radius is sometimes called $n$-th sampling number and may be expressed as

\[
r(S\colon F\to G,\lstd,n)
=\inf_{S_{\Pn}}e(S\colon F\to G,S_{\Pn})
\]

where the infimum is over all sampling operators of the form

\begin{equation}\label{eq:sampling-operator}
\chg{S_{\Pn}\colon F \to G},
\qquad S_{\Pn}(f)=\varphi\big(f(x_1),\hdots,f(x_n)\big)
\end{equation}

where $\Pn=\{x_1,\ldots,x_n\}\subset D$ consists of $n$ points and $\varphi\colon\IR^n\to G$ is arbitrary. By Proposition <ref>, for any bounded linear $S$ and any point set $\Pn\subset D$,

\begin{equation}
\label{eq:radius-sampling}
\sup_{\substack{f\in F_0\\ f|_{\Pn}=0}}\|S(f)\|_G
\le r(S\colon F\to G,\Pn)
\le 2 \sup_{\substack{f\in F_0\\f|_{\Pn}=0}}\|S(f)\|_G,
\end{equation}

and by taking the infimum over all $n$-point sets this holds for the sampling numbers. Here, $f|_{\Pn}$ is the restriction of $f$ to $\Pn$. Via Proposition <ref> this transfers to the quasi-Banach case, see also Novak and Triebel <cit.>.

Since the infimum in the definition of the sampling numbers is over the smaller set of function evaluations, we have

\[
r(S\colon F\to G,\lstd,n)\ge r(S\colon F\to G,\lall,n),\quad n\in \IN,
\]

and in general comparing the power of standard and linear information is of much interest in IBC, see for example <cit.>.

To formalize Question <ref> on the power of random information for standard information, we need to give meaning what “most” means and for this need a “uniform” measure on the set of evaluation functionals $\lstd$. As each functional $\delta_x\in\lstd$ is in one-to-one correspondence with a point of $x\in D$, this amounts to putting a measure on $D$. In general, let $D=(D,\Sigma,\lambda)$ be a finite measure space, where the measure $\lambda$ will be assumed to be a probability measure. Often, a suitable choice of $\lambda$ can be thought of as uniform measure and may be used to define random standard information as follows.

Recall that for linear information on $\IR^m$ the space itself parametrizes the linear functionals and we defined a random linear functional as a Gaussian vector. For standard information we can identify measurements with points and use random points instead.

A random point evaluation is given by $\delta_X$, where $X$ is a random point $X$ in $D$ distributed according to $\lambda$, that is $\IP(X\in A)=\lambda(A)$ for every $A\in\Sigma$. For random standard information of cardinality $n\in\IN$ we take the map $N_n=(\delta_{X_1},\ldots,\delta_{X_n})$ where $X_1,\ldots,X_n$ are independent copies of $X$. It can be identified with the random point set $\pnran:=\{X_1,\dots,X_n\}$.

In many cases there are obvious choices for such a measure $\lambda$. For example, we will deal with $D$ being some $d$-dimensional open set equipped with the normalized Lebesgue measure defined by $\vol(A\cap D)/\vol(D)$ for all Borel sets $A\subset \IR^d$, where $\vol=\vol_d$ denotes the $d$-dimensional Lebesgue measure. Further examples include Riemannian manifolds, on which the metric induces a volume measure, or the Grassmannian  with its rotation invariant probability measure, which was discussed in the previous section.

For each realization, the random point set $\pnran=\{X_1,\ldots, X_n\}$ is a point set and we ignore the possibility that points of it coincide as this event will have probability zero in the cases we consider. The radius of random standard information is the random quantity	$r(S\colon F\to G,\pnran)$ and it is at least the $n$-th minimal radius of standard information. In other words, random points can not be better than optimal points. We translate Question <ref> to standard information as follows.

What is the power of random standard information?

Do we have for the radius of random information that

\[
r(S\colon F\to G, \pnran) \lesssim r(S\colon F\to G,\lstd, n)
\]

with high probability?

In order to give an answer to this question, we will study the radius of information of arbitrary realizations and derive expressions which can be estimated for the random point set $\pnran$. The following notation which is a variant of the asymptotic notation in Definition <ref> will be useful.

Given two real numbers $a(\Pn)$ and $b(\Pn)$ which depend on a point set $\Pn\subset D$, we write $a(\Pn)\asymp b(\Pn)$ if there exist $c,C>0$ such that

\[
c\, a(\Pn) \le b(\Pn) \le C\,a(\Pn)\quad \text{for all }\Pn=\{x_1,\dots,x_n\}\subset D,n\in\IN,
\]

and analogously for $\lesssim$ and $\gtrsim$.

We will deal with Question <ref> in Chapters <ref>, <ref> and <ref>. We want to describe the approximation and the integration problems for which we study it in more detail. Let $D=(D,\Sigma,\lambda)$ be a finite measure space. If $D$ is additionally a topological space, then the continuity of the evaluation functionals is ensured by assuming that $F\hookrightarrow C_b(D)$, i.e., $F$ is continuously embedded into $C_b(D)$, the space of bounded continuous real-valued functions on $D$ equipped with the supremum norm $\|f\|_{\infty}:=\sup_{x\in D}|f(x)|$. In this case, there exists a constant $C>0$ such that $\sup_{x\in D}|f(x)|\le C\|f\|_F$ for all $f\in F$. This assumption, which is slightly stronger than necessary, is satisfied by the function spaces considered in Chapter <ref>.

Let further $\mu$ be a probability measure on $D$ which is absolutely continuous with respect to $\lambda$ and has bounded density $\varrho\colon D\to\IR$.

$L_q$-approximation. This is the approximation problem considered at the end of Section <ref> with $(G,\|\cdot\|_G)=(L_q(D,\mu),\|\cdot\|_{L_q(D,\mu)})$ for some $0< q \le \infty$. Here, $L_q(D,\mu)$ is the space of (equivalence classes of) measurable functions $f\colon D\to\IR$ with finite $L_q$-norm

\begin{equation} \label{eq:lqnorm}
\|f\|_{L_q(D,\mu)}
\Big(\int_D |f(x)|^q \dd \mu(x)\Big)^{1/q}&\text{if }\chg{0< q<\infty,}\\
\esssup_{x\in D} |f(x)|&\text{if }\chg{q =\infty}.
\end{cases}
\end{equation}

The embedding into $C_b(D)$ ensures, for all $0< q\le\infty$, the embedding into $L_q(D,\varrho)$ because of $\chg{\|f\|_{L_q(D,\mu)}^q\le C\|\varrho\|_{\infty}\lambda(D)\|f\|_F^q}$, for all $f\in F$. If $\mu=\lambda$ we will omit it in the notation and simply write $L_q(D)$.

Integration.  Here, we choose $S={\rm INT}_{\mu}$ and $G=\IR$, where

\[
{\rm INT}_{\mu}\colon F\to \IR,\quad
{\rm INT}_{\mu}(f)
:=\int_D f(x) \dd\mu(x), \quad f\in F,
\]

is the integration functional. Note that ${\rm INT}_{\mu}(f)\le \|f\|_{L_1(D,\mu)}$ and thus $F\hookrightarrow C_b(D)$ also ensures the continuity of $\intmu$. In general, we omit the space $G=\IR$ in the notation and write $e(F,\intmu,A)$ for the worst-case error of an algorithm $A$ and $r(F,\intmu,\Pn)$ for the radius of information given by $\Pn\subset D$. If $\mu=\lambda$, we shall use ${\rm INT}$ instead of $\intmu$.

Both problems will be studied in Chapter <ref> for Sobolev spaces and also other function spaces defined on subsets of $\IR^d$. For simplicity, only the case of $\mu=\lambda=\vol$, the Lebesgue measure, will be considered there. At this point, we remark that on $\IR^d$ measurability and integrability are understood in the sense of Lebesgue, except mentioned otherwise. The integration problem is also central to Chapter <ref>, where it is treated with respect to general probability measures on $\IR^d$, and Chapter <ref>, where mainly the cube equipped with $\vol$ is treated.

Since the measure $\mu$ influences the contribution of subsets of $D$ to the approximation error, one may use $\mu$ instead of $\lambda$ to define random standard information. However, in this thesis we will not consider sampling from distributions different from the uniform one.

CHAPTER: GAUSSIAN INFORMATION FOR GENERALIZED ELLIPSOIDS

In this chapter, we will present results from <cit.> on the power of random linear information for the recovery of vectors from $\ell_p$-ellipsoids, and thus generalize the work <cit.> for the usual ellipsoids. To give some idea, the $\ell_p$-ellipsoids can be defined as the images of $\ell_p$-balls $\IB_p^m$ under diagonal operators and their Gelfand widths are thus related to the Gelfand numbers of diagonal operators. In the upcoming Section <ref> we present their connection to certain function spaces after surveying the literature on random sections of convex bodies.

Let us describe the remainder of this chapter. In Section <ref> we present our main results from <cit.> and discuss connections with existing work. Then in Section <ref> we shall look at the important example of $\ell_p$-ellipsoids with polynomial semiaxes and assess the power of random linear information for those. Afterwards in Sections <ref>, <ref> and <ref> we explain the methods behind the proofs, essentially covering topics ranging from asymptotic geometric analysis to sparse approximation. Finally, in Section <ref> we collect points of departure for further research.

§ INTRODUCTION AND MOTIVATION

Consider the $m$-dimensional approximation problem from Section <ref>, where linear information is used to recover vectors in the $\ell_2^m$-norm from the unit ball of an $m$-dimensional normed space, which is a symmetric convex body $K$. Motivated by Question <ref>, we study the radius of Gaussian information which is equivalent to the radius of the intersection of $K$ with a random subspace of codimension $n$. We will be interested in the case of $m$ being much larger than $n$, say at least $m>2n$.

The study of the radius, or equivalently the diameter, of the section of a convex body with a linear subspace has its roots in the local theory of Banach spaces, see V. D. Milman <cit.>. Today, it is part of the field of asymptotic geometric analysis, where it is connected with low $M^*$-estimates, which will be discussed in Section <ref> as an important tool behind our bounds. With particular focus on subspace dimensions proportional to the dimension of the convex body, this was investigated, among others, by Giannopoulos and Milman <cit.>, also together with Tsolomitis <cit.>, and quite recently by Litvak, Pajor and Tomczak-Jaegermann <cit.>.

In <cit.> a random matrix perspective was employed to show that, on the scale of proportional subspaces, typical intersections of a symmetric convex body $K\subset \IR^m$ are not much larger than minimal intersections. More precisely, typical intersections of $K$ with $N$-codimensional random subspaces are at most a factor $C(\varepsilon)$ larger than the $n$-th Gelfand width $c_n(K)$ provided that $\chg{N/m>\varepsilon}$ and $N/n>1+\varepsilon$ for some fixed $\varepsilon>0$. This is an instance of the “existence versus prevalence” phenomenon mentioned in the introduction, see also <cit.>.

In contrast to <cit.>, where the knowledge of one minimal section suffices, Litvak and Tomczak-Jaegermann <cit.> obtained a bound on the radius of random section in terms of a suitable average over the tail of the sequence of minimal radii. To make this precise, define the random Gelfand numbers of the operator $\id\colon (\IR^m,\|\cdot\|_K)\to \ell_2^m$, that is the random Gelfand widths of $K$, for $1\le n\le m$, by

\begin{equation} \label{eq:crn-def}
\crn(K)
:=\inf\{a>0\colon \rad(K,E_{n-1}^{\rm ran})<a \},
\end{equation}

where in this relation a property holds for a random subspace $E_{n-1}^{\rm ran}$ of codimension $n-1$ if it is satisfied with exponentially high probability in $n$, that is, with probability at least $1-\chg{\exp\big(-\alpha_0(n+1)\big)}$ for a suitable $\alpha_0>0$ fixed beforehand.  Then, for not necessarily symmetric $K$, <cit.> yields constants $c,C>0$ such that the random Gelfand widths satisfy

\begin{equation}\label{eq:general-upper}
\crn(K)
\le C \frac{1}{\sqrt{n}}\sum_{j=\lfloor c\, n\rfloor}^{m} \frac{c_j(K)}{\sqrt{j}}, \quad 1\le n \le m.
\end{equation}

Recall that the Gelfand width $c_{n+1}(K)=\rad(K,n)$ is the minimal radius over $n$-codimensional sections of $K$, which is in turn equivalent to $r(K,n)$, the $n$-th minimal radius of linear information. It can be deduced from this bound that if the Gelfand widths decay at a polynomial rate faster than $n^{-1/2}$, then the random Gelfand widths are asymptotically equivalent to the Gelfand widths and Question <ref> can be answered in the positive. We will say more about this in the next section when we compare this bound to our results.

The bound in (<ref>) is very general but we do not have a matching lower bound. To increase our understanding, we will study concrete examples such as $\ell_p$-ellipsoids which generalize the usual ellipsoid

\begin{equation} \label{eq:ellipsoid}
\elz
:= \Big\{x\in\IR^m\colon \sum_{i=1}^{m} \frac{|x_i|^2}{\sigma_i^2}\le 1\Big\},
\end{equation}

with semiaxes $\sigma=(\sigma_1,\sigma_2,\ldots)$ of positive length. For the sake of motivation, we provide some details about the connection between the sections of ellipsoids and linear information for Hilbert space embeddings before introducing $\ell_p$-ellipsoids.

In the context of function spaces, ellipsoids appear in the study of a compact embedding of a Hilbert space into an $L_2$-space. This is well known and for example elaborated in <cit.>, see also Pinkus <cit.>. To give the details, let $S=\id\colon H\to K$ be a compact embedding between separable Hilbert spaces $H,K$. Then one can form an orthonormal basis $e_1,e_2,\ldots$ of $K$ using the normalized eigenfunctions of the compact selfadjoint operator $S^* S$ defined on $K$, where $S^*$ is the adjoint. The basis is assumed to be ordered such that the singular numbers $\sigma_j=\sqrt{\lambda_j}$ with $S^* S e_j=\lambda_j e_j$, where $j\in\IN$, satisfy $\sigma_1\ge \sigma_2\ge \cdots$. The unit ball in $H$ is then given by all functions $f=\sum_{j=1}^{\infty}a_j e_j$ with

\[
\|f\|_H
\le 1,
\]

that is an infinite dimensional ellipsoid.

Linear functionals on $H$ can then be identified with sequences and random information becomes a sequence of independent standard Gaussian random variables. It is known that optimal information using $n$ linear functionals is given by evaluating the first coefficients $a_j=\langle f,e_j\rangle_H$ and that the optimal algorithm is $A(f)=\sum_{j=1}^{n}\langle f,e_j\rangle_H e_j$, which is the projection onto the coordinates in which the ellipsoid is largest. Then the $n$-th minimal radius of linear information is given by the singular value $\sigma_{n+1}$, which is also the radius of the minimal section of $\elz$, i.e.,

\[
\rad(\elz,n)=r(\elz,n)=\sigma_{n+1}, \quad 0\le n <m.
\]

This is because sections of an ellipsoid are again ellipsoids and the diameter of an ellipsoid is twice its radius. Thus, we have equality in Proposition <ref> and consequently relation (<ref>) instead of the constant two, see, e.g., <cit.> or <cit.>.

In <cit.> the relation between random and minimal sections of an ellipsoid has been investigated and by <cit.> there exists an absolute constant $C>0$ such that

\begin{equation}\label{eq:upper-2}
\rad(\elz,\enran)
\leq C \frac{1}{\sqrt{n}}\Big(\sum_{j\ge \lfloor n/4\rfloor}\sigma_j^2\Big)^{1/2},\quad \text{for }1\le n<m,
\end{equation}

with exponentially high probability (in $n$). Similar to the bound (<ref>) it yields that the typical radius is asymptotically equivalent to the minimal radius provided the latter decays fast enough for increasing $n$.

However, if the semiaxes $\sigma=(\sigma_j)_{j\in\IN}$ decay too slowly and are not square-summable, that is $\|\sigma\|_2=\infty$, then the behaviour of the radii of typical sections changes completely. In this case, <cit.> yields that, for any $\varepsilon>0$,

\begin{equation} \label{eq:lower-2}
\rad(\mathcal{E}_{\sigma}^m,\enran)
\geq  (1-\varepsilon)\sigma_1
\end{equation}

with exponentially high probability, provided that $m$ is large enough compared to $n$.

Taken together, these bounds yield the following dichotomy on the behaviour of the radius of random information compared to the minimal radius of information. Namely, if $\|\sigma\|_2<\infty$, then the radius of random information, $r(\elz,G_{n,m})$, is close to optimal for all $m \, (>n)$. On the other hand, if not, then random information is asymptotically useless if $m \,(>n)$ is large enough. Both statements hold with exponentially high probability.

It should be noted that in <cit.> also an upper bound more suitable for exponentially decaying sequences of semiaxes was obtained, where one looses at most a polynomial factor. We will not consider this but focus our attention on polynomially decaying semiaxes later on.

We wish to extend the results about ellipsoids and investigate the above dichotomy for the more general $\ell_p$-ellipsoids, defined as follows.

An $m$-dimensional $\ell_p$-ellipsoid, $0< p\le \infty$, with semiaxes of length $ \sigma_1\ge \cdots \ge \sigma_m >0$ is given by

\[
\elp:=\Big\{x\in\IR^m\colon \sum_{i=1}^{m} \frac{|x_i|^p}{\sigma_i^p}\le 1\Big\},
\]

where the sum over the $p$-th powers is replaced by the maximum if $p=\infty$.

The $\ell_p$-ellipsoid $\elp$ is the unit ball of $\IR^m$ equipped with the (quasi-)norm

\begin{equation} \label{eq:psigma-norm}
\|x\|_{p,\sigma}
\text{}x\in\IR^m,
\end{equation}

and therefore it is convex if and only if $p\ge 1$. See Figure <ref> for an illustration.

Two-dimensional $\ell_p$-ellipsoids with semiaxes $\sigma_2=0.6\,\sigma_1$.

As a first motivation to study $\ell_p$-ellipsoids, consider the diagonal operator $D_{\sigma}$ with multiplier sequence $\sigma=(\sigma_1,\ldots,\sigma_m)$ taking $x\in\IR^m$ to $D_{\sigma}(x)=(\sigma_1x_1,\ldots,\sigma_m x_m)$. Then $\elp$ is the image of the $\ell_p$-unit ball $\IB_p^m$ under $D_{\sigma}$, and a change of variables shows that, for any linear subspace $E_n\subset \IR^m$,

\[
\rad(\elp,E_n)
=\sup_{\elp\cap E_n}\|x\|_2
=\sup_{\IB_p^m\cap E_n}\|D_{\sigma}x\|_2.
\]

By taking the infimum over all subspaces of codimension $n$ we obtain

\begin{equation} \label{eq:gelfand-diag}
\rad(\elp,n)
=c_{n+1}(D_{\sigma}\colon \ell_p^m\to \ell_2^m) \quad \text{for all }n\in\IN.
\end{equation}

This relation is used in Appendix <ref> to determine the minimal radius for the $\ell_p$-ellipsoids.

In the study of operators between (quasi-) Banach spaces, diagonal operators are important prototypes, in part due to their particular structure, and in part because some interesting operators act like them. For example, differential operators on periodic functions may be analyzed via diagonal operators applied to their Fourier coefficients, and also embeddings between Besov and Sobolev spaces can be modeled using them. We refer to Carl <cit.>, König <cit.>, Kühn <cit.>, Linde <cit.>, Pietsch <cit.> and Schütt <cit.> for detailed information on this topic.

Additionally, we would like to mention that $\ell_p$-ellipsoids have been studied quite recently by Juhos and Prochno <cit.> with focus on the asymptotic volume distribution of the intersection of two such generalized ellipsoids as the dimension of the underlying space tends to infinity, and by van Handel <cit.> as examples to investigate the intricacies of entropy bounds on the expected supremum of Gaussian processes.

To give more details, it has been observed by Talagrand in <cit.> that ellipsoids $\elz$ are examples where the generic chaining approach is superior to Dudley's bound on the expected supremum of a Gaussian process $(Z_t)_{t\in K}$ with $Z_t=\sum_{i=1}^{m}g_j t_j$, which is indexed by a convex body $K$, in terms of entropy numbers of $K$ is not optimal. Intuitively, this is because an ellipsoid is smaller than its entropy numbers suggest. As noted by van Handel <cit.>, this extends to $\ell_p$-ellipsoids. We will discuss this in the upcoming section.

At the end of this section, let us briefly present how $\ell_p$-ellipsoids relate to the following spaces of periodic functions, which were introduced by Sprengel <cit.> in order to generalize error estimates for interpolation using sparse grids.

For $1\le q \le\infty$ and $\alpha\in\IR$ define

\[
:=\Big\{f\in D'(\TT^d)\colon \|f\|_{A_q^{\alpha}(\TT^d)}:=\Big(\sum_{k\in\ZZ^d}\big|(1+\|k\|_2^2)^{\alpha/2}c_k(f)\big|^q\Big)^{1/q}<\infty\Big\},
\]

where $\big(c_k(f)\big)_{k\in\ZZ^d}$ are the Fourier coefficients of $f$ belonging to $D'(\TT^d)$, the space of periodic distributions on the $d$-dimensional torus $\TT^d$.

This scale of function spaces encompasses the Wiener algebra of periodic functions with absolutely summable Fourier coefficients ($q=1$ and $\alpha=0$) and periodic Sobolev spaces ($q=2$ and $\alpha\in\IN$). In one dimension, the case $q=\infty$ and $\alpha>1$ corresponds to Korobov spaces, whose multi-dimensional generalizations are integral to the study of lattice rules, see, e.g., Niederreiter <cit.>. In general, a description of the space $A_q^{\alpha}(\TT^d)$ in terms of smoothness is probably out of reach as already in one dimension there is no precise relation between smoothness and decay conditions on the Fourier coefficients.

To make precise how the function spaces of Definition <ref> are connected to $\ell_p$-ellipsoids, enumerate the integer points $k\in\ZZ^d$ by $\big(k(j)\big)_{j=1}^{\infty}$ such that their Euclidean norm is non-decreasing. Then, for every $f\in A_q^{\alpha}(\TT^d)$,	the sum defining its norm can be regrouped to

\[
\|f\|_{A_q^{\alpha}(\TT^d)}^q
=\sum_{j=1}^{\infty} \frac{|c_{k(j)}|^q}{\sigma_j^q}
\]

where $\sigma_j:=(1+\|k(j)\|_2^{2})^{-\alpha/2}$ for $ j\in \IN$. Thus, via the correspondence $f\leftrightarrow \big(c_k(f)\big)_{k\in\ZZ^d}$, the unit ball of $A_q^{\alpha}(\TT^d)$ may be identified with an infinite-dimensional $\ell_q$-ellipsoid. Then a straightforward volume estimate implies the asymptotic relation $\sigma_j\asymp j^{-\alpha/d}$, and if $\alpha/d>1-1/q=1/q^*$ or $\alpha=0$ and $q=1$, then $A_q^{\alpha}(\TT^d)$ is embedded into the continuous functions. Curiously enough, we will encounter this condition on the semiaxes in our study of the behaviour of the radius of a random section.

§ DISCUSSION OF RESULTS

Having sufficiently motivated the study of sections of $\ell_p$-ellipsoids with random subspaces, we discuss our results obtained in <cit.>. We first state a general upper bound on the radius $\rad(\elp,\enran)$ of a random section for $1\le p\le\infty$ (Theorem <ref>), which we compare with the bound of (<ref>) given in <cit.>. Then we discuss Corollary <ref> which extends a bound on the supremum of a Gaussian process indexed by an $\ell_p$-ellipsoid obtained by van Handel <cit.>. Afterwards an upper bound on the typical radius (Theorem <ref>) obtained in the range $0<p<1$ together with a consequence (Corollary <ref>) for the Gelfand numbers of diagonal operators is presented.

In Section <ref> we shall discuss ramifications for polynomial semiaxes. We shall also state a lower bound (Proposition <ref>) and discuss a dichotomy for the optimality of Gaussian information depending on the decay of the semiaxes. This leads us to Conjecture <ref>.

The following main result bounds the typical radius from above via the $p^*$-norm of the tail of the sequence of semiaxes. Here and in the following, the parameter $p^*$ is the Hölder conjugate of $p$, that is $\frac 1p +\frac{1}{p^*}=1$.

There exists a constant $C>0$ such that, for all $m\in\IN$ and $1\le n<m$, we have

\[
\rad(\elp,\enran)
\le C
\begin{cases}
n^{-1/2}\sup\limits_{k\le j\le m}\sigma_{j}\sqrt{\log(j)+1} &\text{if } p=1, \\
\sqrt{p^*}n^{-1/2} \Big(\sum\limits_{j=k}^{m}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}} &\text{if } 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=k(n)\asymp n$ for $p=1$ while $k=k(n)\asymp \frac{n}{p^*}$ for $p>1$.

The proof will be discussed in Section <ref>.

The notation we use here is different from <cit.>, where we used $\rad$ also for the radius of information and the radius of Gaussian information $r(\elp,G_{n,m})$. Here, the radius of a typical section $\rad(\elp,\enran)=\rad(\elp,\ker G_{n,m})$ is used to state the results. However, by Proposition <ref> these notions are equivalent up to a constant of two if $p\ge 1$ and a constant depending on $p$ otherwise. To see this, note that $\elp$ is the unit ball of $\IR^m$ equipped with $\|\cdot\|_{p,\sigma}$, which satisfies, by the $p$-triangle inequality,

\[
\|x+y\|_{p,\sigma}\le 2^{(1/p-1)_+}\big(\|x\|_{p,\sigma}+\|y\|_{p,\sigma}\big)\quad\text{for every }x,y\in\IR^m.
\]

Theorem <ref> canonically extends the bound (<ref>) obtained in <cit.> for the case $p=2$ and shows that if $\sigma\in \ell_{p^*}$ we get a bound on the radius of most sections. In order to compare this with the more general upper bound (<ref>) from above, obtained by Litvak and Tomczak-Jaegermann in <cit.>, we introduce the following concept. Similar to <cit.> we will be interested in bounds which are independent of the dimension $m$ and may be extended to infinite $m$.

Let $0<p,q\le \infty$. The Lorentz (quasi-)norm of a (possibly finite) sequence $x=(x_1,x_2,\dots)$ is given by

\[
\|x\|_{p,q}
\]

where $x_1^*\ge x_2^*\ge\cdots$ is the non-increasing rearrangement of $(|x_i|)_{i=1}^{\infty}$, see, e.g., <cit.>.

For convenience let us recall that (<ref>) yields

\begin{equation*}
\crn(\elp)
\le C \frac{1}{\sqrt{n}}\sum_{j=\lfloor c\, n\rfloor}^{m} \frac{c_j(\elp)}{\sqrt{j}}, \quad \text{for all }n\in\IN
\end{equation*}

with exponentially high probability in $n$.

To compare this with the upper bound of Theorem <ref>, we need to know the behaviour of the Gelfand widths $\big(c_n(\elp)\big)_{n\le m}$ or, equivalently, the minimal radius of information. Due to equality (<ref>), we can use results about Gelfand numbers of diagonal operators to infer the behaviour of $	\big(c_n(\elp)\big)_{n\le m}$ in terms of the sequence of semiaxes $\sigma$. We collect these results in Appendix <ref> and note that for $p<2$ one knows this behaviour only to polynomial order.

The bound in (<ref>) is finite for all $m\in\IN$ if and only if $\big(c_n(D_{\sigma}\colon \ell_p\to\ell_2)\big)_{n\in\IN}\in \ell_{2,1}$. From Proposition <ref> in Appendix <ref> one can deduce that for $p\ge 2$ this holds if and only if $\sigma\in \ell_{p^*,1}$. This is a stronger requirement than $\sigma\in \ell_{p^*}$, which is needed by Theorem <ref> for a finite upper bound independent of $m$.  Note that this observation is already true for $p=2$ and thus could have been made after the statement of (<ref>).

Let us elaborate. For $p=2$ the semiaxes coincide with the minimal radii, i.e., we have $\sigma_{n+1}=\rad(\mathcal{E}_\sigma^m,n)$. If $r(\elz,n)\asymp n^{-\lambda}(\log n)^{\alpha}$ for $\lambda>1/2$ and $\alpha\in \IR$ both (<ref>) and (<ref>) imply that the radius of a random section satisfies

\begin{equation} \label{eq:ell-answer}
\rad(\elz,\enran)\lesssim \rad(\elz,n)
\end{equation}

with exponentially high probability, i.e., we have asymptotic optimality of random information. If $\lambda=1/2$ and $\alpha<-1/2$, then the bound (<ref>) gives (<ref>) with an additional factor of $\sqrt{\log n}$ on the right-hand side.  This improves upon the general bound (<ref>) by a factor of $\sqrt{\log n}$. A slightly smaller improvement of $(\log n)^{1/p}$ may be deduced in the case of $p>2$ and $\alpha<-1+1/p$ from Theorem <ref> and Proposition <ref>.

Summarizing, we may say that, applied to $\ell_p$-ellipsoids $\elp$ with $1\le p\le \infty$ and $ m\in\IN$, the bound (<ref>) is in general slightly weaker than Theorem <ref>. However, we wish to emphasize that the bounds differ only at an logarithmic scale and for comparing the polynomial order, as done in Section <ref>, they are of equal strength.

As a consequence of the proof of Theorem <ref>, more precisely of Proposition <ref> in Section <ref> below, we obtain the following corollary on the supremum of a Gaussian process indexed by an $\ell_p$-ellipsoid.

Let $g_1,g_2,\dots$ be independent standard Gaussians. Then there exists a constant $C>0$ such that, for all $m\in\IN$,

\[
\IE\sup_{y\in \elp}\sum_{j=1}^{m}g_j y_j
\le C
\begin{cases}
\sup\limits_{1\le j\le m}\sigma_{j}\sqrt{\log(j)+1} &\text{if } p=1, \\
\sqrt{p^*} \big(\sum\limits_{j=1}^{m}\sigma_{j}^{p^{*}}\big)^{1/p^{*}} & \text{if }1<p\le\infty.
\end{cases}
\]

In view of the dependence on the parameter $p$, this bound extends the mentioned work by van Handel <cit.> who deduced it for $1\le p <\infty$ but with an unspecified constant in $p$ which cannot be obtained using his approach, see <cit.>. In Corollary <ref>, we obtain an upper bound on the behavior in $p$ and thus complement his result.

Employing estimates for entropy numbers of diagonal operators from <cit.> as in <cit.>, it can be deduced that the $\ell_p$-ellipsoid $\elp$ 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\IN}\sigma_{j}\sqrt{\log(j)+1}<\infty\text{ but }\sigma\not\in\ell_{\infty,1}
\]

is an example where Dudley's bound, in contrast to Corollary <ref>, fails to give a finite bound if the dimension becomes large. In the case $1<p<\infty$, van Handel explains this with the fact that the entropy numbers need not be estimated for the whole set but for certain thin subsets, in this case dilations of $\ell_{2p-2}$-ellipsoids. For $p\ge 2$ an alternative explanation can be given in terms of $p$-convexity, see <cit.>. Note that in finite dimension Dudley's bound can be off by at most $\log m$, see <cit.>.

Regarding the case $0<p<1$, it seems that little is known in general about random sections of unit balls of quasi-Banach spaces and different techniques are necessary than in the case of convex bodies.  Relying on methods commonly used in the field of compressed sensing, e.g., in a work of Foucart, Pajor, Rauhut and T. Ullrich <cit.> on the Gelfand widths of $\ell_p$-balls in the quasi-Banach regime, see also Donoho <cit.>, we deduce the following upper bound for the radius of random information when the semiaxes have polynomial decay.

Let $0<p\leq 1$ and $\sigma_j=j^{-\lambda}$, $j\in\IN$, for some $\lambda>0$. Then there exist constants $c,C,D>0$ such that, for all $m\in\IN$ and all $1\le n <m$ with

\[
n\ge D\log({\rm e}m/n),
\]

we have

\[
\rad(\elp,\enran)
\le C\,\Big(\frac{\log({\rm e}m/n)}{n}\Big)^{\lambda+1/p-1/2}
\]

with probability at least $1-2\exp(-c\, n)$.

To the best of our knowledge, this seems to be the best known upper bound for the minimal radius of sections of $\ell_p$-ellipsoids with $0<p<1$ and thus the best information available is given by random Gaussian measurements. Below, we shall prove the more general Theorem <ref>, where the radius is measured in the $\ell_q$-quasi-norm for $p<q\le 2$. This yields the following bound on Gelfand numbers of diagonal operators in the quasi-Banach regime and extends known results on the identity between $\ell_p^m$ and $\ell_q^m$ from the mentioned works <cit.> and <cit.>.

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

\[
n\ge D\log({\rm e}m/n),
\]

we have

\[
c_{n+1}(D_{\sigma}\colon \ell_p^m\to \ell_q^m)
\le C\, \Big(\frac{\log({\rm e}m/n)}{n}\Big)^{\lambda+1/p-1/q}.
\]

§ DISCUSSION OF RESULTS – POLYNOMIAL SEMIAXES

In the following, we discuss the consequences of our results for $\ell_p$-ellipsoids with $1\le p\le \infty$ and polynomially decaying semiaxes. Our main reason for doing so is to be able to compare the minimal radius $\rad(\elp,n)$ with the radius of typical sections $\rad(\elp,\enran)$ and to make progress towards extending the dichotomy for the ellipsoids $\elz$ mentioned in Section <ref>. We give some further motivation to look at polynomial semiaxes.

An incentive can be seen in the function spaces $A_q^{\alpha}(\TT^d)$ of Definition <ref>, whose unit ball can be identified with an infinite-dimensional $\ell_q$-ellipsoid with semiaxes $\sigma_j\asymp j^{-\alpha/d}$. Let us mention here that Theorem <ref> can be applied to this sequence if and only if $\alpha/d>1/p^*$. In this case, one could use an isomorphism to obtain a bound on random linear information for the spaces $A_q^{\alpha}(\TT^d)$.

For the sake of further motivation, let us mention that the unit ball of $\IR^m$ equipped with the Lorentz (quasi-)norm $\|\cdot\|_{p,q}$ bears some similarity to an $\ell_q$-ellipsoid with semiaxes $\sigma_j=j^{1/q-1/p}$. Under the assumption that the coefficients are ordered non-increasingly, one may interpret recovery of functions whose Fourier or wavelet coefficients belong to a Lorentz ball as a possible application of our results. This includes for example nonlinear approximation classes, in part related to Besov spaces, see for example <cit.>.

Let now $\sigma_j=j^{-\lambda}$ for all $j\in\IN$ and some $\lambda>0$. Equivalent results hold if this is weakened to $\sigma_j\asymp j^{-\lambda}$. In order to assess the size of the radius of a typical section of $\elp$, we need to know the minimal radius $\rad(\elp,n)$ for all $n\in\IN$.  Its behavior is known exactly when $p\ge 2$ but can only be deduced up to subpolynomial factors when $1\le p<2$, see Appendix <ref>. Therefore, we will ignore subpolynomial terms in the following discussion and use only the rate of polynomial decay to compare.

To make this precise, we define the rate of polynomial decay (in $n$) of an infinite array $a=(a_{n,m})_{m\in\IN,1\le n <m}$ of real numbers by

\[
\decay(a)
:=\sup\{\varrho\ge 0\colon \exists C>0 \text{ with }a_{n,m}\le C\, n^{-\varrho} \text{ for all }m\in\IN \text{ and }1\le n<m\}.
\]

This definition is derived from the concept of a diagonal limit order used to study Gelfand numbers of diagonal operators arising from a polynomially decaying sequence, see, e.g., Pietsch <cit.>.

Further, we need to suppose that $\sigma_j=j^{-\lambda}$, $j\in\IN$, for some

\[
\lambda>\frac{1}{s}:=\Big(\frac{1}{2}-\frac{1}{p}\Big)_+=\max\Big\{\frac{1}{2}-\frac{1}{p},0\Big\},
\]

since the minimal radius does not decay if $\lambda\le \frac{1}{s}$. For the decay rate of the minimal radius Corollary <ref> implies

\begin{equation}\label{eq:min-order}
\decay\big(\rad(\elp,n)\big)
=	\begin{cases}
\lambda\cdot\frac{p^{*}}{2}&\text{if } 1\le p<2 \text{ and }\lambda<\frac{1}{p^{*}},\\
\lambda+\frac{1}{p}-\frac{1}{2}&\text{otherwise.}
\end{cases}
\end{equation}

By Theorem <ref>, if $\sigma$ decays polynomially with exponent $\lambda>\frac{1}{p^*}$, then there is $C>0$ such that the radius of a random section satisfies, for every $m\in\IN$ and $1\le n<m$,

\begin{equation}\label{eq:bound-polynomial}
\rad(\elp,\enran)
\le C
\begin{cases}
n^{-\lambda-1/2}\sqrt{\log n}&\text{if }p=1,\\
n^{-\lambda+1/2-1/p}&\text{if }1<p\leq \infty,
\end{cases}
\end{equation}

with probability $1-c_1\exp(-c_2 n)$.

Similar to the above, let us define $\decay\big(\rad(\elp,\enran)\big)$ to be the supremum over all $\varrho\ge 0$ such there exist $C,C_1,C_2\in (0,\infty) $ such that
\rad(\elp,\enran)\le C n^{-\varrho}
holds with probability at least $1-C_1\exp(-C_2n)$ for all $m\in\IN$ and $1\le n <m$. This notion is somewhat related to the notion of the random Gelfand widths.

Then the combination of (<ref>) and (<ref>) implies, for $1\le p\le\infty$ and $\lambda>\frac{1}{p^*}$,

\begin{equation}\label{eq:ran-order}
\decay\big(\rad(\elp,\enran)\big)
=	\lambda+\frac{1}{p}-\frac{1}{2}
=	\decay\big(\rad(\elp,n)\big).
\end{equation}

That is, the rate of decay of random information is equal to the one of optimal information which provides a positive partial answer to Question <ref> for $\ell_p$-ellipsoids with polynomially decaying semiaxes.

Therefore, the bound of Theorem <ref> yields an optimal bound on the rate of polynomial decay of typical sections in the case of $\lambda>\frac{1}{p^*}$. However, if $\lambda\le \frac{1}{p^*}$, it does not yield a useful result. Instead, we have the following lower bound on the radius of a random section if $1< p\le 2$ and $m$ is large enough compared to $n$.

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

\[
\IP\Big[\rad( \elp,\enran)\ge \frac{1}{2}\Big]
\ge 1-\varepsilon.
\]

In other words, if $1< p\le 2$ and the semiaxes decay too slowly compared to $\frac{1}{p^*}$, random information is asymptotically as good as no information at all, that is, its radius does not decay as the following corollary summarizes in terms of random sections.

Let $1\le p\le 2$ and $\sigma_j=j^{-\lambda},j\in\IN$, for some $\lambda$ with $0<\lambda<\frac{1}{p^*}$. Then

\[
\decay\big(\rad(\elp,\enran)\big)=0.
\]

We visualize $\decay\big(\rad(\elp,\enran)\big)$, or equivalently the rate of decay of the radius of random information, in Figure <ref> and discuss it in the following.

[lgrey] (0,0) – (0,.35) – (0.35,0) – (0,0);
[->] (0,-.1) – (0,1) node [midway,xshift=-10pt,yshift=-10pt]$\frac{1}{2}$ node [near end,xshift=-10pt,yshift=0pt]$1$ node [at end,xshift=-10pt,yshift=0pt]$\lambda$ ;
[->] (-.1,0) – (1,0) node [midway,yshift=-10pt,xshift=-10pt]$\frac{1}{2}$ node [near end,yshift=-10pt,xshift=0pt]$1$ node [at end,xshift=3pt,yshift=-10pt]$\frac{1}{p}$;
(0,.7) – (.7,0);
(0,0) rectangle (.35,.35);
[dashed] (0,.35) – (.35,0);
[dashed] (.7,0) – (.7,1) node [at end,yshift=5pt]$p=1$;
at (.35,.75) $\lambda+\frac{1}{p}-\frac{1}{2}$;
at (.12,.44) $?$;
at (.27,.27) 0;
at (.47,.10) 0;
(0,0) rectangle (0.35,.35);

This diagram depicts our knowledge about $\decay\big(\rad(\elp,\enran)\big)$ in the $\frac{1}{p}-\lambda$-plane, where $0< p,\lambda\le \infty$ and $\sigma_j=j^{-\lambda},j\in\IN$.

Above the line $\lambda=1-\frac{1}{p}$, where $ 1\le p\le\infty,$ we just deduced that Theorem <ref> 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 (<ref>). As noted above, below and including the line $\lambda=\frac{1}{2}-\frac{1}{p}$, where $ 2\le p\le\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 $\elp$ has a radius bounded from below.

In the square, that is for $p\ge 2$ and $\lambda\le\frac{1}{2}$, it follows via $\elz\subset \elp$ from the lower bound (<ref>) for the case $p=2$ that, no matter how large we choose $n$, if $m$ is large enough, then with high probability $\rad(\elp,\enran)$ is bounded from below by a constant.  That is, $\decay\big(\rad(\elp,\enran)\big)=0$ and so random information is useless. By Corollary <ref> this also holds for the triangle given by $1< p<2$ and $0<\lambda<1-\frac{1}{p}$.

Finally, note that on the right-hand side of the dashed line where $p=1$, that is, where $0<p<1$, Theorem <ref> 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.

Let $1\le p\le\infty$ and $\sigma_j=j^{-\lambda},j\in\IN,$ with $\lambda>\frac{1}{s}$. Then,

\[
\decay\big(\rad(\elp,\enran)\big)=
\begin{cases}
\decay\big(\rad(\elp,n)\big)
&\text{if }\lambda>\frac{1}{p^*},\\
0&\text{if }\lambda\le\frac{1}{p^*}.
\end{cases}
\]

In fact, this dichotomy may also be true more generally for non-polynomial semiaxes depending on whether $\|\sigma\|_{p^*}<\infty$ or not, see Question <ref> in Section <ref>.

§ LOW $M^*$-ESTIMATES AND THE ROUNDING OF ELLIPSOIDS

In this section we will explain how Theorem <ref> follows from a (low(er)) $M^*$-estimate using a rounded version of the $\ell_p$-ellipsoid $\elp$. To illustrate the ideas behind this approach, which has been used already in <cit.>, and in a similar form also in <cit.> (and many other papers), we will consider a general convex body $K\subset \IR^m$.

As mentioned, unit balls of normed spaces and in particular the $\ell_p$-ellipsoids, where $1\le p\le \infty$, are examples of convex bodies, and additionally symmetric. In the following, $K$ need not be symmetric but for convenience we assume that it contains the origin in its interior.

A well-known type of result in the field of asymptotic geometric analysis is the low $M^*$-estimate, which consists of an estimate of the radius of the intersection of $K$ with a random subspace in terms of its mean width and a factor depending on the proportion of the dimension of subspace. Let us introduce the necessary notions and give a formal statement together with some history.

The mean width of $K$ measures the average width of $K$ over all directions belonging to the sphere $\IS^{m-1}=\{x\in \IR^m\colon \|x\|_2=1\}$. To formally define it, let $h_{K}\colon \mathbb S^{m-1}\to\IR$, $u\mapsto\sup_{y\in K}\langle u,y\rangle$ be the support function of $K$, which measures the distance from the origin of the supporting hyperplane in direction $u$. That is, the width into direction $u$ is given by $h_K(u)+h_K(-u)$. The (half) mean width of $K$ is then

\begin{equation} \label{eq:mean-width}
:=\int_{\mathbb S^{m-1}}h_{K}(u)\,\dd\sigma^{m-1}(u),
\end{equation}

where $\sigma^{m-1}$ is the normalized surface measure on $\mathbb S^{m-1}$. Intuitively, this is the expected radius of a one-dimensional random subspace.

Using the probabilistic representation of the uniform measure on $\mathbb S^{m-1}$ in terms of standard Gaussians (see Section <ref>) shows that $M^*(K)$ can be written as the supremum of a Gaussian process (see, e.g., <cit.>), namely,

\begin{equation}\label{eq:mstargaussian}
= \frac{1}{c_m} \IE \sup_{t\in K}\sum_{j=1}^{m}t_j g_j,
\end{equation}

where $g_{1},g_{2},\ldots$ are independent standard Gaussian random variables and $c_m\asymp \sqrt{m}$.

We will state now a form of the lower $M^*$-estimate as presented in <cit.> with $\gamma=\frac{1}{2}$ there.

Let $K\subset\IR^{m}$ be a convex body containing the origin in its interior. For any $1\le 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

\[
\|x\|_{2}\le 2\frac{a_{m}}{a_{n}}M^{*}(K),
\]

where, for each $k\in\IN$,

\begin{equation}\label{eq:asymptotic ak}
\asymp \sqrt{k}.
\end{equation}

Thus it implies

\[
\rad(K,\enran)
\le 2\frac{a_{m}}{a_{n}}M^{*}(K),
\]

for the random subspace $\enran$ with the claimed probability.

The statement of Proposition <ref> is adapted from Gordon <cit.> who proved it using a min-max principle to derive a result on subspaces escaping through a mesh. In <cit.> and <cit.> one may find some history starting with V. D. Milman <cit.>. In particular, Gordon's result improves upon the work <cit.> due to Pajor and Tomczak-Jaegermann who obtained a larger constant. In fact, this would be sufficient for our purposes as we do not care about the size of the absolute constants.

As in the mentioned works <cit.>, <cit.> and <cit.>, see  also <cit.>, we use the technique of rounding to improve the power of the low $M^*$-estimates as follows. Define the rounded body by

\[
K_{\varrho}:=K\cap \varrho\IBo_2^m=\{x\in K\colon \|x\|_2\le \varrho\},
\]

where $\varrho>0$ is some cutoff threshold. The idea to obtain a bound on the radius of the section with the random subspace $\enran$ is then to derive a bound on $M^*(K_{\varrho})$ for an unspecified $\varrho>0$, which gives by the $M^*$-estimate a bound on $\rad(K_{\varrho}, E_n)$ for most realizations $E_n$ of $\enran$, and to afterwards minimize over all $\varrho>0$ such that

\begin{equation} \label{eq:rounding}
\rad(K_{\varrho}, E_n)<\varrho\quad\text{and consequently}\quad \rad(K, E_n)< \varrho
\end{equation}

holds for these subspaces. The improvement in this case comes from the fact that we can decrease the mean width $M^*(K_{\varrho})$ by decreasing $\varrho$ and thus cut off the peaky parts of $K$, which are somewhat irrelevant to random subspaces.

For the proof of Theorem <ref> we apply this technique to the $\ell_p$-ellipsoid $\elp$ which results in cutting away the contribution of the first $cn$ semiaxes, where  $0<c<1$.  This will be a consequence of the following proposition.

Let $m\in\IN$. For any $0\le k< m$ and $\varrho>0$,

\[
M^{*}(\elp\cap \varrho \IB_{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) &\text{if } 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) &\text{if } 1< p\le \infty.
\end{cases}
\]

This follows from an application of Hölder's inequality together with estimates on the norm of a Gaussian vector. A similar approach was used by Gordon, Litvak, Mendelson and Pajor in <cit.> for estimating the supremum of a Gaussian process indexed by the intersection of the $\ell_p$-ball $\IB_p^m$ with a scaled $\ell_q$-ball $\varrho\IB_q^m$. Using a suitable cutoff $\varrho>0$, which we will not attempt to optimize, one can obtain from Proposition <ref> the proof of Theorem <ref>. The details are deferred to Appendix <ref>.

Now, Corollary <ref> follows from Proposition <ref> by setting $k=0$ and $\varrho>0$ large enough such that $\elp\subset \varrho \IB_{2}^m$ together with the representation (<ref>) of the expected supremum of a Gaussian process indexed by a convex body.

§ A LOWER BOUND

The idea behind the proof of the lower bound of Proposition <ref> for polynomial semiaxes in the case $1< p\le 2$ is as follows. To bound the radius of $\elp$ intersected with a random subspace from below, we have to find with a certain probability a vector in it which has large enough norm. In fact, it is often even possible to find a vector having a single large coordinate with high probability as the following observation made in <cit.> shows.

For any $\varepsilon\in (0,1)$ it holds that, for all $m\in\IN$ and $1\le n< m$,

\[
\IP\Big[\sup\big\{ x_1^2\colon \|x\|_2=1, G_{n,m}x=0\big\}\ge 1-\frac{n}{\varepsilon m}\Big]
\ge 1-\varepsilon.
\]

Using this, we can prove the following more general version of Proposition <ref>.

Let $1< p\le 2$. For any $\varepsilon\in (0,1)$, all $m\in\IN$ and $1\le n< m$ with $n\le \varepsilon\sigma_m^2 m^{2/p^*}$ we have

\[
\IP\Big[\rad(\elp,\enran)\ge \frac{\sigma_1}{1+\sigma_1}\Big]
\ge 1-\varepsilon.
\]

In order to prove Proposition <ref> we take a random vector as given by Lemma <ref> which belongs to the intersection of the unit sphere with the kernel of $G_{n,m}$  and has a large first coordinate. Then we show using Hölder's inequality that the renormalization by the factor $1+1/\sigma_1$ lies in $\elp$ provided that the dimension $m$ is large enough compared to $n$ when $\sigma_m m^{1/p^*}$ is increasing. For details we refer to Appendix <ref>.

In the case $p=2$ this method yields bounds which are optimal with respect to polynomial order, see <cit.>. The restriction to $1\le p\le 2$ is due to Hölder's inequality and different ideas seem to be necessary for the case $p>2$. We do not know if also there it is sufficient to exhibit vectors with a single large coordinate but we believe that this may be true. A possible approach could consist in finding a variant of Lemma <ref> where the sphere is replaced by the surface of the cube.

From Proposition <ref> it can be deduced that the statement of Proposition <ref> remains true in the case of $\sigma_j=j^{-1/p^*}a_j, j\in\IN,$ with $a_j\to \infty$ as $j\to \infty$.

In <cit.> both bounds (<ref>) and (<ref>) were proven using random matrices. In particular, knowledge on the singular values of structured Gaussian matrices was employed and the Hilbert space structure was used in a crucial way. This is the reason why we could not extend the method they used without the loss of additional factors in the dimension $m$. Perhaps, new results on structured Gaussian random matrices may be of help, see, e.g., Guédon, Hinrichs, Litvak and Prochno <cit.>.

§ SPARSE APPROXIMATION

In order to describe the ideas behind the proof of Theorem <ref>, we give a short introduction to a subfield of compressed sensing, known as sparse approximation or recovery. We refer to the book of Foucart and Rauhut <cit.> for a mathematical background on the subject.

It is in part due to random matrices that sparse recovery experienced a relatively recent surge of interest. The seminal papers of Candès, Romberg and Tao <cit.> and Donoho <cit.> were among the first to investigate this and found that random matrices satisfy with high probability the restricted isometry property which enables exact reconstruction of sparse vectors. Further, an universality principle has been discovered, namely, random matrices can be used to gather measurements which are effective independently of the basis with respect to which a signal is sparse.

The fact that random information is the best information available for many problems in sparse recovery is reflected in the statement of Theorem <ref> which will be deduced from the more general Theorem <ref> below. To this end, let us give some background on sparse approximation.

Let $m,s\in\IN$ with $1\le s \le m$. A vector $z\in\IR^m$ is called $s$-sparse if at most $s$ of its coordinates are non-zero.  Given information $N_n z =y$, where $N_n\in \IR^{n\times m}$ is a suitable linear information map, sparse vectors can be reconstructed via $\ell_p$-minimization, where $0<p\le 1$, that is,

\begin{equation} \label{eq:ellp-min}
\Delta_p(y):= \text{arg min} \|z\|_p \quad \text{subject to }N_n z=y.
\end{equation}

Note that $\Delta_p$ is a map from $\IR^n$ to $\IR^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

\begin{equation} \label{eq:rip}
\le \|Az\|_2^2
\le (1+\delta)\|z\|_2^2 \quad \text{for all }2s\text{-sparse }z\in\IR^m,
\end{equation}

then $s$-sparse vectors $z\in\IR^m$ can be recovered exactly, i.e., $z=\Delta_p(N_n z)$. This is a consequence of the next proposition which gives a bound on the error of reconstruction using $\ell_p$-minimization in terms of the following concept.

Given $0<p\le \infty$, the error of best $s$-term approximation of $x\in \IR^m$ in the $\ell_p$-(quasi-)norm is

\[
\sigma_s(x)_p := \inf\{\|x-z\|_p \colon z \text{ is }s\text{-sparse}\}.
\]

If $0<p\le 1$ and $N_n$ satisfies the restricted isometry property with constant $\delta_{2s}<\sqrt{2}-1$, then, for all $x\in\IR^m$,

\[
\|x-\Delta_p(N_nx)\|_p\le C^{1/p} \sigma_s(x)_p,
\]

where $C>0$ is a constant that depends only on $\delta_{2s}$. In particular, the reconstruction of $s$-sparse vectors is exact.

The restricted isometry property can be interpreted as a condition of uniformity on the information map $N_n$, which is satisfied by a rescaling of the Gaussian matrix $G_{n,m}=(g_{ij})_{i=1,j=1}^{n,m}$ with high probability as the following result shows.

For every $\delta\in(0,1)$ there exist $C_1,C_2>0$ such that for all $m\in\IN$ the restricted isometry property $\delta_{s}(n^{-1/2}G_{n,m})\le \delta$ holds with probability at least $1-2\exp(-C_2 n)$ provided that
n\ge C_1 s \log({\rm e}m/s).

In fact, the statement is more general and applies also to subgaussian random matrices, see also Remark <ref>. Taken together, Propositions <ref> and <ref> show that, provided that enough, in fact not much more than the number of its non-zero entries if $m$ is not too large compared to $n$,  Gaussian measurements are available, a sparse vector can be reconstructed exactly with high probability using $\ell_p$-minimization. Together with the following lemma this completes the proof strategy for Theorem <ref>.

Let $m\in\IN$, $0<p,q\leq\infty$ and $\sigma_j=j^{-\lambda}$, $1\leq j \leq m$,  for some $\lambda>(1/q-1/p)_+$. Then, for all $1\le s\le m/2$,

\[
\sup_{x\in\elp}\sigma_s(x)_q
\asymp s^{-\lambda+1/q-1/p},
\]

where the implicit constant is independent of $s$ and $m$.

Its proof, given in Appendix <ref>, is inspired by the proof for the $\ell_p$-balls which can be found in Vybíral <cit.>.

To state the afore mentioned generalization of Theorem <ref>, where we measure the radius in the quasi-norm of $\ell_q^m$ instead of $\ell_2^m$, we define the radius $\rad_G(K,E)$ of the section of any set $K\subset \IR^m$ with a linear subspace $E\subset\IR^m$ in $G$ by

\[
\rad_G(K,E):=\sup_{x\in K\cap E}\|x\|_G,
\]

where $G$ is equipped with a quasi-norm $\|\cdot\|_G$. By Proposition <ref> it is related to the radius of information for recovery of vectors in $K$ in $\|\cdot\|_G$.

Let $0<p\leq 1$ and $p<q\le 2$. Assume that $\sigma_j=j^{-\lambda}$, $j\in\IN$, for some $\lambda>0$. Then there exist constants $c,C,D>0$ such that, for all $m\in\IN$ and all $1\le n <m$ with

\[
n\ge D\log({\rm e}m/n),
\]

we have

\[
\rad_{\ell_q^m}(\elp,\enran)
\le C\, \Big(\frac{\log({\rm e}m/n)}{n}\Big)^{\lambda+1/p-1/q}
\]

with probability at least $1-2\exp(-c\, n)$.

The proof of this theorem is a straightforward adaption of the proof of <cit.> and relies on Lemma <ref> as well as other techniques from sparse recovery. Again, details are provided in Appendix <ref>.

Our original proof of Theorem <ref> as given in the preprint <cit.> used $\ell_r$-minimization with $r=p$ which does not yield the claimed bound without additional modifications. Instead of giving a corrected version of this variant, we can set $r=\min\{1,q\}$ as in the proof of <cit.> since Lemma <ref> is more general than <cit.>. To keep the presentation self-contained, we give a complete proof instead of only stating the required modifications.

§ OPEN QUESTIONS

As mentioned in Section <ref>, knowledge of a single minimal section may imply a bound on typical sections of similar dimension which is in contrast to (<ref>), derived from <cit.>, where knowledge of the whole sequence $\big(c_n(K)\big)_{1\le n\le m}$ is needed. This difference has been observed at the end of Section 1.2 in <cit.> by E. Milman and Yifrach, who stated that it can be expected that knowledge of the whole sequence of minimal radii is needed to obtain good upper bounds, but a precise formulation is unavailable.

Is the knowledge of the whole sequence of Gelfand widths necessary to obtain an optimal bound on the radius of a random section?

To the best of our knowledge, general lower bounds on the radius of typical information or the random Gelfand widths, which could complement the upper bound (<ref>), are not available. Related to Question <ref> we pose the following one.

Can the upper bound (<ref>) be improved? What about lower bounds?

It would be interesting to have for example a negative statement if the Gelfand widths are not square-summable. We hope that our study of $\ell_p$-ellipsoids sheds some light on these questions.

As discussed in Section <ref>, Conjecture <ref> is verified except for the two cases

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

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

Can one prove Conjecture <ref> or find counterexamples to it?

It seems reasonable to conjecture even that $\decay\big(\rad(\elp,\enran)\big) = \decay\big(\rad(\elp,n)\big)$ as long as $\|(\sigma_j)_{j\in\IN}\|_{p^*}<\infty$, while $\decay\big(\rad(\elp,\enran)\big)=0$ whenever $\|(\sigma_j)_{j\in\IN}\|_{p^*}=\infty$. With an eye on the case $p=2$, it may also be true that the threshold is determined by the square-summability of the sequence of minimal radii or Gelfand widths.

In Corollary <ref> we obtained an upper bound on the dependence on $p$ of the supremum of a Gaussian process indexed by $\elp$. As we do not have a corresponding lower bound, the following would be interesting to know.

What is the correct dependence in Corollary <ref> on $p$?

A possible approach could be based on the equality case in Hölder's inequality used for the proof. See also <cit.>, where lower bounds on the mean width are provided.

If $0<p<1$, we do not have a lower bound on the minimal radius of information and therefore cannot compare typical with optimal information.

How sharp is Theorem <ref> or its extension Theorem <ref>?

We comment on a possible approach to a lower bound to Theorem <ref> or Theorem <ref> and more generally a lower bound on the Gelfand numbers of diagonal operators in the quasi-Banach regime. In the case of the $\ell_p$-balls, that is  $\sigma_1=\cdots=\sigma_m$, a matching lower bound is provided in <cit.>. Its proof relies on a combinatorial lemma providing a partially overlapping covering of the index set $\{1,\ldots,m\}$ and does not extend to $\ell_p$-ellipsoids with decaying semiaxes.

In <cit.> the authors had to find a different method of proof than the one used by Donoho <cit.> who relied on the validity of Carl's inequality, which compares entropy numbers with Gelfand numbers, in quasi-Banach spaces. However, this was only shown several years later by Hinrichs, Kolleck and Vybíral <cit.>. With this additional knowledge one could possibly prove a lower bound to Theorem <ref> using a lower bound on the entropy numbers of diagonal operators as shown by Kühn <cit.> for the case of the identity operator.

An important tool in the proof of Theorem <ref>, Lemma <ref> itself is proven only for polynomial semiaxes. Naturally, the following question arises.

Can Lemma <ref> be generalized to other types of semiaxes?

A generalization to other semiaxes would directly generalize Theorem <ref> and thus Theorem <ref> to the same class of semiaxes.

A possible approach to a lower bound may be to bound the supremum from below by the average of $\sigma_s(x)_q$ over $x\in \elp$. Then one can use an expression of a uniform vector in $\elp$ in terms of asymptotically independent vectors, see <cit.>, and use results from Gordon, Litvak, Schütt and Werner <cit.> on $k$-th minima ($\chg{(m-k)}$-th maxima) of independent random variables.

CHAPTER: FUNCTION RECOVERY AND QUANTIZATION

Passing from linear to standard information, this chapter is concerned with the quality of random samples compared to optimal samples. We present the results obtained in <cit.> together with Krieg for the $L_q$-approximation problem and the integration problem for Sobolev but also Hölder and Triebel-Lizorkin spaces. Compared to the original presentation, the proof technique employed here is slightly different, however, and allows for an extension to integration in Triebel-Lizorkin spaces.

Subsequently, we will motivate the study of random standard information, in particular for the important example of Sobolev spaces. Afterwards, in Section <ref> we will present the obtained results for Sobolev spaces and extensions to other spaces. In particular, we will characterize the radius of information given by a point set in terms of a geometric quantity. This allows us to compare the expected radius of random information to the minimal radius of information and consequently to determine the power of random information in terms of the given parameters.

Then we will give some details on the proof strategy in Section <ref>, where we discuss an asymptotically optimal construction for any point set, Section <ref>, where a lower bound and the relation to the integration problem is established, and Section <ref>, where the geometric quantity will be discussed. Finally, in Section <ref> we collect remaining open questions.

§ INTRODUCTION AND MOTIVATION

Given a function $f$ belonging to some function space $F$ defined on a set $D$ we can use standard information, that is, function evaluations $f(x_1),\ldots,f(x_n)$ at some point set $\Pn=\{x_1,\dots,x_n\}\subset D$, in order to solve a numerical problem. We are interested in comparing the radius of random points with the sampling numbers in order to give possible answers to Question <ref>. We refer to Section <ref> for a background.

As function evaluations are in particular linear measurements, linear information can lead to better algorithms than relying on standard information alone. In general, however, evaluations are more easily obtained than, say, Fourier coefficients and thus there is an interest in algorithms using standard information. Further, as we will briefly discuss in the following, recent research shows that for an important type of problem function evaluations can be almost as good as optimal linear information.

In the case of $L_2$-approximation in a function space $F$, it has been obtained by Krieg and M. Ullrich for Hilbert spaces <cit.>, and for more general spaces in <cit.>, that a least squares algorithm using random points is up to a logarithmic factor as good as the best linear algorithm. There, the sampling density depends on $F$ and is allowed to be uniform in some cases. Together with an improvement by M. Ullrich <cit.> this shows that typical information (with respect to this density) is close to optimal. There was an improvement by Nagel, Schäfer and T. Ullrich <cit.> based on progress in the related field of sampling discretization due to Nitzan, Olevskii and Ulanovskii <cit.> in turn building on the solution of the Kadison-Singer conjecture by Marcus, Spielman and Srivastava <cit.>. Recently, Dolbeault, Krieg and M. Ullrich <cit.> provided sharp upper bounds. However, in general, the logarithmic gap between the power of standard and linear information cannot be dispensed with as an example of Sobolev spaces with low smoothness given by Hinrichs, Krieg, Novak and Vybíral <cit.> shows.

It seems difficult to improve the current results on the radius of typical information for general function spaces. We are positive that the methods and results from <cit.>, which we discuss in this chapter, carry over to other settings. Further, we hope to shed light on possible conditions for asymptotic optimality of (sequences of) point sets in more general function spaces, and on the power of random standard information for those.

A starting point for our study was an open question by Hinrichs, Krieg, Novak, Prochno and M. Ullrich <cit.>, who obtained for the $L_q$-approximation problem for Sobolev spaces $W^1_p([0,1])$ that uniform random points are asymptotically on average optimal if $q<p$ and worse by a logarithmic factor if $q\ge p$. They made use of known asymptotics for averages of spacings between uniformly distributed points on an interval, which is related to the norm of a random point in a simplex as studied by Baci, Kabluchko, Prochno, Thäle and the author in <cit.>. In <cit.> we extended the work <cit.> to bounded convex sets in arbitrary dimension.

Another motivation was to improve a related suboptimal bound on the radius of random information for the approximation of Sobolev functions on manifolds obtained by Ehler, Gräf and Oates <cit.> using known asymptotics for the radius of the largest hole amidst a set of uniformly distributed independent random points. Together with D. Krieg we could close the logarithmic gap from <cit.> in almost all cases in the work <cit.>, where we transferred the results from <cit.> via charts to manifolds.

In general, one reason to study Sobolev spaces is their ubiquity in the theory of function spaces, which is in part due to their fundamental role as solution spaces of partial differential equations (PDEs). See for example Evans <cit.> for a gentle introduction and Maz'ja <cit.> for a comprehensive account. Let us give their definition.

Let $\Omega\subset\IR^d$ be a domain, that is an open and non-empty set. For a smoothness parameter $ s\in\mathbb{N} $ and an integrability parameter $ 1\leq p\le \infty $ we consider the Sobolev space

\[
W^s_p(\Omega):=\Big\{f\in L_p(\Omega)\colon \|f\|_{W^s_p(\Omega)}:=\Big(\sum_{|\alpha|\leq s} \|D^{\alpha}f\|_{L_p(\Omega)}^p\Big)^{1/p}<\infty\Big\},
\]

where the sum is over all multi-indices $ \alpha\in \mathbb{N}_0^d $ with $ |\alpha|=\alpha_1+\ldots+\alpha_d \le s $ and the expression $D^\alpha f = \frac{\partial^{|\alpha|}}{\partial x_1^{\alpha_1}\cdots\partial x_d^{\alpha_d}} f$ denotes a weak partial derivative of order $|\alpha|$.

By definition, the Sobolev space $W^s_p(\Omega)$ is a subspace of $L_p(\Omega)$ in which two elements are identified if they differ only on a set of measure zero. Without any additional assumptions, function evaluation is therefore not well defined. The embedding $W^s_p(\Omega)\hookrightarrow C_b(\Omega)$ into the bounded continuous functions eliminates this concern. It holds if

\begin{equation} \label{eq:embedding}
s>d/p \quad \text{if }1<p\le \infty \quad \text{or}\quad s\ge d \quad \text{if } p=1,
\end{equation}

under additional assumptions on $\Omega$ which will be satisfied for the domains we consider, see, e.g., <cit.>. In fact, we shall need the slightly stronger condition of $s>d/p$ for all $1\le p\le\infty$, which we assume from now on. In this case we have a compact embedding $W^s_p(\Omega)\hookrightarrow C_b(\Omega)$, see, e.g., <cit.>.

Several $s$-numbers of embeddings between Sobolev spaces have been studied, see, e.g., Pinkus <cit.> for an overview. There, and also for example in the book by Lorentz, von Golitschek and Makovoz <cit.>, discretization techniques allow to use bounds from embeddings between sequence spaces. This is connected to the study of diagonal operators as mentioned in the introduction to Chapter <ref>.

Let us describe the situation for sampling numbers or equivalently the minimal radius of standard information. Recall that the $n$-th minimal radius of information is given in the case of $L_q$-approximation by

\[
r\big(W_p^s(\Omega)\hookrightarrow L_q(\Omega),n\big)
=\inf_{S_{\Pn}}\sup_{\|f\|_{W^s_p(\Omega)}\le 1}\|f-S_{\Pn}(f)\|_{L_q(\Omega)},
\]

where the infimum is over all sampling operators of the form

\begin{equation}\label{eq:sampling-operator1}
S_{\Pn}\colon W^s_p(\Omega) \to L_q(\Omega),
\qquad S_{\Pn}(f)=\varphi\big(f(x_1),\dots,f(x_n)\big)
\end{equation}

for some $n$-point set $\Pn=\{x_1,\ldots,x_n\}\subset \Omega$ and $\varphi\colon \IR^n\to L_q(\Omega)$. Here, we dropped the $\lstd$ in the notation as we will only be concerned with standard information from now on.

On a bounded Lipschitz domain $\Omega\subset\IR^d$ (see Definition <ref> below), the minimal radius is known to satisfy

\begin{equation} \label{eq:minrad-app}
r\big(W_p^s(\Omega)\hookrightarrow L_q(\Omega),n\big)
\,\asymp\, n^{-s/d+(1/p-1/q)_+},
\end{equation}

where $(1/q-1/p)_+=1/q-1/p$ if $q<p$ and zero otherwise, see the discussion below. Note that the rate of decay improves if the smoothness $s$ is large compared to the dimension $d$ but deteriorates otherwise. This is in contrast to anisotropic function spaces of mixed smoothness where the dependence on the dimension is through a logarithmic factor. We refer to Temlyakov <cit.> for more information and note that for an important class of function spaces of mixed smoothness the asymptotics of the sampling numbers in $L_2$ are resolved by <cit.>.

For the integration problem, which corresponds to $q=1$ above, it is known that

\[
r\big(W^s_p(\Omega),{\rm INT},n\big)
\,\asymp\, n^{-s/d}.
\]

Recall that, in analogy to the above, the $n$-th minimal radius of information is given by

\[
r\big(W_p^s(\Omega),{\rm INT},n\big)
=\inf_{S_{\Pn}}\sup_{\|f\|_{W^s_p(\Omega)}\le 1}\Big|\int_{\Omega}f(x)\dd x-S_{\Pn}(f)\Big|,
\]

where the infimum is over all sampling operators as in (<ref>) with $L_q(\Omega)$ replaced by $\IR$.

In fact, it is known that for integration as well as $L_q$-approximation the sampling operators achieving the optimal asymptotic rate can be chosen linear, i.e., of the form

\begin{equation} \label{eq:linear-algo}
=\sum_{i=1}^{n}u_i f(x_i),
\end{equation}

where $\Pn=\{x_1,\ldots,x_n\}$ is a suitably chosen point set and $u_i$ are real numbers in the case of the integration problem and bounded real-valued functions on $\Omega$ in the case of the approximation problem. In general, the optimal algorithm for the integration problem given any standard information is linear. This is a well-known result due to Smolyak and Bakhvalov, see, e.g., <cit.>.

The above asymptotics for the minimal radius are classical for special domains like the cube and we do not know their origin. They have been obtained, for example, in the context of finite elements, which are used for the numerical approximation of solutions of PDEs, see, e.g., Heinrich <cit.> who refers to the treatise of Ciarlet <cit.>.

Using the moving least squares method, Wendland <cit.> proved a result on the local reproduction of polynomials, see Section <ref>. This was then used by Novak and Triebel in <cit.> to prove the asymptotic behaviour of the radius of minimal information for approximation (<ref>) for bounded Lipschitz domains. For sufficiently high smoothness, this may also be deduced from an earlier result due to Narcowich, Ward and Wendland <cit.> also relying on <cit.>. At this point, it seems worthwhile noting that in <cit.> the authors also compared the minimal radius of standard information to the one of linear information and concluded that, if one restricts to linear methods, linear information can be asymptotically better than standard information if and only if $p<2<q$.

As standard information is given by point sets, it is perhaps natural to look at their geometry to find (asymptotically) optimal point sets. In the works above it has been found that (sequences of) point sets covering the domain well, so that no point is far from the point set, are asymptotically optimal. That is, it was supposed that the covering radius

\begin{equation} \label{eq:covering-rad}
:=\sup_{x\in \Omega}\dist(x,\Pn)
\end{equation}

which is the supremum of the distance function

\begin{equation}\label{eq:dist-function}
\dist(\cdot, \Pn)\colon \mathbb{R}^d\to [0,\infty),
\qquad \dist(x,\Pn):=\min_{y\in \Pn}\|x-y\|_2
\end{equation}

to the $n$-point sampling set $\Pn\subset \Omega$ has to be of the best possible order $n^{-1/d}$, see also (<ref>) below. This assumption of an optimal covering radius is very common in numerical analysis; to give an impression, we refer to  Arcangéli, López de Silanes and Torrens <cit.>, Brauchart, Dick, Saff, Sloan, Wang and Womersley <cit.>, Duchon <cit.>, Mhaskar <cit.>, as well as Wendland and Schaback <cit.>, while being well aware of the incompleteness of this enumeration. In the following section, we will see that the covering radius is not sufficient to describe which (sequences of) point sets achieve the optimal rate. This allows for an asymptotic description of the expected power of random standard information.

§ DISCUSSION OF RESULTS

Motivated by the question whether random points or typical information is optimal, we derived a geometric characterization for the radius of information given by a point set, Theorem <ref> below. This yields a criterion (Corollary <ref>) of optimality given a sequence of point sets. Using results from quantization theory we show Proposition <ref> and derive Corollary <ref> which settles Question <ref> on the power of random information for the $L_q$-approximation and the integration problem above. Finally, Theorem <ref> extends the results to other spaces, including Hölder classes, Sobolev spaces of fractional smoothness and Triebel-Lizorkin spaces.

In order to investigate the power of random standard information, we analyzed the quality of arbitrary point sets and arrived at the following theorem.

Let $\Omega\subset \mathbb{R}^d$ be a bounded convex domain, $1\le p,q \le \infty$ and $s\in\mathbb{N}$ as in (<ref>).  Then, for any point set $\Pn\subset \Omega$,

\begin{align}
\tag{\textit a}
&r\big(W^s_p(\Omega)\hookrightarrow L_q(\Omega),\Pn\big)\, \asymp \,
\begin{cases}
\big\|\dist(\cdot, \Pn)\big\|_{L_{\infty}(\Omega)}^{s-d(1/p-1/q)} & \text{if } q\ge p,\vphantom{\bigg|}\\
\big\|\dist(\cdot, \Pn)\big\|_{L_{\gamma}(\Omega)}^s & \text{if } q<p,
\end{cases}\\[9pt]
\tag{\textit b}
&r\big(W^s_p(\Omega),{\rm INT},\Pn\big)\, \asymp\, r\big(W^s_p(\Omega)\hookrightarrow L_1(\Omega),\Pn\big),
\end{align}

where $\gamma=s(1/q-1/p)^{-1}$ and $\asymp$ is to be interpreted as in Definition <ref>. The algorithm achieving the upper bounds can be chosen linear, that is, of the form (<ref>).

The proof and the assumption of convexity will be discussed in Sections <ref> and <ref>.

Theorem <ref> implies for a sequence of point sets $(P_n)_{n\in\IN}$, each consisting of $n$ points, that the radius of information of $\Pn$ is asymptotically determined by the radius of the largest hole amidst the points if $q\ge p$ and by an average of the distance to the point set if $q<p$. The case $q\ge p$, where the covering radius determines the radius of information is included for completeness and can be deduced from the results of <cit.> and <cit.> mentioned before. Our contribution was to show that the covering radius is too large to capture the radius of information for $q<p$, and in particular, for numerical integration. In general, the assumption of a small covering radius is unnecessarily strong as we shall see in Corollary <ref> below.

Theorem <ref> is a tool to analyze the asymptotic optimality of arbitrary (sequences of) point sets and, in particular, random or typical ones. Before we will come to the quality of random points, let us comment on the optimal behaviour of the minimal $L_{\gamma}$-norm of the distance function to any point set with at most $n$ points. It is well known that this satisfies

\begin{equation} \label{eq:dist-optimal}
\inf_{\#\Pn \le n} \|\dist(\cdot, \Pn)\|_{L_{\gamma}(\Omega)} \,\asymp\, n^{-1/d}
\qquad \text{for every} \quad
0<\gamma\leq \infty,
\end{equation}

where the infimum is taken over all point sets $\Pn\subset \Omega$ with at most $n$ points. This can be deduced from a standard volume argument using balls centered at the points. For completeness a proof is provided in Appendix <ref>.

Thus, asymptotically optimal points, such as for example a suitably scaled lattice (see Chapter <ref>), can be said to have holes of order $n^{-1/d}$. Plugging this into Theorem <ref>, one can see that the rates for the minimal radius described in the introduction are achieved by such point sets. This yields the following characterization of (asymptotically) optimal point sets.

Let $\Omega\subset \mathbb{R}^d$ be a bounded convex domain, $1\le p,q \le \infty$ and $s\in\mathbb{N}$ as in (<ref>). Assume that for each (or at least infinitely many) $ n\in\mathbb{N}$ an $ n $-point set $ P_n\subset \Omega $ is given.  These point sets are asymptotically optimal, i.e.,

\[
r\big(W^s_p(\Omega)\hookrightarrow L_q(\Omega),n\big)
\,\asymp \,r\big(W^s_p(\Omega)\hookrightarrow L_q(\Omega),P_n\big),
\]

if and only if

\[
\|\dist(\cdot, P_n)\|_{L_\gamma(\Omega)} \,\asymp\, n^{-1/d},
\]

where $\gamma=s(1/q-1/p)^{-1}$ for $q<p$ and $\gamma=\infty$ for $q\ge p$.

By Theorem <ref>b, we clearly get the same characterization for numerical integration as for the problem of $L_1$-approximation. The relation between these two problems will be commented on later in Section <ref>.

Our results for $q<p$ seem to be novel already for $d=1$, where recent results were obtained in <cit.>. To the best of our knowledge, similar results only have been known for the spaces $W_\infty^s(\Omega)$ with $s\le 2$, see Sukharev <cit.> and Pagès <cit.>. The latter author uses concepts from the theory of quantization of measures which will be discussed later on.

To illustrate the advantage of the characterization of optimal points in Corollary <ref> compared to conditions involving the covering radius, consider the following example depicted in Figure <ref>.

Take for each $n\in\IN$ an $n$-point set $\Pn$ on a bounded convex domain $\Omega\subset\IR^d$. With regard to asymptotic behaviour, we ask:

How large can the largest hole admist $\Pn$ be for this to be still optimal as a sampling set for $L_q$-approximation of $W^s_p(\Omega)$-functions?

By Corollary <ref> the sequence of point sets $(P_n)$ can be (but not necessarily is) asymptotically optimal for this problem if and only if

\begin{equation} \label{eq:condition-largest-hole}
h_{P_n,\Omega}\lesssim n^{-1/d+1/(\gamma+d)}.
\end{equation}

This means that the radius of the largest hole is allowed to exceed the optimal covering radius $n^{-1/d}$ by the polynomial factor $n^{1/(\gamma+d)}$. A proof is provided in Appendix <ref>. We also refer to <cit.>, where the necessity of condition (<ref>) (for $q=1$) has been observed for numerical integration on the sphere.

An otherwise well-spaced point set containing a single large hole $B_n$ whose radius may be larger than the other holes by a polynomial factor without destroying the asymptotic optimality. Courtesy of D. Krieg.

Now that we have looked at optimal points, let us come to random points which have almost optimal covering properties as the following proposition shows.

Let $X_1,X_2,\ldots$ be independent and uniformly distributed on a bounded convex domain $\Omega\subset \mathbb{R}^d$. Consider the random $n$-point set $\pnran=\{X_1,\ldots,X_n\}$. Then, for any $\alpha\in (0,\infty)$,

\[
\mathbb{E}\,\|\dist(\cdot,\pnran)\|_{L_{\gamma}(\Omega)}^{\alpha}\,\asymp\,
\begin{cases}
n^{-\alpha/d} & \text{if } 0<\gamma<\infty,\\
n^{-\alpha/d}(\log n)^{\alpha/d} & \text{if } \gamma=\infty.