# Randomized approximation of summable sequences – adaptive and non-adaptive

Robert J. Kunsch, Erich Novak, Marcin Wnuk RWTH Aachen University, at the
Chair of Mathematics of Information Processing, Pontdriesch 10, 52062 Aachen,
Email<EMAIL_ADDRESS>FSU Jena, Ernst-Abbe-Platz 2, 03641 Jena,
Email<EMAIL_ADDRESS>für Mathematik, Osnabrück University,
Albrechtstraße 28a, 49076 Osnabrück, Email<EMAIL_ADDRESS>corresponding author

(August 28, 2024)

###### Abstract

We prove lower bounds for the randomized approximation of the embedding
$\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$ based on algorithms that use
arbitrary linear (hence non-adaptive) information provided by a (randomized)
measurement matrix $N\in{\mathbb{R}}^{n\times m}$. These lower bounds reflect
the increasing difficulty of the problem for $m\to\infty$, namely, a term
$\sqrt{\log m}$ in the complexity $n$. This result implies that non-compact
operators between arbitrary Banach spaces are not approximable using non-
adaptive Monte Carlo methods. We also compare these lower bounds for non-
adaptive methods with upper bounds based on adaptive, randomized methods for
recovery for which the complexity $n$ only exhibits a $(\log\log
m)$-dependence. In doing so we give an example of linear problems where the
error for adaptive vs. non-adaptive Monte Carlo methods shows a gap of order
$n^{1/2}(\log n)^{-1/2}$.

Keywords:  Monte Carlo, information-based complexity, lower bounds, compact
operators, adaption

##  1 Introduction

Consider a linear problem given by a linear operator $S\colon\;F\to G$ between
Banach spaces $F$ and $G$. We are interested in the randomized approximation
error, namely for a randomized algorithm $A_{n}$ and an input $f\in F$, the
output $A_{n}(f)$ is a $G$-valued random variable and we define its error by

$e(A_{n},S,f):=\operatorname{\mathbb{E}}\|A_{n}(f)-S(f)\|_{G}\,.$

A randomized algorithm can be seen as a family
$A_{n}=(A_{n}^{\omega})_{\omega\in\Omega}=(\phi^{\omega}\circ
N^{\omega})_{\omega\in\Omega}$ of mappings $F\to G$ on a complete probability
space $(\Omega,\mathcal{A},{\mathbb{P}})$ where each realization
$A_{n}^{\omega}$ can be decomposed into an information map $N^{\omega}\colon
F\to{\mathbb{R}}^{n}$ that uses $n$ linear functionals, and a reconstruction
map $\phi^{\omega}\colon{\mathbb{R}}^{n}\to G$. In the simplest setting of
_non-adaptive_ information, $N^{\omega}$ is a linear map yielding information

$\boldsymbol{y}=(y_{1},\ldots,y_{n})=N^{\omega}(f)=\bigl{(}L_{1}^{\omega}(f),\ldots,L_{n}^{\omega}(f)\bigr{)}$

with linear functionals $L_{1}^{\omega},\ldots,L_{n}^{\omega}\in F^{\prime}$.
In a finite-dimensional problem setup with $F={\mathbb{R}}^{m}$, a non-
adaptive information map $N=(N^{\omega})_{\omega\in\Omega}$ can be identified
with a random $(n\times m)$-matrix. The more general case of _adaptive_
information allows $L_{2}^{\omega},\ldots,L_{n}^{\omega}$ to be chosen
depending on previous information, in detail, for $k=2,\ldots,n$ we may have

$y_{k}:=L_{k}^{\omega}(f;y_{1},\ldots,y_{k-1})\qquad\text{where}\quad
L_{k}^{\omega}(\,\cdot\,;y_{1},\ldots,y_{k-1})\in F^{\prime}.$

We assume Borel measurability for the maps $\Omega\times{\mathbb{R}}^{k-1}\to
F^{\prime}$ selecting the $k$-th information functionals, thus guaranteeing
the measurability of the information map $N\colon\Omega\times
F\to{\mathbb{R}}^{n}$ as a whole. We also assume measurability of the
reconstruction $\phi\colon\Omega\times{\mathbb{R}}^{n}\to G$ which implies
measurability of the algorithm $A_{n}\colon\Omega\times F\to G$.

We compare algorithms that use (at most) $n$ linear functionals and call $n$
the (information) cost of such an algorithm. This leads to the following
notion of a minimal Monte Carlo error for the problem $S$,

$e^{\textup{ran}}(n,S):=\inf_{(A_{n}^{\omega})_{\omega\in\Omega}}\sup_{\|f\|_{F}\leq
1}\operatorname{\mathbb{E}}\|A_{n}(f)-S(f)\|_{G}\,;$

the minimal $n$ needed to guarantee an error at most $\varepsilon$ is called
complexity. We thus use the standard worst case setting of approximation
theory and information-based complexity for randomized algorithms. In this
paper, we also use the term _Monte Carlo method_ to refer to any randomized
algorithm.

If $A_{n}^{\omega}\colon F\to G$ does not depend on $\omega$, the algorithm is
called _deterministic_ and we write $A_{n}\colon F\to G$. The corresponding
error notion is

$e^{\textup{det}}(n,S):=\inf_{A_{n}}\sup_{\|f\|_{F}\leq
1}\|A_{n}(f)-S(f)\|_{G}\,,$

where the infimum is taken with respect to all deterministic algorithms with
information cost at most $n$. An algorithm is called non-adaptive if its
information mapping $N$ is non-adaptive, otherwise it is called adaptive. We
define

$e^{\textup{ran},\textup{nonada}}(n,S):=\inf_{(A_{n}^{\omega})_{\omega\in\Omega}}\sup_{\|f\|_{F}\leq
1}\operatorname{\mathbb{E}}\|A_{n}(f)-S(f)\|_{G}$

as above, but the infimum is taken over the set of non-adaptive algorithms. By
writing $e^{\textup{ran},\textup{lin}}$ we indicate the restriction to
algorithms $A_{n}$ based on linear maps $\phi^{\omega}$ and $N^{\omega}$. (A
slight generalization of these error notions allows for algorithms with
_varying cardinality_ where the amount of information $n$ may be random or
even adaptively chosen and is only bounded in terms of its expected value. It
turns out, that, at least in the non-adaptive setting, varying cardinality
$n(\omega)$ cannot improve much over the setting with strict cost bound, see
[9, pp. 289/290] or [19, Lem 1.4].)

For the main part of this paper, we study the identical embedding between
finite dimensional sequence spaces,

$S\colon\ell_{p}^{m}\to\ell_{q}^{m},\quad\boldsymbol{x}\mapsto\boldsymbol{x}\,,$

where $1\leq p,q\leq\infty$ and $m\in{\mathbb{N}}$. We will write
$\ell_{p}^{m}\hookrightarrow\ell_{q}^{m}$ as a shorthand for the sequence
space embedding $S$, and $[m]:=\\{1,\ldots,m\\}$ for the index set of a vector
$\boldsymbol{x}=(x_{1},\ldots,x_{m})\in{\mathbb{R}}^{m}$. We consider
approximation with incomplete information, namely $n<m$, say, $m\geq 4n$. A
particular interest lies in extreme cases with $n\ll m$, or in other words,
the asymptotic behaviour for $\frac{n}{m}\to 0$, or even just $m\to\infty$ for
fixed $n$. Sequence space embeddings play an important role in understanding
more general approximation problems, for instance contrasting approximation
rates for different classes of algorithms: Linear vs. non-linear, adaptive vs.
non-adaptive, deterministic vs. randomized. We quickly review classical
results for three important special cases, for a comprehensive overview of
deterministic approximation theory in sequence spaces, see [28, Chap VI] and
[7, Chap 10].

$\ell_{1}^{m}\hookrightarrow\ell_{2}^{m}$:

From Kashin (1974) [16] and Garnaev, Gluskin (1984) [8] we know deterministic
rates, namely, for $m\geq 2n$ we have

$e^{\textup{det}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\asymp\min\left\\{1,\,\sqrt{\frac{\log\frac{m}{n}}{n}}\right\\}\,.$
(1)

Upper bounds in this case are achieved by using a non-linear reconstruction
$\phi(\boldsymbol{y}):=\operatorname*{argmin}\limits_{\boldsymbol{z}\in{\mathbb{R}}^{m}\colon
N\boldsymbol{z}=\boldsymbol{y}}\|\boldsymbol{z}\|_{1}$ based on suitable non-
adaptive information $\boldsymbol{y}=N\boldsymbol{x}$. Non-linearity, indeed,
is a necessary feature as lower bounds for linear randomized methods show:
Mathé (1991) [23, Sec 3, Lem 2 (ii)] implies that for $m\geq 2n$,

$e^{\textup{ran},\textup{lin}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\asymp
e^{\textup{det},\textup{lin}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\asymp
1\,.$

From Heinrich (1992) [9] we know lower bounds for general randomized methods,
namely, for $m\geq 2n$, he proves

$e^{\textup{ran}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\succeq
n^{-1/2}\,.$ (2)

This bound shows that randomized methods cannot improve the $n$-dependence
over deterministic algorithms, but it does not reflect an $m$-dependence.

$\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m}$:

Here, in the deterministic setting, for $m\geq 2n$, no substantial
approximation is possible,

$e^{\textup{det}}(n,\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m})\asymp 1\,,$

while using linear (thus non-adaptive) randomized algorithms, Mathé [23] shows
that for $m\geq 2n$,

$e^{\textup{ran}}(n,\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m})\preceq\sqrt{\frac{\log
m}{n}}\,.$

The algorithms used for this result consist of a linear information map
representable as $(n\times m)$-matrix $N$ with i.i.d. standard Gaussian
entries, and a linear reconstruction map representable as the matrix
$\varphi^{\omega}=\frac{1}{n}(N^{\omega})^{\top}\in{\mathbb{R}}^{m\times n}$.
Once again, from Heinrich [9] we know a lower bound for $m\geq 2n$ without an
$m$-dependence

$e^{\textup{ran}}(n,\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m})\succeq\sqrt{\frac{\log
n}{n}}\,.$ (3)

$\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$:

In the deterministic setting there exist linear methods that are optimal, see
[5] or [26, Thms 4.5 and 4.8], yet the precise rates remain unknown. The rates
from non-linear deterministic methods in the setting
$\ell_{1}^{m}\hookrightarrow\ell_{2}^{m}$ with the stricter error criterion,
see (1), directly translate into upper bounds for
$\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$. Lower bounds reflecting a
logarithmic $m$-dependence can be found in [6, Prop 2.1] and the rate in $n$
is also known to be optimal. Mathé [23, Sec 3, Lem 2 (ii)] showed for $m\geq
2n$ that

$e^{\textup{ran},\textup{lin}}(n,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\succeq
n^{-1/2}\,,$

hence, linear randomized methods cannot improve the rate in $n$ over
deterministic methods, yet the optimal $m$-dependence remains unknown.
Combining the non-linearity for $\ell_{1}^{m}\hookrightarrow\ell_{2}^{m}$ and
the randomness for $\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m}$, Heinrich
[9] constructed a two-stage algorithm showing an improved main rate (for
$m\geq 4n$), together with a lower bound:

$\frac{\sqrt{\log n}}{n}\preceq
e^{\textup{ran}}(n,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\preceq\frac{\sqrt{(\log\frac{m}{n})(\log
m)}}{n}\,.$ (4)

Here as well, the lower bound lacks an $m$-dependence.

Our main contribution is a lower bound for non-adaptive randomized
approximation that reflects the $m$-dependence. Theorem 2.7 shows for $n\leq
c_{0}\sqrt{\log m}$ (with a suitable constant $c_{0}>0$) that

$e^{\textup{ran},\textup{nonada}}(n,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\geq\varepsilon_{0}>0\,.$

This result has two main consequences which we state and comment below.

######  Consequence 1.

Non-compact operators between arbitrary Banach spaces are not approximable
using non-adaptive Monte Carlo methods, see Theorem 2.11.

This statement relies on the fact that the sequence space embedding
$\ell_{1}\hookrightarrow\ell_{\infty}$ is known to be a universal non-compact
operator [15], see Proposition 2.12. The first consequence therefore justifies
our focus on lower bounds for the problem
$\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$. On an elementary level, among
all sequence space embeddings $\ell_{p}^{m}\hookrightarrow\ell_{q}^{m}$ with
$1\leq p,q\leq\infty$, the case $(p,q)=(1,\infty)$ is the easiest from an
approximation point of view: The $\ell_{1}$-unit ball $B_{1}^{m}$ is the
smallest among all $\ell_{p}$-balls, further, the $\ell_{\infty}$-norm is the
least punishing among all $\ell_{q}$-norms we might choose to measure the
error. Hence, our lower bound holds for all embeddings from $\ell_{p}^{m}$ to
$\ell_{q}^{m}$.

Lower bounds are also studied in the field of sparse recovery with a different
error criterion, see in particular Woodroff et al. [2, 30] and also (19) in
Section 3. The lower bounds in [30] can be transferred to lower bounds for
$\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m}$ and cover both the adaptive and
the non-adaptive setting. Our proof technique as described in Section 2.1 is a
substantial modification of their approach suited to accommodate the much
smaller input set $B_{1}^{m}$ in the problem
$\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$. However, we only discuss the
non-adaptive case, the adaptive case is left for future research. The setting
in [2] resembles our setting with input space $\ell_{1}^{m}$ and contains a
lower bound for non-adaptive algorithms. Their proof, relying on communication
complexity, seems not to translate easily to our error criterion, though. On
the other hand, upper bounds in the sparse recovery setting [14, 21] can
easily be used to prove upper bounds in our setting, see Section 3 where we
find upper bounds using adaptive algorithms which lead to the second main
consequence.

######  Consequence 2.

Adaptive Monte Carlo methods are much better than non-adaptive methods for
some linear problems. The gap in the error can be of the order $n^{1/2}(\log
n)^{-1/2}$ for the embedding $\ell_{1}^{m}\hookrightarrow\ell_{2}^{m}$, see
Corollary 3.3.

It is well known that for linear problems in the deterministic setting,
adaption can reduce the error by a factor $2$ at most, hence, no difference in
the approximation rates can be observed, see the survey [25] for this and for
related results. It was not known whether such a result also holds for
randomized algorithms. The problem was posed in [25] and restated in [26, Open
Problem 20].

This open problem was recently solved by Stefan Heinrich [10, 11, 12, 13] who
studied (parametric) integration and approximation in mixed
$\ell_{p}(\ell_{q})$-spaces using standard information (function evaluations).
In [12] he proved that in the randomized setting a gap of order $n^{1/2}(\log
n)^{-1}$ is possible between adaptive and non-adaptive approximation. Our gap
is slightly larger in the logarithmic term and one can prove that the largest
possible gap is at most $n^{1/2}$ for mappings into a Hilbert space, see
Remark 3.5. Note that our result is obtained for the class of all linear
functionals as admissible information rather than just function evaluations,
hence, in a different algorithmic setting which requires different proof
techniques.

The problem $\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$ is notable due to
the fact that in the deterministic setting, additional algorithmic features
like non-linearity or adaptivity cannot improve the error whatsoever, but in
the randomized setting, the algorithmic features of non-linearity and
adaptivity both bring about significant improvements.

### Notation

For a normed space $(F,\|\cdot\|_{F})$ we denote its closed unit ball by
$B_{F}$, the distance between two sets $F_{1},F_{2}\subset F$ is defined via

$\operatorname{dist}_{F}(F_{1},F_{2}):=\inf_{\begin{subarray}{c}f_{1}\in
F_{1}\\\ f_{2}\in F_{2}\end{subarray}}\|f_{1}-f_{2}\|_{F}\,.$

In spaces $\ell_{p}^{m}$ we use the abbreviations
$\|\cdot\|_{p}:=\|\cdot\|_{\ell_{p}^{m}}$ for the norm,
$B_{p}^{m}:=B_{\ell_{p}^{m}}$ for the unit ball, and
$\operatorname{dist}_{p}:=\operatorname{dist}_{\ell_{p}^{m}}$ for the
distance. When talking about operators between normed spaces, we always mean
bounded linear operators.

For functions $f,g\colon M\to(0,\infty)$ on a domain $M$ we write $f\preceq g$
if there exists a constant $C>0$ such that for all $x\in M$ we have $f(x)\leq
Cg(x)$. If $f\preceq g$ and $f\succeq g$, we write $f\asymp g$ and call $f$
and $g$ _weakly asymptotically equivalent_.

Throughout this paper we work with an underlying probability space
$(\Omega,\mathcal{A},{\mathbb{P}})$. For $\Omega^{\prime}\subset\Omega$ we
denote its complement by $\Omega^{\prime c}:=\Omega\setminus\Omega^{\prime}$.
Furthermore, all the measurable spaces are tacitly assumed to be Polish, so
that one can use the disintegration theorem to produce conditional measures.
We use the following conventions concerning conditional probabilities with
respect to a random variable $\boldsymbol{Y}$ on a measurable space $H$: We
write
${\mathbb{P}}^{\boldsymbol{Y}}(\,\cdot\,):={\mathbb{P}}(\boldsymbol{Y}\in\cdot\,)$
for the distribution of $\boldsymbol{Y}$, and let the mapping
$H\times\mathcal{A}\to[0,1],\,(\boldsymbol{y},A)\mapsto{\mathbb{P}}_{\boldsymbol{y}}(A)={\mathbb{P}}(A\mid\boldsymbol{Y}=\boldsymbol{y})$
denote a regular conditional probability (for details see, e.g., [17, Chap 8])
such that

${\mathbb{P}}(\,\cdot\,)=\int_{H}{\mathbb{P}}_{\boldsymbol{y}}(\,\cdot\,)\,\mathup{d}{\mathbb{P}}^{\boldsymbol{Y}}(\boldsymbol{y})\,.$

Accordingly, we write
$\operatorname{\mathbb{E}}_{\boldsymbol{y}}[\;\cdot\;]=\operatorname{\mathbb{E}}[\;\cdot\mid\boldsymbol{Y}=\boldsymbol{y}]$
for integration with respect to ${\mathbb{P}}_{\boldsymbol{y}}$.

##  2 A lower bound for non-adaptive algorithms

###  2.1 The average-case setting

We make use of Bakhvalov’s technique for Monte Carlo lower bounds [3, 9, 24].
Namely, for a (sub-)probability measure $\mu$ supported on the unit ball
$B_{F}$ of the normed space $F$ (that is, $\mu\geq 0$ and
$\mu(F)=\mu(B_{F})\leq 1$), consider the _average case error_

$e^{\mu}(n,S):=\inf_{A_{n}}\int\|A_{n}(f)-S(f)\|_{G}\,\mathup{d}\mu(f)\,,$

where the infimum is taken with respect to all measurable deterministic
algorithms using at most $n$ information functionals. Exploiting measurability
of randomized algorithms as mappings $\Omega\times F\to G$, we have the lower
bound

$e^{\textup{ran}}(n,S)\geq e^{\mu}(n,S)\,.$ (5)

Restricting to non-adaptive deterministic algorithms in the $\mu$-average
setting yields lower bounds for non-adaptive randomized algorithms. The lower
bound results cited in the introduction rely on truncated Gaussian measures on
the unit ball $B_{p}^{m}\subset\ell_{p}^{m}$ intersected with a subspace, see
Heinrich [9]. The problem with scaled $m$-dimensional standard Gaussian
measures is that for $p<q$ already the _initial error_ of their respective
truncations $\mu$ on the unit ball $B_{p}^{m}$ decays to zero, no matter how
we change the scaling:

$e^{\mu}(0,\ell_{p}^{m}\hookrightarrow\ell_{q}^{m})=\int\|\boldsymbol{x}\|_{q}\,\mathup{d}\mu(\boldsymbol{x})\xrightarrow[m\to\infty]{}0\,.$

For that reason, Heinrich [9] only considered $4n$-dimensional Gaussian
measures (if $m\geq 4n$) resulting in lower bounds that do not reflect the
increasing difficulty of the problem with growing $m$.

In what follows, we will consider a random input of the form

$\boldsymbol{X}:=\boldsymbol{u}_{I}+\sigma\boldsymbol{W}\,.$ (6)

Here, $(\boldsymbol{u}_{i})_{i\in[M]}$, $M\in{\mathbb{N}}$, is a collection of
points from the $\ell_{p}^{m}$-unit ball $B_{p}^{m}\subset{\mathbb{R}}^{m}$
(we are especially interested in the $\ell_{1}$-ball $B_{1}^{m}$), and
$I\sim\operatorname{unif}[M]$ is a selector random variable which chooses the
random point $\boldsymbol{u}_{I}$. The disturbance $\boldsymbol{W}$ is
generated by projecting a standard Gaussian vector
$\boldsymbol{Z}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},\operatorname{id}_{m})$
onto $2n$ randomly chosen coordinates and we introduce a scaling $\sigma>0$.
In detail, we define the set of subsets

$\mathcal{J}_{2n}:=\left\\{\mathfrak{j}\subseteq[m]\colon\\#\mathfrak{j}=2n\right\\}\,,$
(7)

and write $P_{\mathfrak{j}}\colon{\mathbb{R}}^{m}\to{\mathbb{R}}^{m}$ for the
projection onto the coordinates given by an index set
$\mathfrak{j}\subseteq[m]$. Taking
$\mathfrak{J}\sim\operatorname{unif}{\mathcal{J}_{2n}}$, we define
$\boldsymbol{W}:=P_{\mathfrak{J}}\boldsymbol{Z}$, i.e.

$W_{j}=\begin{cases}Z_{j}&\text{if }j\in\mathfrak{J}\,,\\\ 0&\text{if
}j\notin\mathfrak{J}\,.\end{cases}$

Here, $I$, $\boldsymbol{Z}$, and $\mathfrak{J}$ are independent random
variables. The distribution of $\boldsymbol{X}$ is a measure

$\widetilde{\mu}:={\mathbb{P}}^{\boldsymbol{X}}$ (8)

on ${\mathbb{R}}^{m}$. We assume that, with suitably chosen radius $r_{0}>0$,
the $\ell_{p}^{m}$-balls

$F_{i}:=\boldsymbol{u}_{i}+r_{0}B_{p}^{m}$ (9)

around each point $\boldsymbol{u}_{i}$ fit inside the unit ball $B_{p}^{m}$
and are separated by $c>0$ in the $\ell_{q}^{m}$-metric,

$F_{i}\subseteq
B_{p}^{m}\qquad\text{and}\qquad\operatorname{dist}_{q}(F_{i},F_{i^{\prime}})\geq
c\quad\text{for }i\neq i^{\prime}.$

We truncate the measure $\widetilde{\mu}$ with respect to the following event,

$\Omega^{\prime}:=\left\\{\omega\in\Omega\colon\boldsymbol{X}(\omega)\in
F_{I(\omega)}\right\\}=\left\\{\omega\in\Omega\colon\|\boldsymbol{W}(\omega)\|_{p}\leq\frac{r_{0}}{\sigma}\right\\}\,,$
(10)

namely, we define the truncated measure

$\mu(\,\cdot\,):={\mathbb{P}}\bigl{(}\Omega^{\prime}\cap\\{\boldsymbol{X}\in\,\cdot\,\\}\bigr{)}\,.$
(11)

That way we ensure in particular that $\mu$ is supported on $B_{p}^{m}$ and we
can indeed apply Bakhvalov’s technique (5). The scaling $\sigma>0$ of the
disturbance has an influence on the truncation probability

$\delta:=\widetilde{\mu}({\mathbb{R}}^{m})-\mu({\mathbb{R}}^{m})={\mathbb{P}}\left(\Omega^{\prime
c}\right)\,.$ (12)

Integrating with respect to the truncated measure $\mu$ is equivalent to
taking the expectation multiplied with the indicator function of
$\Omega^{\prime}$, that is, the corresponding $\mu$-average error of a
deterministic (measurable) algorithm
$A_{n}\colon{\mathbb{R}}^{m}\to{\mathbb{R}}^{m}$ is

$\int\|A_{n}(\boldsymbol{x})-\boldsymbol{x}\|_{q}\,\mathup{d}\mu(\boldsymbol{x})=\operatorname{\mathbb{E}}\left[\|A_{n}(\boldsymbol{X})-\boldsymbol{X}\|_{q}\cdot\mathds{1}_{\Omega^{\prime}}\right]\,.$

In the non-adaptive setting, $A_{n}=\phi\circ N$ is built with a linear
information mapping $N\colon{\mathbb{R}}^{m}\to{\mathbb{R}}^{n}$ which can be
identified with a matrix $N\in{\mathbb{R}}^{n\times m}$. By subsequent Lemma
2.2, finding lower bounds on the error of the average case problem reduces to
finding lower bounds on the failure probability for identifying $I$ from
measurements $\boldsymbol{Y}:=N\boldsymbol{X}$.

Measures similar to the distribution of $\boldsymbol{X}$ in (6) have been
considered in [30] in a compressed sensing model with $\ell_{2}$-noise. If the
source space is $\ell_{2}^{m}$, then instead of $2n$-dimensional disturbances
$\sigma\boldsymbol{W}$ we may directly work with the $m$-dimensional Gaussian
vector $\sigma\boldsymbol{Z}$ and omit the projection step. The reason for the
projection step is that, in order to keep the truncation probability $\delta$
small, in the $\ell_{1}$-setting the scaling factor $\sigma$ would need to
shrink prohibitively fast with growing dimension of the Gaussian measure. In
the $\ell_{2}$-setting, however, the projection step is not necessary; the
analysis of adaptive algorithms then is way easier and has indeed been
conducted in [30].

For the analysis of the average case setting with different directions
$\mathfrak{j}\subset[m]$ of the disturbance $\boldsymbol{W}$, we need a
monotonicity argument for information.

######  Lemma 2.1.

Let $S\colon F\to G$ be a measurable map between Banach spaces and let
$\boldsymbol{X}$ be a random variable with values in $F$. Consider random
variables $\boldsymbol{Y}$ and $\widetilde{\boldsymbol{Y}}$ with values in
measurable spaces $H$ and $\widetilde{H}$, respectively, so-called
_information_ , and assume that $\boldsymbol{Y}$ can be written as a
measurable function of $\widetilde{\boldsymbol{Y}}$.

Then, for any event $\Omega^{\prime}\subset\Omega$, we have

$\inf_{\widetilde{\phi}\colon\widetilde{H}\to
G}\operatorname{\mathbb{E}}\left[\|S(\boldsymbol{X})-\widetilde{\phi}(\widetilde{\boldsymbol{Y}})\|_{G}\cdot\mathds{1}_{\Omega^{\prime}}\right]\leq\inf_{\phi\colon
H\to
G}\operatorname{\mathbb{E}}\left[\|S(\boldsymbol{X})-\phi(\boldsymbol{Y})\|_{G}\cdot\mathds{1}_{\Omega^{\prime}}\right]\,,$

where the infima are taken over measurable mappings.

###### Proof.

Let $f:\widetilde{H}\rightarrow H$ be a measurable mapping with
$\boldsymbol{Y}=f(\widetilde{\boldsymbol{Y}})$ almost surely. For each
measurable $\phi\colon H\to G$, the mapping $\phi\circ\boldsymbol{Y}$ can be
replicated via a measurable mapping $\phi\circ
f\circ\widetilde{\boldsymbol{Y}}$, that is, $\widetilde{\phi}=\phi\circ f$. ∎

As described beforehand, we will analyse the average case error
$e^{\mu}(n,\ell_{p}^{m}\hookrightarrow\ell_{q}^{m})$ for which we only need to
consider deterministic algorithms $A_{n}:=\phi\circ N$ with information map
$N\colon\ell_{p}^{m}\to{\mathbb{R}}^{n}$ and reconstruction map
$\phi\colon{\mathbb{R}}^{n}\to\ell_{q}^{m}$. There can only be one output
$\phi(\boldsymbol{y})\in\ell_{q}^{m}$ for one information vector
$\boldsymbol{y}\in{\mathbb{R}}^{n}$. This output shall be optimal with respect
the truncated conditional distribution. The following lemma provides an error
bound for the conditional average error, in later applications we take
${\mathbb{P}}_{y}$ for ${\mathbb{P}}$ and $\operatorname{\mathbb{E}}_{y}$ for
$\operatorname{\mathbb{E}}$.

######  Lemma 2.2.

Let $S:F\to G$ be a measurable map between Banach spaces, and consider a
family of sets $(F_{i})_{i=1}^{M}$ in $F$ where there is a constant $c>0$ such
that

$\operatorname{dist}_{G}(S(F_{i}),S(F_{i^{\prime}}))\geq c$

for distinct indices $i,i^{\prime}\in[M]$. Put
$F^{\prime}:=\bigcup_{i=1}^{M}F_{i}$. Furthermore, let $\boldsymbol{X}$ be a
random variable with values in $F$ and consider an event
$\Omega^{\prime}\subset\\{\boldsymbol{X}\in F^{\prime}\\}$. Then

$\inf_{g\in G}\mathbb{E}\left[\lVert
S(\boldsymbol{X})-g\rVert_{G}\cdot\mathds{1}_{\Omega^{\prime}}\right]\geq
c\min\left\\{\frac{{\mathbb{P}}(\Omega^{\prime})}{2},{\mathbb{P}}(\Omega^{\prime})-\max_{i\in[M]}{\mathbb{P}}(\Omega^{\prime}\cap\\{\boldsymbol{X}\in
F_{i}\\})\right\\}\,.$

###### Proof.

Fix $g\in G$ and assume that
$d:=\operatorname{dist}_{G}(g,S(F_{M}))\leq\operatorname{dist}_{G}(g,S(F_{i}))$
for all $i\in[M-1]$. We write
$t:={\mathbb{P}}(\Omega^{\prime}\cap\\{\boldsymbol{X}\in F_{M}\\})$ and
$T:={\mathbb{P}}(\Omega^{\prime})$. From the triangle inequality, for
$i\in[M-1]$, we have

$\displaystyle c$
$\displaystyle\leq\operatorname{dist}_{G}(S(F_{i}),S(F_{M}))\leq\operatorname{dist}_{G}(S(F_{i}),g)+\underbrace{\operatorname{dist}_{G}(g,S(F_{M}))}_{=d}$
$\displaystyle\quad\Longrightarrow\quad\operatorname{dist}_{G}(S(F_{i}),g)\geq
c-d\,.$

This leads to

$\displaystyle\mathbb{E}\left[\lVert
S(\boldsymbol{X})-g\rVert_{G}\cdot\mathds{1}_{\Omega^{\prime}}\right]$
$\displaystyle=\sum_{i=1}^{M}\mathbb{E}\left[\lVert
S(X)-g\rVert_{G}\cdot\mathds{1}_{\Omega^{\prime}}\cdot\mathds{1}_{\\{\boldsymbol{X}\in
F_{i}\\}}\right]$
$\displaystyle\geq\sum_{i=1}^{M}{\mathbb{P}}\bigl{(}\Omega^{\prime}\cap\\{\boldsymbol{X}\in
F_{i}\\}\bigr{)}\cdot\operatorname{dist}_{G}(S(F_{i}),g)$
$\displaystyle\geq\sum_{i=1}^{M-1}{\mathbb{P}}\bigl{(}\Omega^{\prime}\cap\\{\boldsymbol{X}\in
F_{i}\\}\bigr{)}\cdot\max(d,c-d)+td.$

The last expression above is equal to $h_{t}(d)$ where

$\displaystyle h_{t}:(0,\infty)\rightarrow{\mathbb{R}},\quad$ $\displaystyle
d\mapsto\begin{cases}(2t-T)d+Tc-tc&\text{ if }d\leq\frac{c}{2}\,,\\\ Td&\text{
if }d>\frac{c}{2}\,.\end{cases}$

The minimum of $h_{t}(\cdot)$ is to be found for $d\in[0,\frac{c}{2}]$,
namely, due to the linearity, in one of the endpoints:

$h_{t}(0)=(T-t)\cdot c\,,\qquad
h_{t}\left(\frac{c}{2}\right)=T\cdot\frac{c}{2}\,.$

This shows

$\mathbb{E}\left[\lVert
S(X)-g\rVert_{G}\cdot\mathds{1}_{\Omega^{\prime}}\right]\geq
c\cdot\min\left\\{\frac{T}{2},\,T-t\right\\}\,,$

where $t={\mathbb{P}}(\Omega^{\prime}\cap\\{\boldsymbol{X}\in F_{M}\\})$ and
$T={\mathbb{P}}(\Omega^{\prime})$. Ending up with
${\mathbb{P}}(\Omega^{\prime}\cap\\{\boldsymbol{X}\in F_{M}\\})$ in this
formula, however, was only possible under the simplifying assumption that the
output $g$ is closest to $S(F_{M})$. Replacing $t$ by
$\max_{i\in[M]}{\mathbb{P}}(\Omega^{\prime}\cap\\{\boldsymbol{X}\in
F_{i}\\})$, we account for the possiblity of $g$ being closer to another set
$S(F_{i})$. ∎

Recall that for the truncated measure $\mu$, knowing the index $I=i$ means
knowing in which of the balls $F_{i}=\boldsymbol{u}_{i}+r_{0}B_{p}^{m}$ the
input $\boldsymbol{X}$ lies.

######  Lemma 2.3.

Let $S:F\to G$ be a measurable map between Banach spaces. Consider a family of
sets $(F_{i})_{i=1}^{M}$ in $F$ where there is a constant $c>0$ such that

$\operatorname{dist}_{G}(S(F_{i}),S(F_{i^{\prime}}))\geq c$

for distinct indices $i,i^{\prime}\in[M]$.

Let $\boldsymbol{X}$ be a random variable with values in $F$, let $I$ be a
random variable with values in $[M]$, and consider the event

$\Omega^{\prime}=\left\\{\omega\in\Omega\colon\boldsymbol{X}(\omega)\in
F_{I(\omega)}\right\\}$

with $\delta:={\mathbb{P}}(\Omega^{\prime c})$. Furthermore, let
$\boldsymbol{Y}$ be a random variable with values in some measurable space
$H$, the so-called _information_. We define the “distinctness” function

$D_{I\mid\boldsymbol{Y}}(\boldsymbol{y}):=\max_{i\in[M]}{\mathbb{P}}(I=i\mid\boldsymbol{Y}=\boldsymbol{y})\,.$

Then for any measurable reconstruction map $\phi\colon H\to G$ we have the
average case lower bound

$\operatorname{\mathbb{E}}\bigl{[}\|S(\boldsymbol{X})-\phi(\boldsymbol{Y})\|_{G}\cdot\mathds{1}_{\Omega^{\prime}}\bigr{]}\geq
c\cdot\left(\frac{1}{2}\cdot{\mathbb{P}}\left(D_{I\mid\boldsymbol{Y}}(\boldsymbol{Y})\leq\frac{1}{2}\right)-\delta\right)\,.$

###### Proof.

The case ${\mathbb{P}}(\Omega^{\prime})=0$ is trivial, so let us assume that
${\mathbb{P}}(\Omega^{\prime})>0$. Defining the loss function

$\ell(\boldsymbol{y}):=\operatorname{\mathbb{E}}\bigl{[}\|S(\boldsymbol{X})-\phi(\boldsymbol{Y})\|_{G}\cdot\mathds{1}_{\Omega^{\prime}}\;\big{|}\;\boldsymbol{Y}=\boldsymbol{y}\bigr{]}\,,$

we can write

$\operatorname{\mathbb{E}}\bigl{[}\|S(\boldsymbol{X})-\phi(\boldsymbol{Y})\|_{G}\cdot\mathds{1}_{\Omega^{\prime}}\bigr{]}=\operatorname{\mathbb{E}}\bigl{[}\ell(\boldsymbol{Y})\bigr{]}\,.$

Using Lemma 2.2, we see that for almost every $\boldsymbol{y}$,

$\displaystyle\ell(\boldsymbol{y})$ $\displaystyle\geq
c\cdot\min\left\\{\frac{{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime})}{2},{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime})-\max_{i\in[M]}{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime}\cap\\{\boldsymbol{X}\in
F_{i}\\})\right\\}$ $\displaystyle\geq
c\cdot\min\left\\{\frac{{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime})}{2},{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime})-\max_{i\in[M]}{\mathbb{P}}_{\boldsymbol{y}}(I=i)\right\\}$
$\displaystyle\geq
c\cdot\left[\min\left\\{\frac{1}{2},1-D_{I\mid\boldsymbol{Y}}(\boldsymbol{y})\right\\}-{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime
c})\right]\,,$

where in the last inequality we used

$\frac{{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime})}{2}\geq\frac{1}{2}-{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime
c})\,,$

and, using the notation
$D_{I\mid\boldsymbol{Y}}(\boldsymbol{y})=\max_{i\in[M]}{\mathbb{P}}_{\boldsymbol{y}}(I=i)$,

${\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime})-D_{I\mid\boldsymbol{Y}}(\boldsymbol{y})=1-D_{I\mid\boldsymbol{Y}}(\boldsymbol{y})-{\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime
c})\,.$

Writing $\delta(\boldsymbol{y}):={\mathbb{P}}_{\boldsymbol{y}}(\Omega^{\prime
c})$ with $\operatorname{\mathbb{E}}[\delta(\boldsymbol{Y})]=\delta$, we
finally arrive at

$\displaystyle\operatorname{\mathbb{E}}\bigl{[}\ell(\boldsymbol{Y})\bigr{]}$
$\displaystyle\geq
c\cdot\operatorname{\mathbb{E}}\left[\min\left\\{\frac{1}{2},1-D_{I\mid\boldsymbol{Y}}(\boldsymbol{Y})\right\\}-\delta(\boldsymbol{Y})\right]$
$\displaystyle\geq
c\cdot\left(\frac{1}{2}\cdot{\mathbb{P}}\left(D_{I\mid\boldsymbol{Y}}(\boldsymbol{Y})\leq\frac{1}{2}\right)-\delta\right)\,.$

This is the assertion. ∎

###  2.2 Separating Gaussian mixtures with linear information

######  Lemma 2.4.

Let $(\boldsymbol{v}_{i})_{i=1}^{M}\subset{\mathbb{R}}^{n}$ be a family of
points and $I\sim\operatorname{unif}[M]$ a random index. Define the random
variable $\boldsymbol{Y}:=\boldsymbol{v}_{I}+\boldsymbol{Z}$ with
$\boldsymbol{Z}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},\operatorname{id}_{n})$
being a standard Gaussian vector in ${\mathbb{R}}^{n}$ independent of $I$. For
$r_{1}>0$ consider the set

$\mathfrak{i}:=\left\\{i\in[M]\colon\boldsymbol{v}_{i}\in
r_{1}B_{2}^{n}\right\\}\subseteq[M]\,,$

and write $K:=\\#\mathfrak{i}$. Assume

$\frac{K}{M}\geq\frac{1}{2}\quad\text{and}\quad M\geq
C\cdot\left(r_{1}+3\sqrt{n}\right)^{n}\,,$

where $C=\frac{10e^{3/2}}{3\pi}\approx 4.7552$, and write
$D_{I\mid\boldsymbol{Y}}(\boldsymbol{y})=\max_{i\in[M]}{\mathbb{P}}(I=i\mid\boldsymbol{Y}=\boldsymbol{y})$
as in Lemma 2.3. Then we have

${\mathbb{P}}\left(D_{I\mid\boldsymbol{Y}}(\boldsymbol{Y})\leq\frac{1}{2}\right)\geq\frac{1}{5}\,.$

###### Proof.

The standard Gaussian vector $\boldsymbol{Z}$ possesses the probability
density

$p_{0}(\boldsymbol{z}):=\frac{1}{(2\pi)^{n/2}}\exp\left(-\frac{\|\boldsymbol{z}\|_{2}^{2}}{2}\right)$

which takes its maximum value $\frac{1}{(2\pi)^{n/2}}$ at the origin. The
joint distribution of $(I,\boldsymbol{Y})$ can thus be described by a family
$\\{p_{i}\\}_{i=1}^{M}$ of functions on ${\mathbb{R}}^{d}$,

$p_{i}(\boldsymbol{y}):=\frac{p_{0}(\boldsymbol{y}-\boldsymbol{v}_{i})}{M}\,,\quad\text{giving}\quad{\mathbb{P}}\bigl{(}(I,\boldsymbol{Y})\in
A\bigr{)}=\sum_{i=1}^{M}\int_{{\mathbb{R}}^{n}}p_{i}(\boldsymbol{y})\,\mathds{1}_{\\{(i,\boldsymbol{y})\in
A\\}}\,\mathup{d}\boldsymbol{y}\,,$

where each of the functions $p_{i}$ is bounded above by
$B:=\frac{1}{(2\pi)^{n/2}M}$. The probability density of $\boldsymbol{Y}$ is
given by $p=\sum_{i=1}^{M}p_{i}$. Furthermore, we can give the conditional
probability of $I$ by

${\mathbb{P}}\left(I=i\mid\boldsymbol{Y}=\boldsymbol{y}\right)=\frac{p_{i}(\boldsymbol{y})}{p(\boldsymbol{y})}$

and estimate the probability of interest by

${\mathbb{P}}\left(D_{I\mid\boldsymbol{Y}}(\boldsymbol{Y})\leq\frac{1}{2}\right)\geq{\mathbb{P}}\bigl{(}p(\boldsymbol{Y})>2B\bigr{)}\,.$

We use the concentration bound (24) applied to $\boldsymbol{Z}$ with
$r_{2}=3\sqrt{n}$,

${\mathbb{P}}\bigl{(}\|\boldsymbol{Z}\|_{2}\leq
r_{2}\bigr{)}={\mathbb{P}}\bigl{(}\|\boldsymbol{Z}\|_{2}\leq
3\sqrt{n}\bigr{)}\geq 1-e^{-2n}\geq 1-e^{-2}\,,$

and find the following estimate:

$\displaystyle{\mathbb{P}}\bigl{(}p(\boldsymbol{Y})\geq 2B\bigr{)}$
$\displaystyle\geq{\mathbb{P}}\bigl{(}\|\boldsymbol{Y}\|_{2}\leq
r_{1}+r_{2}\bigr{)}-{\mathbb{P}}\bigl{(}\left(\|\boldsymbol{Y}\|_{2}\leq
r_{1}+r_{2}\right)\wedge\left(p(\boldsymbol{Y})<2B\right)\bigr{)}$
$\displaystyle\geq{\mathbb{P}}(I\in\mathfrak{i})\cdot{\mathbb{P}}\bigl{(}\|\boldsymbol{Z}\|_{2}\leq
r_{2}\bigr{)}-2B\cdot(r_{1}+r_{2})^{n}\cdot\lambda^{n}\left(B_{2}^{n}\right)\,.$

Here, in the second step, for the first term we applied the triangle
inequality to $\boldsymbol{Y}=\boldsymbol{v}_{I}+\boldsymbol{Z}$ and used that
$\boldsymbol{v}_{i}\leq r_{1}$ for $i\in\mathfrak{i}$. The Lebesgue volume of
the $n$-dimensional Euclidean unit ball is given by

$\lambda^{n}\left(B_{2}^{n}\right)=\frac{n^{n/2}}{\Gamma\left(\frac{n}{2}+1\right)}\,.$

We use Stirling’s formula to estimate the Gamma function from below:

$\Gamma\left(\frac{n}{2}+1\right)\geq\sqrt{2\pi}\cdot\underbrace{\sqrt{\frac{n}{2}+1}}_{\geq\sqrt{3/2}}\cdot\left(\frac{n}{2e}\right)^{n/2}\cdot
e^{-1}\cdot\underbrace{\left(1+\frac{2}{n}\right)^{n/2}}_{\in\left[\sqrt{3},e\right]}\geq\frac{3\sqrt{\pi}}{e}\cdot\left(\frac{n}{2e}\right)^{n/2}\,.$

With $r_{2}=3\sqrt{n}$ and the value for $B$, we thus obtain

$\displaystyle{\mathbb{P}}\bigl{(}p(\boldsymbol{Y})\geq 2B\bigr{)}$
$\displaystyle\geq\frac{K}{M}\left(1-e^{-2n}\right)-\frac{2}{(2\pi)^{n/2}M}\cdot\left(r_{1}+3\sqrt{n}\right)^{n}\frac{n^{n/2}}{\Gamma\left(\frac{n}{2}+1\right)}$
$\displaystyle\geq\frac{K}{M}\left(1-e^{-2n}\right)-\frac{2e}{3\sqrt{\pi}}\cdot\left(\frac{e}{\pi}\right)^{n/2}\cdot\left(r_{1}+3\sqrt{n}\right)^{n}\cdot\frac{1}{M}\,.$

Suppose $\frac{K}{M}\geq\frac{1}{2}$, then
$\frac{K}{M}\left(1-e^{-2n}\right)\geq\frac{1}{2}\left(1-e^{-2}\right)>\frac{2}{5}$.
Assuming

$M\geq\frac{10e}{3\sqrt{\pi}}\cdot\left(\frac{e}{\pi}\right)^{n/2}\cdot\,\left(r_{1}+3\sqrt{n}\right)^{n}\,,$

the probability is at least $\frac{1}{5}$ as claimed. Since $\frac{e}{\pi}<1$,
we may simplify $\left(\frac{e}{\pi}\right)^{n/2}\leq\sqrt{\frac{e}{\pi}}$,
the constant in the lemma can be chosen as $C:=\frac{10e^{3/2}}{3\pi}\approx
4.7552$. ∎

The following statement generalizes Lemma 2.4 for arbitrary Gaussian measures
with covariance matrix $\Sigma$. Concerning the notation $\sqrt{\Sigma}$, see
Section A in the appendix.

######  Lemma 2.5.

Let $(\widetilde{\boldsymbol{v}}_{i})_{i=1}^{M}\subset{\mathbb{R}}^{n}$ be a
family of points and $I\sim\operatorname{unif}[M]$ a random index. Define the
random variable
$\widetilde{\boldsymbol{Y}}:=\widetilde{\boldsymbol{v}}_{I}+\widetilde{\boldsymbol{Z}}$
with
$\widetilde{\boldsymbol{Z}}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},\Sigma)$
being a Gaussian vector in ${\mathbb{R}}^{n}$ independent of $I$. The
covariance matrix $\Sigma$ defines the ellipsoid
$E:=\sqrt{\Sigma}(B_{2}^{n})$. Let $r_{1}>0$ and consider the set

$\mathfrak{i}:=\left\\{i\in[M]\colon\widetilde{\boldsymbol{v}}_{i}\in
r_{1}E\right\\}\subseteq[M]\,,$

we write $K:=\\#\mathfrak{i}$. Assume

$\frac{K}{M}\geq\frac{1}{2}\quad\text{and}\quad M\geq
C\cdot\left(r_{1}+3\sqrt{n}\right)^{n}\,,$

with $C>0$ as in Lemma 2.4, and write
$D_{I\mid\widetilde{\boldsymbol{Y}}}(\boldsymbol{y})=\max_{i\in[M]}{\mathbb{P}}(I=i\mid\widetilde{\boldsymbol{Y}}=\boldsymbol{y})$.
Then we have

${\mathbb{P}}\left(D_{I\mid\widetilde{\boldsymbol{Y}}}(\widetilde{\boldsymbol{Y}})\leq\frac{1}{2}\right)\geq\frac{1}{5}\,.$

###### Proof.

If $\Sigma$ is invertible, consider
$\boldsymbol{Y}:=\sqrt{\Sigma^{-1}}\widetilde{\boldsymbol{Y}}=\boldsymbol{v}_{I}+\boldsymbol{Z}$
with $\boldsymbol{v}_{i}:=\sqrt{\Sigma^{-1}}\widetilde{\boldsymbol{v}}_{i}$
and
$\boldsymbol{Z}:=\sqrt{\Sigma^{-1}}\widetilde{\boldsymbol{Z}}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},\operatorname{id}_{n})$.
Since $\widetilde{\boldsymbol{v}}_{i}\in r_{1}E$ is equivalent to
$\boldsymbol{v}_{i}\in r_{1}B_{2}^{n}$, we are precisely in the situation of
Lemma 2.4, the assertion follows.

If the covariance matrix $\Sigma$ is singular with rank $k<n$, find an
orthogonal matrix $Q$ such that $\Sigma=QDQ^{\top}$ with
$D=\operatorname{diag}(\sigma_{1},\ldots,\sigma_{k},0,\ldots,0)$ where
$\sigma_{1},\ldots,\sigma_{k}>0$. We may consider
$\widehat{\boldsymbol{Y}}:=Q^{\top}\widetilde{\boldsymbol{Y}}=\widehat{\boldsymbol{v}}_{I}+\widehat{\boldsymbol{Z}}$
with $\widehat{\boldsymbol{v}}_{i}:=Q^{\top}\widetilde{\boldsymbol{v}}_{i}$
and
$\widehat{\boldsymbol{Z}}:=Q^{\top}\widetilde{\boldsymbol{Z}}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},D)$,
where $\widetilde{\boldsymbol{v}}_{i}\in r_{1}E$ is equivalent to
$\widehat{\boldsymbol{v}}_{i}\in r_{1}\widehat{E}$ with
$\widehat{E}:=\sqrt{D}(B_{2}^{n})\subseteq
U:=\operatorname{span}\\{\boldsymbol{e}_{1},\ldots,\boldsymbol{e}_{k}\\}$,
exploiting $Q^{\top}B_{2}^{n}=B_{2}^{n}$. If we observe
$\widehat{\boldsymbol{Y}}\in U$ then we know that
$\widehat{\boldsymbol{v}}_{I}\in U$, that is, the random index $I$ satisfies

$I\in\mathfrak{i}^{\prime}:=\left\\{i\in[M]\colon\widehat{\boldsymbol{v}}_{i}\in
U\right\\}\subseteq[M]\,.$

The observation $\mathfrak{i}\subseteq\mathfrak{i}^{\prime}$ motivates us to
consider the conditional setting given $I\in\mathfrak{i}^{\prime}$. There we
may resort to a $k$-dimensional standard Gaussian setting using the map
$T\colon(y_{1},\ldots,y_{n})\mapsto\left(y_{1}/\sqrt{\sigma_{1}},\ldots,y_{k}/\sqrt{\sigma_{k}}\right)$,
thus considering $k$-dimensional vectors
$\boldsymbol{Y}^{\prime}:=T\widehat{\boldsymbol{Y}}$ with
$\boldsymbol{v}_{i}^{\prime}:=T\widehat{\boldsymbol{v}}_{i}$ and
$\boldsymbol{Z}^{\prime}:=T\widehat{\boldsymbol{Z}}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},\operatorname{id}_{k})$,
where $\widehat{\boldsymbol{v}}_{i}\in r_{1}\widehat{E}$ is equivalent to
$\boldsymbol{v}_{i}^{\prime}\in r_{1}B_{2}^{k}$. This $k$-dimensional setting
can be compared with an $n$-dimensional setting
$\boldsymbol{Y}=\boldsymbol{v}_{I}+\boldsymbol{Z}$ where
$\boldsymbol{v}_{I}=(\boldsymbol{v}_{I}^{\prime};0,\ldots,0)\in{\mathbb{R}}^{n}$
and
$\boldsymbol{Z}\sim\operatorname{\mathcal{N}}(\boldsymbol{0},\operatorname{id}_{n})$
with $Z_{j}=Z_{j}^{\prime}$ for $j=1,\ldots,k$, so we can write
$\boldsymbol{Y}=(\boldsymbol{Y^{\prime}},\boldsymbol{Y^{\prime\prime}})$.
Obviously, if $\boldsymbol{v}_{I}^{\prime}\in r_{1}B_{2}^{k}$, then also
$\boldsymbol{v}_{I}\in r_{1}B_{2}^{n}$. Similarly to the proof of Lemma 2.4,
the joint distribution of $(I,\boldsymbol{Y}^{\prime})$ conditioned on the
event $\\{I\in\mathfrak{i}^{\prime}\\}$ can be given by a family
$\\{q_{i}\\}_{i\in\mathfrak{i}^{\prime}}$ of shifted Gaussian functions on
${\mathbb{R}}^{k}$ such that for $i\in\mathfrak{i}^{\prime}$ we get

${\mathbb{P}}\left(I=i\mid\boldsymbol{Y}^{\prime}=\boldsymbol{y}^{\prime},I\in\mathfrak{i}^{\prime}\right)=\frac{q_{i}(\boldsymbol{y}^{\prime})}{\sum_{j\in\mathfrak{i}^{\prime}}q_{j}(\boldsymbol{y}^{\prime})}\,,$

and also for $(I,\boldsymbol{Y})$ there is a family
$\\{p_{i}\\}_{i\in\mathfrak{i}^{\prime}}$ of Gaussian functions on
${\mathbb{R}}^{n}$ such that

${\mathbb{P}}\left(I=i\mid\boldsymbol{Y}=\boldsymbol{y},I\in\mathfrak{i}^{\prime}\right)=\frac{p_{i}(\boldsymbol{y})}{\sum_{j\in\mathfrak{i}^{\prime}}p_{j}(\boldsymbol{y})}\,.$

For $i\in\mathfrak{i}^{\prime}$ we can factorize
$p_{i}(\boldsymbol{Y})=p_{i}(\boldsymbol{Y}^{\prime},\boldsymbol{Y}^{\prime\prime})=q_{i}(\boldsymbol{Y^{\prime}})\,\gamma(\boldsymbol{Y^{\prime\prime}})$
where $\gamma$ is the density of the $(n-k)$-dimensional standard Gaussian
distribution, thus

$\frac{p_{i}(\boldsymbol{Y})}{\sum_{j\in\mathfrak{i}^{\prime}}p_{j}(\boldsymbol{Y})}=\frac{q_{i}(\boldsymbol{Y^{\prime}})\,\gamma(\boldsymbol{Y^{\prime\prime}})}{\sum_{j\in\mathfrak{i}^{\prime}}q_{j}(\boldsymbol{Y^{\prime}})\,\gamma(\boldsymbol{Y^{\prime\prime}})}=\frac{q_{i}(\boldsymbol{Y^{\prime}})}{\sum_{j\in\mathfrak{i}^{\prime}}q_{j}(\boldsymbol{Y}^{\prime})}\,.$

With

$D_{I|\boldsymbol{Y}}^{\prime}(\boldsymbol{y}):=\max_{i\in\mathfrak{i}^{\prime}}\frac{p_{i}(\boldsymbol{y})}{\sum_{j\in\mathfrak{i}^{\prime}}p_{j}(\boldsymbol{y})}$

and $M^{\prime}:=\\#\mathfrak{i}^{\prime}$, we can hence write

$\displaystyle{\mathbb{P}}\left(D_{I\mid\widetilde{\boldsymbol{Y}}}(\widetilde{\boldsymbol{Y}})\leq\frac{1}{2}\right)$
$\displaystyle\geq{\mathbb{P}}(I\in\mathfrak{i}^{\prime})\cdot{\mathbb{P}}\left(D_{I\mid\widetilde{\boldsymbol{Y}}}(\widetilde{\boldsymbol{Y}})\leq\frac{1}{2}\;\middle|\;I\in\mathfrak{i}^{\prime}\right)$
$\displaystyle=\frac{M^{\prime}}{M}\cdot{\mathbb{P}}\left(D_{I|\boldsymbol{Y}}^{\prime}(\boldsymbol{Y})\leq\frac{1}{2}\;\middle|\;I\in\mathfrak{i}^{\prime}\right)\,.$

We use Lemma 2.4 for $\boldsymbol{Y}$ conditioned on
$\\{I\in\mathfrak{i}^{\prime}\\}$ where $M^{\prime}$ takes the role of $M$,
with the small modification that we assume
$\frac{K}{M^{\prime}}\geq\frac{M}{2M^{\prime}}$, and $M\geq
C\cdot\left(r_{1}+3\sqrt{n}\right)^{n}$ instead of a bound on $M^{\prime}$.
That way we obtain

${\mathbb{P}}\left(D_{I|\boldsymbol{Y}}^{\prime}(\boldsymbol{Y})\leq\frac{1}{2}\;\middle|\;I\in\mathfrak{i}^{\prime}\right)\geq\frac{M}{5M^{\prime}}\,.$

Combined with the previous estimate, this finishes the proof. ∎

In our main result, Theorem 2.7, we will consider a collection
$(\boldsymbol{u}_{i})_{i\in[m]}$ of points
$\boldsymbol{u}_{i}=\frac{2}{3}\boldsymbol{e}_{i}$ on the coordinate axis,
$M=m$. Thus, given a measurement matrix $N\in{\mathbb{R}}^{n\times m}$, we
have the images
$\boldsymbol{v}_{i}:=N\boldsymbol{u}_{i}=\frac{2}{3}\boldsymbol{c}_{i}$ where
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{m}\in{\mathbb{R}}^{n}$ denote the
colums of $N$. Crucially, however, we only measure
$\boldsymbol{Y}_{i}:=N\boldsymbol{X}_{i}=N\boldsymbol{u}_{i}+\sigma
N\boldsymbol{W}$. In the following we will answer how badly the columns are
separated relative to the noise generated by $N\boldsymbol{W}$.

######  Lemma 2.6.

Let $N\in{\mathbb{R}}^{n\times m}$ be a matrix with columns
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{m}\in{\mathbb{R}}^{n}$. For an
index set $\mathfrak{j}\subset[m]$ let $P_{\mathfrak{j}}$ be the projection
onto the coordinates $j\in\mathfrak{j}$. Using this, write
$\Sigma_{\mathfrak{j}}:=NP_{\mathfrak{j}}N^{\top}$ and define the ellipsoid
$E_{\mathfrak{j}}:=\sqrt{\Sigma_{\mathfrak{j}}}(B_{2}^{n})$. For $2n<m$
consider the set $\mathcal{J}_{2n}$ as in (7) and and let
$\mathfrak{J}\sim\operatorname{unif}{\mathcal{J}_{2n}}$. Then

${\mathbb{P}}\left(\\#\left\\{j\in[m]\colon\boldsymbol{c}_{j}\in
2^{n}E_{\mathfrak{J}}\right\\}\geq\frac{m}{2}\right)\geq\frac{1}{2}\,.$

###### Proof.

The proof goes in two stages. In the first stage we fix one
$\mathfrak{j}\in\mathcal{J}_{2n}$. Our aim is to construct a sufficiently
large set $\widetilde{\mathfrak{m}}$ such that

$j\in\widetilde{\mathfrak{m}}\quad\Longrightarrow\quad\boldsymbol{c}_{j}\in
2^{n}E_{\mathfrak{j}}\,.$ (13)

In the course of our construction we iteratively identify $n$ most important
columns of $N$, described by an index set
$\mathfrak{j}_{n}=\\{j_{1},\ldots,j_{n}\\}\subset\mathfrak{j}$, such that the
ellipsoid $E_{\mathfrak{j}_{n}}$ generated by these $n$ columns is contained
in $E_{\mathfrak{j}}$. The elements of $\widetilde{\mathfrak{m}}$ are
identified by a shrinkage procedure with a nested sequence of candidate sets,

$[m]=\mathfrak{m}_{0}\supset\ldots\supset\mathfrak{m}_{n}\,,$

where for the selected important coordinates $j_{1},\ldots,j_{n}$ we have
$j_{i}\in\mathfrak{m}_{i-1}\setminus\mathfrak{m}_{i}$, and finally
$\widetilde{\mathfrak{m}}=\\{j_{1},\ldots,j_{n}\\}\cup\mathfrak{m}_{n}$. The
geometric idea behind the shrinkage is that after selecting
$j_{1},\ldots,j_{i}$ we define a rectangular set $R_{i}\subset
U_{i}:=\operatorname{span}\\{\boldsymbol{c}_{j_{1}},\ldots,\boldsymbol{c}_{j_{i}}\\}$
such that for $j\in\\{j_{1},\ldots,j_{i}\\}\cup\mathfrak{m}_{i}$ we have
$(\operatorname{id}_{n}-\Pi_{i})\boldsymbol{c}_{j}\in R_{i}$ where
$(\operatorname{id}_{n}-\Pi_{i})$ is the orthogonal projection onto
$U_{i}\subseteq{\mathbb{R}}^{n}$. In the end, for
$j\in\widetilde{\mathfrak{m}}$ our construction guarantees
$\boldsymbol{c}_{j}\in R_{n}$, and we also have $R_{n}\subseteq
2^{n}E_{\mathfrak{j}_{n}}\subseteq 2^{n}E_{\mathfrak{j}}$. What we show here
is therefore actually stronger than (13).

The variables $k_{i}=\\#\left(\\{j_{i}\\}\cup\mathfrak{m}_{i}\right)$ keep
track of how much the candidate set has shrunk so far. In particular, the
distribution of $k_{n}$ regarded as a random variable $K_{n}$, depending on a
random index set $\mathfrak{J}\sim\operatorname{unif}{\mathcal{J}_{2n}}$
instead of a fixed set $\mathfrak{j}$, will help us to understand the typical
size of the set $\widetilde{\mathfrak{m}}$, namely,
$\\#\widetilde{\mathfrak{m}}=k_{n}+n-1$.

Let us now begin with the first stage of the proof and fix
$\mathfrak{j}\in\mathcal{J}_{2n}$. We first describe the construction of
$\widetilde{\mathfrak{m}}$. The iteration is initialized by putting
$\mathfrak{m}_{0}:=[m]$ with $m_{0}:=\\#\mathfrak{m}_{0}=m$, and
$\Pi_{0}:=\operatorname{id}_{n}$. For $i=0,\ldots,n-1$, proceed as follows:

  1. 1.

Sort the elements $j\in\mathfrak{m}_{i}$ according to the standard Euclidean
norm of $\Pi_{i}\boldsymbol{c}_{j}$, that is, find a bijection
$\pi_{i}\colon[m_{i}]\to\mathfrak{m}_{i}$ such that

$\|\Pi_{i}\boldsymbol{c}_{\pi_{i}(1)}\|_{2}\leq\ldots\leq\|\Pi_{i}\boldsymbol{c}_{\pi_{i}(m_{i})}\|_{2}\,.$

  2. 2.

Find the index $j_{i+1}$ from $\mathfrak{j}$ with the largest such norm,

$\displaystyle k_{i+1}$
$\displaystyle:=\max\\{\ell\in[m_{i}]\colon\pi_{i}(\ell)\in\mathfrak{j}\\},$
$\displaystyle j_{i+1}$
$\displaystyle:=\pi_{i}(k_{i+1})\in\mathfrak{j}\cap\mathfrak{m}_{i}\,,$
$\displaystyle\boldsymbol{b}_{i+1}$
$\displaystyle:=\boldsymbol{c}_{j_{i+1}}\,.$

  3. 3.

Define

$\displaystyle\mathfrak{m}_{i+1}$
$\displaystyle:=\left\\{\pi_{i}(\ell)\colon\ell<k_{i+1}\right\\}\subset\mathfrak{m}_{i},$
$\displaystyle m_{i+1}$ $\displaystyle:=\\#\mathfrak{m}_{i+1}=k_{i+1}-1\,,$

and let $\Pi_{i+1}$ be the orthogonal projection onto
$(\operatorname{span}\\{\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{i+1}\\})^{\bot}$.

Finally, we put

$\mathfrak{j}_{i}:=\\{j_{1},\ldots,j_{i}\\},\quad\widetilde{\mathfrak{m}}:=\mathfrak{j}_{n}\cup\mathfrak{m}_{n},\quad\widetilde{m}:=\\#\widetilde{\mathfrak{m}}=m_{n}+n=k_{n}+n-1\,.$
(14)

For this construction, we claim that (13) holds.

The left singular vectors of $NP_{\mathfrak{j}}$ are eigenvectors of
$\Sigma_{\mathfrak{j}}=NP_{\mathfrak{j}}N^{\top}$ and form a basis of
${\mathbb{R}}^{n}$, the respective singular values of the former being the
square roots of the eigenvalues of the latter. Further, for
$\mathfrak{j}^{\prime}\subset\mathfrak{j}\subseteq[m]$, the coordinate
projection $P_{\mathfrak{j}^{\prime}}$ is just a restriction of
$P_{\mathfrak{j}}$. We thus have the following inclusion:

$E_{\mathfrak{j}^{\prime}}=\sqrt{\Sigma_{\mathfrak{j}^{\prime}}}\left(B_{2}^{n}\right)=NP_{\mathfrak{j}^{\prime}}\left(B_{2}^{m}\right)\subseteq
NP_{\mathfrak{j}}\left(B_{2}^{m}\right)=\sqrt{\Sigma_{\mathfrak{j}}}\left(B_{2}^{n}\right)=E_{\mathfrak{j}}\,.$

In particular, for $\mathfrak{j}\in\mathcal{J}_{2n}$ and its accordingly
defined subsets $\mathfrak{j}_{i}$, see above,

$E_{\mathfrak{j}_{1}}\subseteq\ldots\subseteq E_{\mathfrak{j}_{n}}\subseteq
E_{\mathfrak{j}}\,.$

We can compare these ellipsoids to a chain of rectangles
$R_{1}\subseteq\ldots\subseteq R_{n}$,

$R_{i}:=\left\\{\alpha_{1}\Pi_{0}\boldsymbol{b}_{1}+\ldots+\alpha_{i}\Pi_{i-1}\boldsymbol{b}_{i}\colon\alpha_{1},\ldots,\alpha_{i}\in[-1,1]\right\\}\subset{\mathbb{R}}^{n}\,.$

As an intermediate result we aim to show

$j\in\widetilde{\mathfrak{m}}=\mathfrak{j}_{n}\cup\mathfrak{m}_{n}\quad\Longrightarrow\quad\boldsymbol{c}_{j}\in
R_{n}\,.$ (15)

Clearly, the sets $R_{i}$ and $E_{\mathfrak{j}_{i}}$ lie in the space

$U_{i}:=\operatorname{span}\\{\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{i}\\}=\operatorname{span}\\{\Pi_{0}\boldsymbol{b}_{1},\ldots,\Pi_{i-1}\boldsymbol{b}_{i}\\}\,.$

Define

$n_{0}:=\min\left(\\{n\\}\cup\left\\{i\in[n-1]\colon\|\Pi_{i}\boldsymbol{b}_{i+1}\|=0\right\\}\right),$

and note that $U_{n_{0}}=U_{n}$ and $n_{0}=\dim(U_{n})$. By construction, for
all $j\in\mathfrak{m}_{i}$, $i=1,\ldots,n$, we have

$|\langle\Pi_{i-1}\boldsymbol{b}_{i},\boldsymbol{c}_{j}\rangle|=|\langle\Pi_{i-1}\boldsymbol{b}_{i},\Pi_{i-1}\boldsymbol{c}_{j}\rangle|\leq\|\Pi_{i-1}\boldsymbol{b}_{i}\|\cdot\|\Pi_{i-1}\boldsymbol{c}_{j}\|\leq\|\Pi_{i-1}\boldsymbol{b}_{i}\|^{2}\,.$

Hence, using the orthogonal basis
$(\Pi_{0}\boldsymbol{b}_{1},\ldots,\Pi_{n_{0}-1}\boldsymbol{b}_{n_{0}})$ of
$U_{n}$, we can write

$\boldsymbol{c}_{j}=\sum_{i=1}^{n_{0}}\underbrace{\frac{\langle\Pi_{i-1}\boldsymbol{b}_{i},\boldsymbol{c}_{j}\rangle}{\|\Pi_{i-1}\boldsymbol{b}_{i}\|^{2}}}_{\in[-1,1]\text{
if }j\in\mathfrak{m}_{i}}\Pi_{i-1}\boldsymbol{b}_{i}\,.$

This shows $\boldsymbol{c}_{j}\in R_{n_{0}}=R_{n}$ for
$j\in\mathfrak{m}_{n}\subset\ldots\subset\mathfrak{m}_{1}$. Similarly,
$\boldsymbol{b}_{i}=\boldsymbol{c}_{j_{i}}\in U_{i}$, where
$j_{i}\in\mathfrak{m}_{i-1}$, can be given in the form

$\boldsymbol{b}_{i}=\sum_{\ell=1}^{\min\\{n_{0},i\\}}\underbrace{\frac{\langle\Pi_{\ell-1}\boldsymbol{b}_{\ell},\boldsymbol{b}_{i}\rangle}{\|\Pi_{\ell-1}\boldsymbol{b}_{\ell}\|^{2}}}_{\in[-1,1]}\Pi_{\ell-1}\boldsymbol{b}_{\ell}\,,$
(16)

implying $\boldsymbol{b}_{i}\in R_{i}\subseteq R_{n}$. We thus arrive at the
intermediate result (15).

To prove (13), it remains to show

$R_{n}\subseteq 2^{n}\,E_{\mathfrak{j}}\,.$

This can be done by inductively proving

$R_{i}=\left\\{\sum_{\ell=1}^{i}\alpha_{\ell}\Pi_{\ell-1}\boldsymbol{b}_{\ell}\colon\max_{\ell\in[i]}|\alpha_{\ell}|\leq
1\right\\}\\\
\subseteq{\textstyle\sqrt{\frac{4^{i}-1}{3}}}\,E_{\mathfrak{j}_{i}}=\left\\{\sum_{\ell=1}^{i}z_{\ell}\boldsymbol{b}_{\ell}\colon\sum_{\ell=1}^{i}z_{\ell}^{2}\leq\frac{4^{i}-1}{3}\right\\}\,.$
(17)

For $i=1$, by $\Pi_{0}\boldsymbol{b}_{1}=\boldsymbol{b}_{1}$ and
$\frac{4^{1}-1}{3}=1$, the assertion $R_{1}\subseteq E_{\mathfrak{j}_{1}}$
holds with equality. For $i=2,\ldots,n$, from (16) we know

$\boldsymbol{b}_{i}-\Pi_{i-1}\boldsymbol{b}_{i}=\sum_{\ell=1}^{\min\\{n_{0},i-1,n-1\\}}\underbrace{\frac{\langle\Pi_{\ell-1}\boldsymbol{b}_{\ell},\boldsymbol{b}_{i}\rangle}{\|\Pi_{\ell-1}\boldsymbol{b}_{\ell}\|^{2}}}_{\in[-1,1]}\Pi_{\ell-1}\boldsymbol{b}_{\ell}\in
R_{i-1}\,.$

Hence, an element $\boldsymbol{y}\in R_{i}$ may be written with
$\boldsymbol{y}^{\prime}\in R_{i-1}$ and $|\alpha_{\ell}|\leq 1$ in the form

$\boldsymbol{y}=\boldsymbol{y}^{\prime}+\alpha_{\ell}\Pi_{i-1}\boldsymbol{b}_{i}=\underbrace{\bigl{(}\boldsymbol{y}^{\prime}-\alpha_{\ell}\,(\boldsymbol{b}_{i}-\Pi_{i-1}\boldsymbol{b}_{i})\bigr{)}}_{\in
2R_{i-1}}+\,\alpha_{\ell}\boldsymbol{b}_{i}\,.$

Using the induction assumption $2R_{i-1}\subseteq
2\sqrt{\frac{4^{i-1}-1}{3}}\,E_{\mathfrak{j}_{i-1}}$, there is a
representation

$\boldsymbol{y}=\sum_{\ell=1}^{i-1}z_{\ell}\boldsymbol{b}_{\ell}+\alpha_{i}\boldsymbol{b}_{i}\quad\text{with}\quad\sum_{\ell=1}^{i-1}z_{\ell}^{2}+\alpha_{i}^{2}\leq
4\cdot\frac{4^{i-1}-1}{3}+1=\frac{4^{i}-1}{3}\,.$

This proves (17). Before we proceed with the second part of the proof, note
that for all stages $i=1,\ldots,n$ of the construction, we have
$\\#(\mathfrak{m}_{i}\cap\mathfrak{j})=2n-i$.

For the second part of the proof, instead of a fixed set $\mathfrak{j}$, let
$\mathfrak{J}$ be drawn uniformly from $\mathcal{J}_{2n}$. The construction
given in the first part of the proof is now to be understood as random, in
particular the quantities in (14), most prominently $\widetilde{M}=K_{n}+n-1$
which we write with a capital letter to stress the randomness. By the
geometric considerations above, this random variable $\widetilde{M}$ serves as
a lower bound for the quantity of interest:

$\\#\left\\{j\in[m]\colon\boldsymbol{c}_{j}\in
2^{n}E_{\mathfrak{J}}\right\\}\geq\widetilde{M}\,.$

If the set $\mathfrak{J}$ is random, the value $k_{i+1}$ in step 2 of the
construction is random as well, so we write $K_{i+1}$ instead to indicate that
this is now a random variable. In order to understand the distribution of
$K_{i+1}$, let us first write the random set
$\mathfrak{J}=\\{K_{1}^{\prime},\ldots,K_{2n}^{\prime}\\}$ with random
elements in decaying order $K_{1}^{\prime}>\ldots>K_{2n}^{\prime}$. Obviously,
$K_{1}$ and $K_{1}^{\prime}$ have the same distribution. Further, let
$i\in[n-1]$, fix $m-i+1\geq k_{i}>k_{i+1}\geq 2n-i$, and, by counting all
remaining possibilities for $\mathfrak{J}$, observe that

${\mathbb{P}}(K_{i+1}^{\prime}=k_{i+1}\mid
K_{i}^{\prime}=k_{i})={\mathbb{P}}(K_{i+1}=k_{i+1}\mid K_{i}=k_{i})\,.$

In other words, the distribution of $K_{i+1}$ does not depend on the
particular set $\mathfrak{j}_{i}$ and the particular ordering $\pi_{i}$ the
construction would yield for a given realization of $\mathfrak{J}$. Hence,
$K_{i}$ and $K_{i}^{\prime}$ have the same distribution for $i=1,\ldots,n$.

For the special case of even $m=2k$, we can split $[m]$ into two parts $[k]$
and $[m]\setminus[k]$ of equal cardinality. By symmetry of the distribution of
$\mathfrak{J}$,

$\displaystyle{\mathbb{P}}(K_{n}^{\prime}\geq k+1)$
$\displaystyle={\mathbb{P}}\bigl{(}\\#(\mathfrak{J}\cap[m]\setminus[k])\geq
n\bigr{)}$ $\displaystyle={\mathbb{P}}\bigl{(}\\#(\mathfrak{J}\cap[k])\geq
n\bigr{)}$ $\displaystyle={\mathbb{P}}(K_{n+1}^{\prime}\leq k)$
$\displaystyle=1-{\mathbb{P}}(K_{n+1}^{\prime}\geq k+1)$
$\displaystyle[K_{n+1}^{\prime}<K_{n}^{\prime}]\qquad$ $\displaystyle\geq
1-{\mathbb{P}}(K_{n}^{\prime}\geq k+1)\,,$

therefore

${\mathbb{P}}(K_{n}\geq k+1)={\mathbb{P}}(K_{n}^{\prime}\geq
k+1)\geq\frac{1}{2}\,,$

which by $\widetilde{M}\geq K_{n}$ shows the assertion. For odd $m=2k+1$ the
calculation is similar except that one equality becomes the inequality

${\mathbb{P}}\bigl{(}\\#(\mathfrak{J}\cap[m]\setminus[k])\geq
n\bigr{)}\geq{\mathbb{P}}\bigl{(}\\#(\mathfrak{J}\cap[k])\geq n\bigr{)}\,,$

further, $k+1=\lceil\frac{m}{2}\rceil>\frac{m}{2}$ in this case. ∎

###  2.3 Main results for non-adaptive Monte Carlo methods

The following theorem is the main result of this paper.

######  Theorem 2.7.

For $m\geq C\cdot e^{an^{2}}$ with suitable constants $C,a>0$, we have

$e^{\textup{ran},\textup{nonada}}(n,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\geq\frac{1}{3}\left(\frac{1}{20}-e^{-4}\right)=:\varepsilon_{0}\approx
0.010561>0\,.$

Hence, for $\varepsilon\in(0,\varepsilon_{0})$ we have the complexity

$n^{\textup{ran},\textup{nonada}}(\varepsilon,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\geq\sqrt{\frac{\log\frac{m}{C}}{a}}\,.$

###### Proof.

We work with Bakhvalov’s technique for the setup of measures $\widetilde{\mu}$
and $\mu$ as described in generality in Section 2.1 where $\widetilde{\mu}$ is
the distribution of a random vector
$\boldsymbol{X}=\boldsymbol{u}_{I}+\sigma\boldsymbol{W}$. Here now we consider
a simple setting with $M=m$ points
$\boldsymbol{u}_{i}=\frac{2}{3}\boldsymbol{e}_{i}$, each containing only one
non-zero coordinate, a random index $I\sim\operatorname{unif}[m]$, and a
Gaussian disturbance $\boldsymbol{W}$ into $2n$ random directions. The scaling
parameter is chosen to be $\sigma:=\frac{1}{18n}$, and the truncated measure
$\mu$ is supported on the $\ell_{1}$-balls $F_{i}$ of radius
$r_{0}=\frac{1}{3}$ around the points $\boldsymbol{u}_{i}$. As before, we
truncate with the event $\Omega^{\prime}$, see (10), and via (25) applied to
the $2n$-dimensional Gaussian distribution this yields a truncation
probability

$\delta={\mathbb{P}}(\Omega^{\prime
c})={\mathbb{P}}\left(\|\boldsymbol{W}\|_{1}>\frac{r_{0}}{\sigma}\right)<e^{-4n}\leq
e^{-4}\approx 0.018316\,,$

and an $\ell_{1}$-separation distance

$\operatorname{dist}_{1}(F_{i},F_{i^{\prime}})=\lVert\boldsymbol{u}_{i}-\boldsymbol{u}_{i^{\prime}}\rVert_{1}-2r_{0}=\frac{2}{3}$

for $i\neq i^{\prime}$. The $\ell_{\infty}$-separation can be traced back to
the distance of the coordinate projections of $F_{i}$ and $F_{i^{\prime}}$
onto the two-dimensional space
$\operatorname{span}\\{\boldsymbol{e}_{i},\boldsymbol{e}_{i^{\prime}}\\}$,
namely

$\operatorname{dist}_{\infty}(F_{i},F_{i^{\prime}})=\frac{\operatorname{dist}_{1}(F_{i},F_{i^{\prime}})}{2}=\frac{1}{3}=:c>0\,.$

Our aim is to provide a lower bound on the performance of randomized
algorithms. It turns out to be easier to analyse “extended” algorithms that
base their output not only on the linear information
$\boldsymbol{Y}=N\boldsymbol{X}$ but on the extended information
$\widetilde{\boldsymbol{Y}}:=(\boldsymbol{Y},\mathfrak{J})$. By Lemma 2.1, a
lower bound on the error of the extended algorithms
$\widetilde{\phi}(\boldsymbol{Y},\mathfrak{J})$ is also a lower bound for
simple algorithms $\phi(\boldsymbol{Y})$. Lemma 2.3 gives

$\operatorname{\mathbb{E}}\left[\|\boldsymbol{X}-\widetilde{\phi}(\boldsymbol{Y},\mathfrak{J})\|_{\infty}\cdot\mathds{1}_{\Omega^{\prime}}\right]\geq
c\cdot\left(\frac{1}{2}\cdot{\mathbb{P}}\left(D_{I\mid\boldsymbol{Y},\mathfrak{J}}(\boldsymbol{Y},\mathfrak{J})\leq\frac{1}{2}\right)-\delta\right),$
(18)

where
$D_{I\mid\boldsymbol{Y},\mathfrak{J}}(\boldsymbol{y},\mathfrak{j})=\max_{i\in[M]}{\mathbb{P}}(I=i\mid\boldsymbol{Y}=\boldsymbol{y},\mathfrak{J}=\mathfrak{j})$.
Conditioned on $\\{\mathfrak{J}=\mathfrak{j}\\}$, the disturbance $\sigma
N\boldsymbol{W}$ has the covariance matrix $\sigma\Sigma_{\mathfrak{j}}$ in
the information space ${\mathbb{R}}^{n}$, associated with the ellipsoid
$\sigma E_{\mathfrak{j}}$, see the notation of Lemma 2.6. We apply Lemma 2.5,
namely, provided $m\geq C\cdot\left(r_{1}+3\sqrt{n}\right)^{n}$, if for
$\mathfrak{j}\in\mathcal{J}_{2n}$ we have

$\\#\left\\{j\in[m]\colon N\boldsymbol{u}_{j}\in r_{1}\sigma
E_{\mathfrak{j}}\right\\}\geq\frac{m}{2}\,,$

then

${\mathbb{P}}\left(D_{I\mid\boldsymbol{Y},\mathfrak{J}}(\boldsymbol{Y},\mathfrak{J})\leq\frac{1}{2}\;\middle|\;\mathfrak{J}=\mathfrak{j}\right)\geq\frac{1}{5}\,.$

With $N\boldsymbol{u}_{j}=\frac{2}{3}\boldsymbol{c}_{j}$ and
$\sigma=\frac{1}{18n}$, Lemma 2.6 shows that this prerequisite is met with
probability

${\mathbb{P}}\left(\\#\left\\{j\in[m]\colon N\boldsymbol{u}_{j}\in r_{1}\sigma
E_{\mathfrak{J}}\right\\}\geq\frac{m}{2}\right)\geq\frac{1}{2}$

if we choose $r_{1}=12n\cdot 2^{n}$, which then leads to

${\mathbb{P}}\left(D_{I\mid\boldsymbol{Y},\mathfrak{J}}(\boldsymbol{Y},\mathfrak{J})\leq\frac{1}{2}\right)\geq\frac{1}{5}\cdot\frac{1}{2}=\frac{1}{10}\,.$

Plugging this into (18), for any algorithm $\phi\circ N$ we obtain the error
bound

$e^{\mu}(\phi\circ
N,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\geq\frac{1}{3}\cdot\left(\frac{1}{2}\cdot\frac{1}{10}-e^{-4}\right)=:\varepsilon_{0}\approx
0.010561\,.$

The condition $m\geq C\cdot\left(r_{1}+3\sqrt{n}\right)^{n}$ we need for the
application of Lemma 2.5 can be replaced by a stronger condition, namely

$m\geq C\cdot e^{an^{2}}\geq C\cdot\left(12n\cdot
2^{n}+3\sqrt{n}\right)^{n}\,,$

with suitable $a>0$. (A universal choice would be $a=3\log(3)\approx 3.2951$
with equality for $n=1$, but for $n\geq 18$ we could take $a=1$. However, no
matter how much we restrict $n$, we always have $a>\log(2)\approx 0.6931$.) By
Bakhvalov’s technique, we are done. ∎

######  Remark 2.8.

The main result shows a lower bound of order $\sqrt{\log m}$ for the
complexity $n$ when aiming for a small error $\varepsilon>0$. In view of the
upper bounds we conjecture that a lower bound of order $\log m$ would be
optimal. The gap seems to be caused by the rather pessimistic inflation factor
$2^{n}$ in Lemma 2.6. Any improvement that replaces this factor by something
polynomial in $n$ would lead to a lower bound of order $\frac{\log m}{\log\log
m}$.

Still, establishing these lower bounds, we have a first proof that the
difficulty of the problem $\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$ grows
with $m$, allowing to establish an approximability result for general linear
problems, see Section 2.4. Quantitatively, our bounds are yet good enough to
compare the non-adaptive setting with adaptive algorithms and prove a result
on the possible gaps, see Section 3.

######  Corollary 2.9.

For the identical embedding $\ell_{1}\hookrightarrow\ell_{\infty}$ we have

$\lim_{n\rightarrow\infty}e^{\textup{ran},\textup{nonada}}(n,\ell_{1}\hookrightarrow\ell_{\infty})\geq\varepsilon_{0}>0\,.$

######  Remark 2.10.

For deterministic algorithms and $n\geq 1$ we have

$e^{\det}(n,\ell_{1}\hookrightarrow\ell_{\infty})=\frac{1}{2}\,,$

see [27, Prop 11.11.10]. The result in [27] is formulated for approximation
numbers, that is, the error of deterministic linear algorithms, but since the
error is measured in the supremum norm, linear algorithms are optimal in the
deterministic setting, see [5] or [26, Thms 4.5 and 4.8]. We conjecture that
randomized methods cannot improve upon the deterministic error in this
infinite-dimensional problem, which would mean that we could replace
$\varepsilon_{0}$ by $\frac{1}{2}$ in Corollary 2.9, and we speculate that
this even holds for adaptive randomized methods.

###  2.4 Impossibility to approximate non-compact operators

A linear operator $S$ between Banach spaces is called _approximable_ with
respect to an error notion $e(n,S)$ if

$e(n,S)\xrightarrow[n\to\infty]{}0\,.$

######  Theorem 2.11.

Let $F,G$ be Banach spaces. An operator $S:F\rightarrow G$ is approximable
with respect to $e^{\textup{ran},\textup{nonada}}$ if and only if $S$ is
compact.

To prove Theorem 2.11 we need a result from [15] which shows that the
identical embedding embedding $\ell_{1}\hookrightarrow\ell_{\infty}$ is in a
sense a universal non-compact operator.

######  Proposition 2.12.

Let $X,Y$ be Banach spaces and $S:\ell_{1}\rightarrow\ell_{\infty}$ be the
identical embedding. A bounded operator $T:X\rightarrow Y$ is non-compact if
and only if there exist bounded operators $B\colon\ell_{1}\to X$, $C\colon
Y\to\ell_{\infty}$ such that $S=CTB$, that is, the following diagram commutes:

${X}$${Y}$${{\ell_{1}}}$${{\ell_{\infty}}}$$\scriptstyle{T}$$\scriptstyle{C}$$\scriptstyle{S}$$\scriptstyle{B}$

###### Proof of Theorem 2.11.

Compact operators are approximable with respect to deterministic algorithms.
Since each deterministic algorithm is formally also a randomized algorithm
(with trivial dependence on $\omega$) we get that compactness of $T$ is
sufficient for approximability.

Now we show that compactness of $T$ is also necessary. Let $T$ be non-compact
and consider the factorization $S=CTB$ of the identical embedding
$S:\ell_{1}\hookrightarrow\ell_{\infty}$ from Proposition 2.12. We may assume
$\|B\|=1$, otherwise rescale $B^{\prime}:=\|B\|^{-1}B$ and
$C^{\prime}:=\|B\|C$ to get $S=C^{\prime}TB^{\prime}$. Aiming at a
contradiction, assume that there exists a sequence of randomized non-adaptive
algorithms $\widetilde{A}_{n}=\widetilde{\phi}_{n}\circ\widetilde{N}_{n}$ for
$n\in{\mathbb{N}}$ which approximates $T$ arbitrarily well, that is,
$e^{\textup{ran}}\bigl{(}\widetilde{A}_{n},T\bigr{)}$ converges to zero.
Define the algorithms $A_{n}=\phi_{n}\circ N_{n}$ with
$\phi_{n}:=C\circ\widetilde{\phi}_{n}$ and $N_{n}:=\widetilde{N}_{n}\circ B$
for approximating $\ell_{1}\hookrightarrow\ell_{\infty}$. It is
straightforward to check that

$e^{\textup{ran}}(A_{n},\ell_{1}\hookrightarrow\ell_{\infty})\leq\|C\|\cdot
e^{\textup{ran}}\bigl{(}\widetilde{A}_{n},T\bigr{)}\xrightarrow[n\to\infty]{}0\,.$

This is a contradiction to Corollary 2.9. ∎

##  3 Upper bounds for adaptive algorithms

Theorem 2.7 is a lower bound for _non-adaptive_ algorithms applied to the
approximation problem $\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$. As
mentioned in the introduction, this bound holds for all embeddings
$\ell_{p}^{m}\hookrightarrow\ell_{q}^{m}$ with $p,q\in[1,\infty]$, namely, we
have

$e^{\textup{ran},\textup{nonada}}(n,\ell_{p}^{m}\hookrightarrow\ell_{q}^{m})\geq\varepsilon_{0}>0$

for $m\geq Ce^{an^{2}}$ with suitable constants $C,a>0$. As it turns out,
adaptive randomized algorithms can do significantly better than non-adaptive
algorithms in this regime of very large $m$, at least for embeddings
$\ell_{1}^{m}\hookrightarrow\ell_{q}^{m}$ with $q\in[2,\infty]$, as Theorem
3.1 shows. The theorem is stated for
$\ell_{1}^{m}\hookrightarrow\ell_{2}^{m}$, but of course this upper bound also
holds for the easier problems with smaller $\ell_{q}^{m}$-norms, that is,
$q>2$, in particular for $\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$.

The upper bound of Theorem 3.1 is based on an adaptive sparse recovery
algorithm due to Woodruff et al. [14, 21, 22]. A vector $\boldsymbol{x}$ is
called $k$-sparse if it has at most $k$ non-zero entries. For general
$\boldsymbol{x}=(x_{j})_{j\in[m]}\in{\mathbb{R}}^{m}$, Woodruff et al. aim to
find an approximation $\boldsymbol{x}^{\ast}$ that is close to the best
$k$-term approximation with an $\ell_{2}/\ell_{2}$-type of guarantee, namely,
for some error demand $\epsilon>0$, we shall have

$\|\boldsymbol{x}-\boldsymbol{x}^{\ast}\|_{2}\leq\min_{\boldsymbol{x}^{\prime}\colon\text{$k$-sparse}}(1+\epsilon)\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\|_{2}$
(19)

with high probability. Their algorithm works in two stages. The first stage
reduces the $k$-sparse recovery problem to a $1$-sparse recovery problem by
randomly sampling a subset $\mathfrak{m}\subset[m]$ of the big index set where
$\\#\mathfrak{m}\asymp\frac{\epsilon m}{k}$ (the authors discuss several
adaptive and non-adaptive reduction methodologies). With a certain
probability, the reduced vector
$\boldsymbol{x}_{\mathfrak{m}}:=(x_{j})_{j\in\mathfrak{m}}$ for such a
candidate set $\mathfrak{m}\subset[m]$ contains one “heavy coordinate”
$j^{\ast}\in\mathfrak{m}$ in the sense of
$|x_{j^{\ast}}|\gg\|\boldsymbol{x}_{\mathfrak{m}\setminus\\{j^{\ast}\\}}\|_{2}$.
The second stage of the algorithm is a shrinkage procedure
$\mathfrak{m}=\mathfrak{m}_{0}\supset\mathfrak{m}_{1}\supset\ldots\supset\\{j^{\prime}\\}$,
eventually identifying $j^{\ast}=j^{\prime}$ with high probability of success.
Within each shrinkage step $\mathfrak{m}_{i}\supset\mathfrak{m}_{i+1}$, we
compare a random linear measurement of $\boldsymbol{x}_{\mathfrak{m}_{i}}$
with a slightly disturbed measurement to further narrow down the location of
$j^{\ast}$. The crucial point is that this shrinking process becomes easier
the larger the heavy coordinate is compared to the remaining coordinates of
the candidate set. This allows for an accelerated adaptive shrinkage that
requires only $\mathcal{O}\left(\log\log\frac{\epsilon m}{k}\right)$ steps.
Repeating this $1$-sparse recovery for a number of $K\asymp\frac{k}{\epsilon}$
initial candidate sets, the algorithm yields an index set
$\mathfrak{K}\subset[m]$, $\\#\mathfrak{K}\leq K$, which hopefully contains
(most of) the $k$ largest coordinates. The corresponding entries can be
measured exactly and the output $\boldsymbol{x}^{\ast}$ of the algorithm is
defined as

$x^{\ast}_{j}:=\begin{cases}x_{j}&\text{if }j\in\mathfrak{K},\\\
0&\text{else.}\end{cases}$

This also means that, even if the algorithm fails to identify the $k$ largest
coordinates, the error is bounded by the norm of the input vector,
$\|\boldsymbol{x}-\boldsymbol{x}^{\ast}\|_{2}\leq\|\boldsymbol{x}\|_{2}$.

######  Theorem 3.1.

Using adaptive randomized algorithms we obtain the upper bound

$e^{\textup{ran}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\preceq\sqrt{\frac{\log\log\frac{m}{n}}{n}}\,,$

which holds for $n\in{\mathbb{N}}$ and $m\geq cn$ with a suitable constant
$c>0$.

###### Proof.

We use the adaptive randomized algorithm of Indyk, Price and Woodruff [14, Alg
3.2] together with the improvements of Yi Li, Nakos and Woodruff [21, Thm 11].
For any $\boldsymbol{x}\in{\mathbb{R}}^{m}$, one gets a (random)
$\boldsymbol{x}^{*}$ such that

$\|\boldsymbol{x}-\boldsymbol{x}^{*}\|_{2}\leq
2\|\boldsymbol{x}-\boldsymbol{x}_{k}\|_{2}$

with probability $1-\exp(-k^{0.99})$, where $\boldsymbol{x}_{k}$ is the best
approximation of $\boldsymbol{x}$ by a $k$-sparse vector. The algorithm
requires

$n\asymp k\,\log\log\frac{m}{k}$

adaptive linear measurements (for $m\geq 16k$).

It is well-known (see, e.g., [4]) that for $1\leq p<q$ and $m>k$ we have

$\|\boldsymbol{x}-\boldsymbol{x}_{k}\|_{q}\leq k^{-r}\|\boldsymbol{x}\|_{p},$

where $r=1/p-1/q$. Here, we consider the case $(p,q)=(1,2)$ and assume
$\|\boldsymbol{x}\|_{1}\leq 1$. If we aim for an expected error smaller or
equal $\varepsilon\in(0,\frac{1}{2})$, we may apply the algorithm of Woodruff
et al. for $k=\lceil 16\varepsilon^{-2}\rceil$ to guarantee an error of at
most $2k^{-1/2}\leq\frac{\varepsilon}{2}$ with probability
$1-\exp(-k^{0.99})$. Here we need

$n\asymp\varepsilon^{-2}\,\log\log(m\varepsilon^{2})$ (20)

adaptive random measurements. In case the algorithm fails to identify the $k$
most important coordinates, the error will still be bounded by $1$. The
failure probability is at most $\exp(-k^{0.99})\leq\frac{\varepsilon}{2}$, so
the expected error is then bounded by

$e^{\textup{ran}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\leq\left(1-\exp(-k^{0.99})\right)\cdot\frac{\varepsilon}{2}+\exp(-k^{0.99})\cdot
1\leq\varepsilon\,,$

as claimed. Finally, we use (20) to derive an error bound in terms of $n$ and
$m$. The restriction $m\geq 16k$ gives $m\varepsilon^{2}\geq 256$. Further,
from (20) we know that there exists a constant $c>0$ such that

$\displaystyle n\leq c\,\varepsilon^{-2}\log\log(m\varepsilon^{2})$
$\displaystyle\quad\Longleftrightarrow\quad\varepsilon^{2}\leq
c\,\frac{\log\log(m\varepsilon^{2})}{n}$ (21)
$\displaystyle\quad\Longleftrightarrow\quad\log(m\varepsilon^{2})\leq\log\frac{cm}{n}+\log\log\log(m\varepsilon^{2})\,.$

Since $\log\log t<\frac{t}{10}$ for $t>1$, here with
$t=\log(m\varepsilon^{2})>\log 256$, we have

$\log(m\varepsilon^{2})\leq\frac{10}{9}\log\frac{cm}{n}\,.$

This eventually, together with (21), gives the desired bound,

$\varepsilon\leq\sqrt{c\,\frac{\log\left(\frac{10}{9}\log\frac{cm}{n}\right)}{n}}\asymp\sqrt{\frac{\log\log\frac{m}{n}}{n}}\,,$

where the weak asymptotic equivalence holds for, say, $m\geq
16\max\\{1,c^{-1}\\}\,n$. ∎

######  Remark 3.2.

From the deterministic error asymptotics for the problem
$\ell_{1}^{m}\hookrightarrow\ell_{2}^{m}$, see (1) in the introduction of this
paper, it follows that if $m\succeq e^{n}$ then the error of deterministic
algorithms is larger than a constant $\varepsilon_{0}>0$ that does not depend
on $n$ or $m$. Therefore, the bound in Theorem 3.1 is a great improvement
which is possible if adaptive randomized algorithms are allowed and $m$ is
large.

Also the improvement over non-adaptive randomized algorithms is substantial.
Consider the case $m=\bigl{\lceil}Ce^{an^{2}}\bigr{\rceil}$ such that

$e^{\textup{ran},\textup{nonada}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})\geq
e^{\textup{ran},\textup{nonada}}(n,\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m})\geq\varepsilon_{0}>0\,.$

Together with Theorem 3.1 we obtain the following consequence.

######  Corollary 3.3.

For $m=\bigl{\lceil}Ce^{an^{2}}\bigr{\rceil}$ with the constants $C,a>0$ from
Theorem 2.7, we obtain

$\frac{e^{\textup{ran}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})}{e^{\textup{ran},\textup{nonada}}(n,\ell_{1}^{m}\hookrightarrow\ell_{2}^{m})}\preceq\sqrt{\frac{\log
n}{n}}$

for large $n$.

######  Remark 3.4.

In the corollary above we consider a different problem for every $n$, so an
obvious question is: Do we find an infinite-dimensional problem $S$ such that
the gap of Corollary 3.3 can be observed for this single problem? The answer
is yes up to logarithmic terms. Inspired by constructions in [13, Sec 5], we
consider the following example defined with the constants $C,a>0$ from Theorem
2.7 and some $\alpha>0$:

$\displaystyle N_{k}:=2^{k},\quad
m_{k}:=\bigl{\lceil}Ce^{aN_{k}^{2}}\bigr{\rceil}\qquad\text{for
}k\in{\mathbb{N}}\,,$ $\displaystyle
S\colon\ell_{1}\to\ell_{2},\;\boldsymbol{x}\mapsto\boldsymbol{z}\quad\text{where
}z_{i}:=\begin{cases}x_{i}&\text{for }1\leq i\leq m_{1}\\\
\frac{x_{i}}{\sqrt{k}\,(\log k)^{1/2+\alpha}}&\text{for }m_{k-1}<i\leq
m_{k},\;k\geq 2\,.\end{cases}$

Clearly, we can employ Theorem 2.7 to find non-adaptive lower bounds for
$k\geq 2$:

$\displaystyle e^{\textup{ran},\textup{nonada}}(N_{k},S)$
$\displaystyle\geq\frac{e^{\textup{ran},\textup{nonada}}(N_{k},\ell_{1}^{m_{k}}\hookrightarrow\ell_{2}^{m_{k}})}{\sqrt{k}\,(\log
k)^{1/2+\alpha}}\geq\frac{\varepsilon_{0}}{\sqrt{k}\,(\log k)^{1/2+\alpha}}$
$\displaystyle\asymp(\log N_{k})^{-1/2}\,(\log\log N_{k})^{-1/2-\alpha}\,.$

For the upper bounds we define ‘splitting’ indices $l_{j}:=2^{j}$ for
$j\in{\mathbb{N}}$, and index sets $\mathfrak{m}_{1}:=[m_{l_{1}}]$,
$\mathfrak{m}_{j}:=[m_{l_{j}}]\setminus[m_{l_{j-1}}]$ for $j\geq 2$. Given a
total budget of $N_{k}=2^{k}$ pieces of information, we spend at most $n_{j}$
information functionals on the approximation of
$\boldsymbol{x}_{\mathfrak{m}_{j}}$ for $j=1,\ldots,k$, where the individual
budgets form a decaying sequence:

$n_{j}:=\left\lfloor
c_{\alpha}^{-1}\,j^{-1-2\alpha}\,N_{k}\right\rfloor=\left\lfloor
c_{\alpha}^{-1}\,j^{-1-2\alpha}\,2^{k}\right\rfloor,\quad
c_{\alpha}:=\sum_{j=1}^{\infty}j^{-1-2\alpha}\,.$

If $n_{j}$ is large enough, we can employ an adaptive algorithm $A_{n_{j}}$
with budget of at most $n_{j}$ as in the proof of Theorem 3.1 for
approximating $\boldsymbol{x}_{\mathfrak{m}_{j}}$. Since these algorithms are
homogeneous, i.e. $A_{n_{j}}(\lambda\boldsymbol{x}_{\mathfrak{m}_{j}})=\lambda
A_{n_{j}}(\boldsymbol{x}_{\mathfrak{m}_{j}})$ for scalar factors $\lambda\neq
0$, we have the following error bounds, valid under a constraint $m\geq
cn_{j}$:

$\operatorname{\mathbb{E}}\|\boldsymbol{x}_{\mathfrak{m}_{j}}-A_{n_{j}}(\boldsymbol{x}_{\mathfrak{m}_{j}})\|_{2}\preceq\|\boldsymbol{x}_{\mathfrak{m}_{j}}\|_{1}\cdot\sqrt{\frac{\log\log\frac{\\#\mathfrak{m}_{j}}{n_{j}}}{n_{j}}}\,.$

With $\log_{2}N_{k}=k$ and
$\log\log\frac{\\#\mathfrak{m}_{j}}{n_{j}}\preceq\log\log(\\#\mathfrak{m}_{j})\preceq\log
N_{l_{j}}\preceq l_{j}=2^{j}$, and inserting the value of $n_{j}$, we can
simplify this estimate to

$\operatorname{\mathbb{E}}\|\boldsymbol{x}_{\mathfrak{m}_{j}}-A_{n_{j}}(\boldsymbol{x}_{\mathfrak{m}_{j}})\|_{2}\preceq\|\boldsymbol{x}_{\mathfrak{m}_{j}}\|_{1}\cdot\sqrt{\frac{2^{j}\cdot
j^{1+2\alpha}}{2^{k}}}\,.$ (22)

Since for $m\leq n_{j}$ there is an algorithm $A_{n_{j}}$ that recovers
$\boldsymbol{x}_{\mathfrak{m}_{j}}$ exactly, by adjusting the implicit
constant, (22) extends to $n_{j}>m/c$ as well. If, however, $n_{j}$ is too
small to give an error bound of, say,
$\frac{1}{2}\|\boldsymbol{x}_{\mathfrak{m}_{j}}\|_{1}$, than the zero
algorithm $A_{0}(\boldsymbol{x}_{\mathfrak{m}_{j}})=\boldsymbol{0}$ produces
an error at most
$\|\boldsymbol{x}_{\mathfrak{m}_{j}}\|_{2}\leq\|\boldsymbol{x}_{\mathfrak{m}_{j}}\|_{1}$,
so (22) holds true for all $j$, even if $n_{j}$ is small or even zero for
certain large $j$. By approximating $\boldsymbol{x}_{\mathfrak{m}_{j}}$ for
$j=1,\ldots,k$, we can find an approximation of
$\boldsymbol{z}_{\mathfrak{m}_{j}}$, while approximating the tail
$\boldsymbol{z}_{{\mathbb{N}}\setminus[m_{l_{k}}]}$ with zero. Applying the
triangle inequality to the definition of the Monte Carlo error, we obtain the
following adaptive upper bound:

$\displaystyle e^{\textup{ran}}(N_{k},S)$
$\displaystyle\preceq\sup_{\|\boldsymbol{x}\|_{1}\leq
1}\left(\frac{\|\boldsymbol{x}_{{\mathbb{N}}\setminus[m_{l_{k}}]}\|_{1}}{2^{k/2}\cdot
k^{1/2+\alpha}}+\sum_{j=1}^{k}\frac{\|\boldsymbol{x}_{\mathfrak{m}_{j}}\|_{1}}{\max\\{2^{(j-1)/2}\cdot(j-1)^{1/2+\alpha},1\\}}\cdot\sqrt{\frac{2^{j}\cdot
j^{1+2\alpha}}{2^{k}}}\right)\,,$
$\displaystyle\preceq\max\left\\{\frac{1}{2^{k/2}\cdot
k^{1/2+\alpha}},\frac{1}{2^{j/2}\cdot
j^{1/2+\alpha}}\cdot\sqrt{\frac{2^{j}\cdot j^{1+2\alpha}}{2^{k}}}\text{ for
}j=1,\ldots,k\right\\}$ $\displaystyle=2^{-k/2}=\frac{1}{\sqrt{N_{k}}}\,.$

Since $N_{k}$ is chosen in dyadic steps, we find an asymptotic gap for all
integers $n\geq 2$:

$\frac{e^{\textup{ran}}(n,S)}{e^{\textup{ran},\textup{nonada}}(n,S)}\preceq\sqrt{\frac{\log
n}{n}}\cdot(\log\log n)^{1/2+\alpha}\,.$

######  Remark 3.5.

Having found such a gap, we may pose the question: How much can be gained in
general with respect to optimal error bounds if we choose the $n$ pieces of
linear information adaptively and/or randomly? This question is studied for
general linear problems $S:F\to G$ between Banach spaces $F$ and $G$ in [18].
Using inequalities between $s$-numbers it turns out that the maximal gap is of
the order $n$ for general spaces and of the order $n^{1/2}$ if $F$ or $G$ is a
Hilbert space. In an upcoming paper [20], new upper bounds for the adaptive
approximation of $\ell_{1}^{m}\hookrightarrow\ell_{\infty}^{m}$ will show a
gap of order $n$ (up to logarithmic terms), and for
$\ell_{2}^{m}\hookrightarrow\ell_{\infty}^{m}$ we can also show a gap of order
$n^{1/2}$.

##  Appendix A Gaussian measures

A vector $\boldsymbol{Z}=(Z_{1},\ldots,Z_{m})$ in ${\mathbb{R}}^{m}$ is called
a _standard Gaussian vector_ if its entries are independent standard Gaussian
random variables,
$Z_{j}\stackrel{{\scriptstyle\textup{iid}}}{{\sim}}\operatorname{\mathcal{N}}(0,1)$.
For any given point $\boldsymbol{c}\in{\mathbb{R}}^{m}$ and any given positive
semi-definite matrix $\Sigma\in{\mathbb{R}}^{m\times m}$ we can construct a
Gaussian random vector with _mean_ $\boldsymbol{c}$ and _covariance matrix_
$\Sigma$ by

$\boldsymbol{X}:=\boldsymbol{c}+\sqrt{\Sigma}\boldsymbol{Z}\sim\operatorname{\mathcal{N}}(\boldsymbol{c},\Sigma)\,.$

Here, $\sqrt{\Sigma}$ is defined via the functional calculus for self-adjoint
matrices, that is, for diagonal matrices
$D=\operatorname{diag}(\sigma_{1},\ldots,\sigma_{m})$ with non-negative
entries we define
$\sqrt{D}=\operatorname{diag}(\sqrt{\sigma_{1}},\ldots,\sqrt{\sigma_{m}})$,
and for $\Sigma=QDQ^{\top}$ with an orthogonal matrix $Q$ we have
$\sqrt{\Sigma}=Q\sqrt{D}Q^{\top}$. Further, for any matrix
$A\in{\mathbb{R}}^{n\times m}$, the following vector is a Gaussian vector in
${\mathbb{R}}^{n}$:

$\boldsymbol{Y}:=A\boldsymbol{X}\sim\operatorname{\mathcal{N}}(A\boldsymbol{c},A\Sigma
A^{\top})\,.$ (23)

We cite a very basic version of concentration of Gaussian vectors around the
expectation of its norm, see [29, pp. 180/181] or [1, Lem 2.1.6] for a more
general statement.

######  Lemma A.1.

Let $\boldsymbol{Z}$ be a standard Gaussian vector in ${\mathbb{R}}^{m}$ and
$\|\cdot\|_{\ast}$ an arbitrary norm on ${\mathbb{R}}^{m}$ with
$\ell_{2}$-Lipschitz constant

$L_{\ast}:=\sup_{\boldsymbol{0}\neq\boldsymbol{z}\in{\mathbb{R}}^{m}}\frac{\|\boldsymbol{z}\|_{\ast}}{\|\boldsymbol{z}\|_{2}}\,.$

Then for $t>0$ we have

${\mathbb{P}}\bigl{(}\|\boldsymbol{Z}\|_{\ast}>\operatorname{\mathbb{E}}\|\boldsymbol{Z}\|_{\ast}+t\bigr{)}\leq\exp\left(-\frac{t^{2}}{2L_{\ast}^{2}}\right)\,.$

The expected $\ell_{2}$-norm of a standard Gaussian vector $\boldsymbol{Z}$ in
${\mathbb{R}}^{m}$ is easily estimated from above:

$\operatorname{\mathbb{E}}\|\boldsymbol{Z}\|_{2}\leq\sqrt{\operatorname{\mathbb{E}}\|\boldsymbol{Z}\|_{2}^{2}}=\sqrt{\sum_{j=1}^{m}\operatorname{\mathbb{E}}Z_{j}^{2}}=\sqrt{m}\,.$

With $L_{2}=1$, for $t=2\sqrt{m}$ we obtain

${\mathbb{P}}\left(\|\boldsymbol{Z}\|_{2}>3\sqrt{m}\right)\leq{\mathbb{P}}\left(\|\boldsymbol{Z}\|_{2}>\operatorname{\mathbb{E}}\|\boldsymbol{Z}\|_{2}+2\sqrt{m}\right)\leq
e^{-2m}\,.$ (24)

For $\boldsymbol{z}\in{\mathbb{R}}^{m}$ we have
$\|\boldsymbol{z}\|_{1}\leq\sqrt{m}\cdot\|\boldsymbol{z}\|_{2}$. Hence,

${\mathbb{P}}\left(\|\boldsymbol{Z}\|_{1}>3m\right)\leq{\mathbb{P}}\left(\sqrt{m}\cdot\|\boldsymbol{Z}\|_{2}>3m\right)={\mathbb{P}}\left(\|\boldsymbol{Z}\|_{2}>3\sqrt{m}\right)\leq
e^{-2m}\,.$ (25)

## Acknowledgements

We thank Stefan Heinrich, Aicke Hinrichs, and Thomas Kühn for valuable hints.
We also thank the anonymous referees for carefully reading the manuscript. The
initial version of the paper was written in summer 2023 during the first
author’s temporary employment at TU Chemnitz, Faculty of Mathematics.

## References

  * [1] R.J. Adler and J.E. Taylor, _Random Fields and Geometry_ , Springer Monographs in Mathematics, Springer New York, 2009.
  * [2] Khanh Do Ba, P. Indyk, E. Price, and D.P. Woodruff, _Lower bounds for sparse recovery_ , Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete Algorithms (2010), 1190–1197.
  * [3] N.S. Bakhvalov, _On the approximate calculation of multiple integrals_ , Vestnik MGU, Ser. Math. Mech. Astron. Phys. Chem. 4 (1959), 3–18 (Russian), English translation in J. Complexity 31(4) (2015), 502–516.
  * [4] A. Cohen, W. Dahmen, and R. DeVore, _Compressed sensing and best $k$-term approximation_, J. of the AMS 22 (2009), 211–231.
  * [5] J. Creutzig and P. Wojtaszczyk, _Linear vs. nonlinear algorithms for linear problems_ , J. Complexity 20 (2004), 807–820.
  * [6] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich, _The Gelfand widths of $\ell_{p}$-balls for $0<p\leq 1$_, J. Complexity 26 (2010), 629–640.
  * [7] S. Foucart and H. Rauhut, _A Mathematical Introduction to Compressive Sensing_ , Applied and Numerical Harmonic Analysis, Springer New York, 2013.
  * [8] A.Yu. Garnaev and E.D. Gluskin, _On widths of the euclidean ball_ , Soviet Math. Dokl. 30(1) (1984), 200–204.
  * [9] S. Heinrich, _Lower bounds for the complexity of Monte Carlo function approximation_ , J. Complexity 8 (1992), 277–300.
  * [10] , _Randomized complexity of parametric integration and the role of adaption I. Finite dimensional case_ , J. Complexity 81 (2024), 101821.
  * [11] , _Randomized complexity of parametric integration and the role of adaption II. Sobolev spaces_ , J. Complexity 82 (2024), 101823.
  * [12] , _Randomized complexity of vector-valued approximation_ , preprint on arXiv:2306.13697 [math.NA] (2024).
  * [13] , _Randomized complexity of mean computation and the adaption problem_ , preprint on arXiv:2401.14100 [math.NA] (2025).
  * [14] P. Indyk, E. Price, and D.P. Woodruff, _On the power of adaptivity in sparse recovery_ , 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011, pp. 285–294.
  * [15] W. Johnson, _A universal non-compact operator_ , Colloquium Mathematicum 23 (1971), 267–268.
  * [16] B.S. Kashin, _On Kolmogorov diameters of octohedra_ , Sov. Math. Dokl. 15 (1974), 304–307.
  * [17] A. Klenke, _Probability Theory: A Comprehensive Course_ , Springer, 2014.
  * [18] D. Krieg, E. Novak, and M. Ullrich, _On the power of adaption and randomization_ , in preparation.
  * [19] R.J. Kunsch, _High-dimensional function approximation: Breaking the curse with Monte Carlo methods_ , Dissertation, FSU Jena, available on arXiv:1704.08213 [math.NA] (2017).
  * [20] R.J. Kunsch and M. Wnuk, _Uniform approximation of vectors using adaptive randomized information_ , in preparation.
  * [21] Yi Li, V. Nakos, and D. P. Woodruff, _On low-risk heavy hitters and sparse recovery schemes_ , arXiv:1709.02819 [hep-th].
  * [22] , _On Low-Risk Heavy Hitters and Sparse Recovery Schemes_ , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) (Dagstuhl, Germany) (Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 116, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 19:1–19:13.
  * [23] P. Mathé, _Random approximation of Sobolev embeddings_ , J. Complexity 7 (1991), 261–281.
  * [24] , _A minimax principle for the optimal error of Monte Carlo methods_ , Constr. Approx. 9 (1993), 23–39.
  * [25] E. Novak, _On the power of adaption_ , J. Complexity 12 (1996), 199–237.
  * [26] E. Novak and H. Woźniakowski, _Tractability of Multivariate Problems, Volume I: Linear Information_ , European Mathematical Society, 2008.
  * [27] A. Pietsch, _Operator Ideals_ , North-Holland Publishing Company, 1980.
  * [28] A. Pinkus, _n-Widths in Approximation Theory_ , Springer Berlin, Heidelberg, 1985.
  * [29] G. Pisier, _Probabilistic methods in the geometry of Banach spaces_ , Probability and Analysis, Springer Berlin Heidelberg, 1986, pp. 167–241.
  * [30] E. Price and D. Woodruff, _Lower bounds for adaptive sparse recovery_ , Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2013, pp. 652–663.