Phase Retrieval: Stability and Recovery Guarantees

Introduction

where $w_{i}$ is noise, and $a_{i}$ are a set of known vectors. Since only the magnitude of ${\langle a_{i},x\rangle}$ is measured, and not the phase (or the sign, in the real case), this problem is referred to as phase retrieval. Phase retrieval problems arise in many areas of optics, where the detector can only measure the magnitude of the received optical wave. Several important applications of phase retrieval include X-ray crystallography, transmission electron microscopy and coherent diffractive imaging .

Many methods have been developed for phase recovery which often rely on prior information about the signal, such as positivity or support constraints. One of the most popular techniques is based on alternating projections, where the current signal estimate is transformed back and forth between the object and the Fourier domains. The prior information and observations are used in each domain in order to form the next estimate. Two of the main approaches of this type are Gerchberg-Saxton and Fienup . In general, these methods are not guaranteed to converge, and often require careful parameter selection and sufficient prior information.

To circumvent the difficulties associated with alternating projections, more recently, phase retrieval problems have been treated using semidefinite relaxation, and low-rank matrix recovery ideas . In several masks where used in the measurement process in order to ensure the ability to retrieve the phase. Another approach to generate robust solutions is to assume that the input signal $x$ is sparse, namely, that it contains only a few non-zeros values in an appropriate basis expansion. Sparsity has long been exploited in signal processing, applied mathematics, statistics and computer science for tasks such as compression, denoising, model selection, image processing and more. Despite the great interest in exploiting sparsity in various applications, most of the work to date has focused on recovering sparse or low rank data from linear measurements . Recently, the basic sparse recovery problem has been generalized to the case in which the measurements are quadratic , or given by a more general nonlinear transform of the unknown input . The first paper to consider sparse phase retrieval was , based on semidefinite relaxation combined with a row-sparsity constraint on the resulting matrix. An iterative thresholding algorithm was then proposed that approximates the solution. Similar approaches were later used in . An alternative algorithm was recently designed in using a greedy search method which is far more efficient than the semidefinite relaxation, and often yields more accurate solutions.

Despite the vast interest in phase retrieval, there has been little theoretical work on the fundamental limits of this problem. One important question in this context is how many measurements are needed in order to ensure robust recovery of the input $x$, regardless of the specific recovery method used. Several recent works treat this problem. Most of the papers discuss the case in which $x$ is a general input, namely, there is no sparsity (or other) constraint on $x$. The first result of this kind was obtained in , where it is shown that with probability one $N=4n-2$ randomized equations are sufficient for recovery using a brute force (intractable) method, when there is no noise. However, it is not clear whether a stable recovery method exists with this number of measurements. In the authors consider the case in which $a_{i}$ are real or complex vectors that are either uniform on the sphere of radius $\sqrt{n}$, or iid zero-mean Gaussian vectors with unit variance. Under these assumptions they show that on the order of $n$ measurements are needed in order to recover a generic $x$ using a semidefinite relaxation approach. In the presence of noise, it is shown in that one can find an estimate $\hat{x}$ satisfying

for some $\phi$, where $C_{0}$ is a constant and $w$ is the noise vector that is assumed to be bounded so that $\|w\|_{1}$ is finite.

The paper treats the case in which the input $x$ is $k$-sparse and $a_{i}$ are iid zero-mean normal vectors. When there is no noise, they show that in the real case $N\geq 4k-1$ measurements are needed for uniqueness and in the complex case, $N\geq 8k-2$ measurements are required. They further prove that if $N$ is on the order of $k^{2}\log n$ then the solution can be obtained using a sparse semidefinite relaxation approach as in .

It turns out that the natural complexity parameter for this problem is the same as the one used for analyzing stability in linear measurements, as we will discuss in Section 5. Thus, in a rather general sense, the number of measurements required for stable recovery in the quadratic setting we treat here is of the same order of magnitude as the one needed to ensure stability under linear sampling. In that sense there is no substantial price to be paid for not knowing the phase of the measurements, and for very general choices of input sets $T$.

The second main result of this article deals with the noisy phase retrieval problem. More specifically, we consider recovering an input $x$ in a set $T$ from noisy measurements of the form (1.1). A straightforward approach is to seek the value of $x$ that minimizes the empirical risk (or a least-squares approach). Since this leads to a nonconvex problem, finding its global solution is in general not possible. Nonetheless, we show that if one can find a value ${\hat{x}}$ for which the empirical risk is bounded by a given, computable constant (which depends on the set $T$), then $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}$ is bounded above by an expression that once again depends on the complexity parameter of the set, and which converges to faster than $N^{-1/2+\delta}$ for any $\delta>0$. Here $x_{0}$ is the true (unknown) input. The complexity parameter that determines the rate in the noisy setting is essentially the same as in the stability analysis. Moreover, the resulting sample complexity is of the same order of magnitude as in the linear case in the examples of sets $T$ we consider. An exact formulation of both main results is presented in the next section.

The reminder of the article is organized as follows. The problem and the main results are formulated in Section 2. Stability results in the noise-free setting are developed in Section 3, while the noisy setting is treated in Section 4. In Section 5 the relation between the results in the quadratic case and those in the linear setting are discussed.

Problem Formulation and Main Results

Our goal is to study conditions under which stable recovery is possible irrespective of the specific recovery method used, and to develop guarantees that ensure that empirical minimization or approximate empirical minimization (namely, least-squares recovery) lead to an estimate $\hat{x}$ that is close to $x$ in a squared-error sense.

If $F$ is a class of functions on a probability space $(\Omega,\mu)$, then it is $L$-subgaussian if for every $f,h\in F\cup\{0\}$ and every $t\geq 1$

where $X$ is distributed according to $\mu$.

Our goal is to study when the mapping $\phi(Ax)$ is both invertible and stable first, when $w=0$ (the noise-free case) and second, in the presence of noise.

2 Stability Results

The mapping $\phi(Ax)$ is stable with a constant $C$ in a set $T$ if for every $s,t\in T$,

Note that stability in a set is a much stronger property than invertibility. Indeed, for the latter it suffices that if $s\not=\pm t$ then $\|\phi(At)-\phi(As)\|_{1}>0$, but without any quantitative estimate on the difference.

Let $(g_{i})_{i=1}^{n}$ be independent Gaussian random variables, that have mean zero and variance $1$. Set

Throughout this section, we will refer to $\rho_{T,N}$ as the complexity measure of $T$.

The main result in the noise free case is the following:

For every $L\geq 1$ there exist constants $c_{1},c_{2}$ and $c_{3}$ that depend only on $L$ for which the following holds. Let $\mu$ be an isotropic, $L$-subgaussian measure. Then, for $u\geq c_{1}$, with probability at least $1-2\exp(-c_{2}u^{2}\min\{N,E^{2}\})$, for every $s,t\in T$,

To put Theorem 2.4 in the right perspective, one has to obtain lower bounds on $\kappa(s-t,s+t)$ and upper bounds on $\rho_{T,N}$. Since the latter depends on the number of measurements $N$, its behavior provides insight into the number of measurements that are needed for stability.

In particular, the result is true for a random Gaussian matrix $A$, where $c_{1},c_{2},c_{3}$ and $c_{4}$ are absolute constants.

Interestingly, it can be shown that in the case of linear measurements, stable recovery is guaranteed as long as $N\sim k\log(en/k)$. Thus, the number of measurements needed for stable recovery in the nonlinear and linear settings is the same up to multiplicative constants – at least for ensembles that have a well behaved $\inf_{v,w\in S^{n-1}}\kappa(v,w)$. As mentioned in the introduction, this observation is not a coincidence and will be explained in more detail in Section 5.

In Section 3.2 we study other choices of $T$, and the number of measurements needed in order to guarantee stability.

3 Noisy Recovery Results

Section 4 is devoted to the case in which the measurements are contaminated with iid noise. The goal is to find a point $\hat{x}$ for which $\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}$ is small, using the data $(a_{i},y_{i})_{i=1}^{N}$ and the fact that $y$ is generated according to (1.1) for some $x_{0}\in T$.

A natural approach is to recover $x_{0}$ from $y$ by minimizing the empirical risk:

be the Gaussian complexity of $T$, where $g_{1},...,g_{n}$ are iid standard Gaussian variables, and put

Suppose that for a given $1<p\leq 2$, and $u\geq 1$ (which will later on govern our probability estimates), one produces ${\hat{x}}$ satisfying

Here $\||w|^{p}\|_{\psi_{\alpha}}$, $1\leq\alpha\leq 2$ is a measure of the decay properties of the noise, and will be defined formally in (4.1), $Q_{T,N}$ is a complexity measure similar to $\rho_{T,N}$ (defined formally in (4.8)), and $Q_{T,N,W}=Q_{T,N}+\||w|^{p}\|_{\psi_{1}}/\sqrt{N}$. Our main result shows that, with high probability, such a point ${\hat{x}}$ is close to either $x_{0}$ or to $-x_{0}$. To find an appropriate ${\hat{x}}$, it is possible, for example, to use the greedy method of with different starting points and stop once a solution that satisfies the bound is found.

For every $\kappa>0$ and every $L\geq 1$ there exists constants $c_{1},c_{2},c_{3}$ and $c_{4}$ that depend only on $L$ and $\kappa$, for which the following holds. Let $a$ be distributed according to an isotropic, $L$-subgaussian measure, and assume that $\kappa_{T}\geq\kappa$ where $\kappa_{T}=\inf_{s,t\in T}\kappa(s,t)$. Assume further that $\|w\|_{\psi_{2}}<\infty$. For every integer $N$ set

Let ${\hat{x}}$ be chosen to satisfy (2.11). Then, for $u\geq c_{2}$, with probability at least $1-2\exp(-c_{3}u^{1/3})$,

4 Technical Tool

The main technical tool needed in the proof of both main results is a general estimate on properties of empirical processes indexed by $\{fh:f\in F,\ h\in H\}$. Although the result is true in a far more general situation than needed here, for the sake of simplicity we will present it only in the cases required. We refer the reader to for the more general statement and precise results.

Stability Results

In this section we present the proof of Theorem 2.4, followed by estimates on the values of $\kappa(v,w)$ and $\rho_{T,N}$ appearing in the theorem.

Therefore, to establish the desired stability result, it suffices to show that

By Theorem 2.8 for F=\{|\bigl{<}v,\cdot\bigr{>}|:v\in T_{+}\} and H=\{|\bigl{<}w,\cdot\bigr{>}|:w\in T_{-}\}, it follows that if $N\geq c_{1}E^{2}$ and $u\geq c_{2}$ then with probability at least $1-2\exp(-c_{3}u^{2}E^{2})$,

The claim now follows immediately from the definition of $z_{s,t}$ and of $\kappa(s-t,s+t)$.

Let $(T,d)$ be a compact metric space. For every $\varepsilon>0$, let $N(T,d,\varepsilon)$ be the smallest number of open balls of radius $\varepsilon$ needed to cover $T$. The numbers $N(T,d,\varepsilon)$ are called the $\varepsilon$-covering numbers of $T$ relative to the metric $d$.

The upper bound is due to Dudley and the lower to Sudakov . The proof of both bounds may be found, for example, in .

It is straightforward to verify that the gap between the upper and lower bounds in Proposition 3.3 is at most $\sim\sqrt{\log n}$, and in all the examples we study below, the resulting estimate is sharp.

2.2 Bounding κ𝜅\kappa

Here, we present two simple methods for bounding $\inf_{v,w\in S^{n-1}}\kappa(v,w)$ from below. These methods are not the only possibilities by which one may obtain such a bound; rather, they serve as an indication that the assumption on $\kappa$ is less restrictive than may appear at first glance.

If $a$ satisfies the small ball assumption with constant $c$ then

Proof. Consider $\varepsilon$ for which $c\varepsilon\leq 1/4$. Then for every $v\in S^{n-1}$, there is an event of measure at least $3/4$ on which |\bigl{<}v,a\bigr{>}|\geq\varepsilon. Hence, for two fixed vectors $v,w\in S^{n-1}$,

The following lemma is standard (see e.g. ).

The desired small-ball estimate clearly follows from the lemma, since

The second method, which we only outline, is based on the Paley-Zygmund argument.

Let $Z$ be a random variable, set $0<p<q$ and put $c_{p,q}=\|Z\|_{L_{p}}/\|Z\|_{L_{q}}$. Then, for every $0\leq\lambda\leq 1$,

We will use the lemma for $p=2$ and $q>2$. Assume that $(X_{i})_{i=1}^{n}$ are iid copies of a symmetric, variance $1$ random variable and set $a=(X_{1},...,X_{n})$. If $v,w\in S^{n-1}$, then a straightforward computation shows that

Using the fact that $\|v\|_{2}=\|w\|_{2}=1$, (3.2.2) reduces to

On the other hand, if the reverse inequality holds, then using

Let $X$ be a symmetric, variance $1$ random variable, with a finite $L_{2q}$ moment for some $q>2$. If $a=(X_{1},...,X_{n})$ then

where $c$ depends on $q$ and on $\|X\|_{L_{2q}}$.

Proof. Assume that $X\in L_{2q}$ for some $q>2$. Observe that if $v\in S^{n-1}$ then for every $2\leq r\leq 2q$, \|\bigl{<}a,v\bigr{>}\|_{L_{r}}\leq c_{r}\|X\|_{L_{r}}. Indeed, by a Rosenthal type inequality (see, e.g. , Section 1.5),

Since $\|X\|_{L_{r}}\geq\|X\|_{L_{2}}$ and $\|v\|_{r}\leq\|v\|_{2}=1$, the claim follows.

Therefore, \sup_{v\in S^{n-1}}\|\bigl{<}a,v\bigr{>}\|_{L_{2q}}\leq c_{q}\|X\|_{L_{2q}}, and thus,

3 Examples

Let us turn to a few special cases of Theorem 2.4. To that end, explicit expressions for $\rho_{T,N}$ are required for the sets of interest.

The corollary follows from the fact that with this choice of $N$, $cu^{3}\rho_{T,N}$ is proportional to $\kappa/2$.

When $\kappa$ is given by a constant, independent of the dimension $n$, Corollary 3.8 implies that it is sufficient to choose $N\sim n$ to ensure stable recovery with high probability.

3.2 Sparse Vectors

where $(v_{i}^{*})_{i=1}^{n}$ is a monotone rearrangement of $(|v_{i}|)_{i=1}^{n}$. It is standard to check (see, e.g., ) that there is an absolute constant $c$ such that for every $1\leq k\leq n/4$,

For every $L\geq 1$ there are constants $c_{1}$, $c_{2}$ and $c_{3}$ that depend only on $L$ and for which the following holds. If $\inf_{v,w\in U_{k}}\kappa(v,w)\geq\kappa$, $u\geq c_{1}$ and $N\geq c_{2}u^{3}k\log(en/k)/\kappa^{2}$, then with probability at least $1-2\exp(-c_{3}uk\log(en/k))$, for every $s,t\in S_{k}$,

When $\kappa$ is an absolute constant, Corollary 3.8 implies that it is sufficient to choose $N\sim k\log(en/k)$ to ensure stable recovery with high probability.

3.3 Finite Set

Therefore, $E\lesssim\sqrt{\log|T|^{2}}\sim\sqrt{\log{|T|}}$, implying that

For every $L\geq 1$ there are constants $c_{1}$, $c_{2}$ and $c_{3}$ that depend only on $L$ and for which the following holds. If $\inf_{v,w\in T_{+}}\kappa(v,w)\geq\kappa$, $u\geq c_{1}$ and $N\geq c_{2}u^{3}\log|T|/\kappa^{2}$, then with probability at least $1-2\exp(-c_{3}u\log|T|)$, for every $s,t\in T$,

In this case, with constant $\kappa$, $N\sim\log|T|$ measurements ensure stable recovery with high probability.

3.4 Block Sparse Vectors

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. For every $0<\varepsilon<1/2$,

Proof. Let $I_{J}=\{i\in I_{j},\ j\in J\}$ and observe that

where for every $I\subset\{1,...,n\}$, $S^{I}$ is the Euclidean sphere on the coordinates $I$. Clearly, there are at most $\binom{n/d}{k}$ such subsets $J$. Using a standard volumetric estimate (see, e.g., ), for every fixed set $J$ and every $\varepsilon<1/2$, one needs at most $(5/\varepsilon)^{d|J|}=(5/\varepsilon)^{dk}$ Euclidean balls of radius $\varepsilon$ to cover $S^{I_{J}}$. Therefore, for every $0<\varepsilon<1/2$,

The second part of the claim is an immediate consequence of Proposition 3.3 and the fact that $N(T,\varepsilon)$ is a decreasing function of $\varepsilon$.

For every $L\geq 1$ there are constants $c_{1}$, $c_{2}$ and $c_{3}$ that depend only on $L$ and for which the following holds. If $\inf_{v,w\in W_{k}}\kappa(v,w)\geq\kappa$, $u\geq c_{1}$ and $N\geq c_{2}u^{3}(k\log(en/(dk))+dk)/\kappa^{2}$, then with probability at least $1-2\exp(-c_{3}u(k\log(en/(dk))+dk))$, for every $s,t\in S_{k}^{d}$,

When $\kappa$ is constant we conclude that $N\sim k(\log(en/(kd))+d)$ measurements are needed for stability. This result is consistent with that of which shows that the same value $N$ ensures that a random Gaussian matrix satisfies the block restricted isometry constant.

Noisy Measurements

Next, consider the phase retrieval problem in the presence of noise. The goal is to find an estimate ${\hat{x}}$ of the true signal $x_{0}$ that is close to $x_{0}$ (or $-x_{0}$) in a squared error sense.

for some $x_{0}\in T$. Let $a$ be an isotropic, $L$-subgaussian random vector and assume that the noise $w$ is independent of $a$, symmetric, and of reasonable decay properties, which will be specified in Assumption 4.1 below.

Given $(a_{i},y_{i})_{i=1}^{N}$, combined with the information that the noisy data $y_{i}$ is generated by a point $x_{0}\in T$ via (4.1), is it possible to produce an estimate ${\hat{x}}\in T$ for which $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}$ is small?

Note that the error is measured by the product $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}$, since it is impossible to distinguish between $x_{0}$ and $-x_{0}$.

The answer to this question is affirmative, as shown in Theorem 4.8.

Throughout our analysis we assume that the noise $w$ decays properly. In order to quantify this decay we rely on the notion of $\psi_{\alpha}$ random variables, which are defined below (see as general references for properties of $\psi_{\alpha}$ random variables).

Let $X$ be a random variable. For $1\leq\alpha\leq 2$ let

and denote by $L_{\psi_{\alpha}}$ the set of random variables for which $\|X\|_{\psi_{\alpha}}<\infty$.

The $\psi_{\alpha}$ norm can be characterized using information on the tail of $X$. Indeed, there exists an absolute constant $c$, for which, if $t\geq 1$, then $Pr(|X|\geq t)\leq 2\exp(-ct^{\alpha}/\|X\|_{\psi_{\alpha}}^{\alpha})$. The reverse direction is also true, that is, if $Pr(|X|\geq t)\leq 2\exp(-t^{\alpha}/A^{\alpha})$, then $\|X\|_{\psi_{\alpha}}\leq c_{1}A$ for an absolute constant $c_{1}$.

It is well known that $\|\ \|_{\psi_{\alpha}}$ is a norm on $L_{\psi_{\alpha}}$, and that

In the language of the previous section, $X$ is $L$-subgaussian if and only if $\|X\|_{\psi_{2}}\leq cL\|X\|_{L_{2}}$. Since the $\psi_{\alpha}$ norms have a natural hierarchy, it follows that if $X$ is $L$-subgaussian then

Therefore, if $X$ is $L$-subgaussian and mean-zero then $\|X\|_{\psi_{2}}\sim_{L}\sigma_{X}$, where $\sigma_{X}$ is the standard deviation of $X$.

A straightforward application of the tail behavior of a $\psi_{\alpha}$ random variable implies that if $X_{1},...,X_{N}$ are independent copies of $X$ and $t\geq 1$, then

From the definition of the $\psi_{\alpha}$ norm it is evident that if $\alpha=\beta/q$ then

and in particular, $X\in L_{\psi_{\beta}}$ for $\beta>1$ if and only if $|X|^{\beta}\in L_{\psi_{1}}$.

Although there are versions of the following theorem (and of Definition 4.2) for any $0<\alpha$, for the sake of simplicity, we shall restrict ourselves to the case $\alpha=1$, which is the setting needed in the proofs below.

There exists an absolute constant $c_{1}$ for which the following holds. If $X\in L_{\psi_{1}}$ and $X_{1},...,X_{N}$ are independent copies of $X$, then for every $t>0$,

Combining Theorem 4.3 and (4.4) leads to the following corollary:

Let $p>1$ and assume that $w$ is a random variable for which $|w|^{p}\in L_{\psi_{1}}$ (or $w\in L_{\psi_{p}}$). Then, with probability at least $1-2\exp(-ct)$,

The corollary follows immediately from Theorem 4.3 by taking $t^{\prime}=\sqrt{t/N}$ for $0<t<N$, and since $\||w|^{p}\|_{\psi_{1}}=\|w\|_{\psi_{p}}^{p}$.

For every $L>1$ there exist constants $c_{1}$, $c_{2},c_{3}$ and $c_{4}$ that depend only on $L$ and for which the following holds. If $u\geq c_{1}$, then with probability at least $1-2\exp(-c_{2}u\log N)$,

2 The Recovery Algorithm

The assumptions we make throughout this section are as follows:

Assume that $a$ is isotropic and subgaussian, and that the noise $w$ in (4.1) is a symmetric, $\psi_{2}$ random variable that is independent of $a$.

Recall that the goal is to find an estimate ${\hat{x}}$ of $x_{0}$ that is close to $x_{0}$ or to $-x_{0}$. Given the measurements $(y_{i})_{i=1}^{N}$, a reasonable approach is to seek a value of $x$ that minimizes the empirical risk function:

for some $p$. Here we will consider values of $p$ in the regime $1<p\leq 2$; the exact choice of $p$ will become clear later on. Note that for every $x\in T$,

Let $1<p\leq 2$ be given, and choose a value of $u\geq 1$. Given the data $(a_{i},y_{i})_{i=1}^{N}$, ${\hat{x}}\in T$ is called a good estimate if it satisfies that

To motivate the choice of ${\hat{x}}$ in Definition 4.6, observe that $Q_{T,N,W}$ captures the “statistical complexity” of the problem – namely, the sum of the “gaussian complexity” of $T$, $Q_{T,N}$, and the influence of the noise, $\||w|^{p}\|_{\psi_{1}}/\sqrt{N}$. The parameter $u$ tunes the probability estimate, for the moment is of secondary importance. The exact choice of $p$ and $u$ will be specified in Theorem 4.8.

Observe that the value on the left hand side of (4.9) is the empirical excess risk $P_{N}{\cal L}_{x}$ where

is the excess loss functional. The definition implies that the empirical excess risk at ${\hat{x}}$ is of the same order of magnitude as the “statistical error” and thus

Unfortunately, it is impossible to estimate the empirical excess risk since one does not have access to the sampled noise $w_{1},...,w_{N}$, and therefore, nor to $\frac{1}{N}\sum_{i=1}^{N}|w_{i}|^{p}$ – which is the reason for the second modification. By Assumption 4.1, $w\in L_{\psi_{2}}$ and consequently $|w|^{p}\in L_{\psi_{1}}$. From Corollary 4.4, if $u\leq N$, then with probability at least $1-2\exp(-c_{1}u^{2})$,

Therefore, if ${\hat{x}}$ satisfies (4.7), then it also satisfies (4.9), meaning that its empirical excess risk is bounded above by the desired quantity. This leads to the following proposition.

There exists an absolute constant $c_{1}$ for which the following holds. Let ${\hat{x}}$ be a point that satisfies (4.7) and let $w\in L_{\psi_{2}}$. If $0\leq u\leq N$, then with probability at least $1-2\exp(-c_{1}u^{2})$, $P_{N}{\cal L}_{{\hat{x}}}\leq uQ_{T,N,W}$.

To see that there is always a point $\hat{x}$ that satisfies (4.7), observe that for $x_{0}$ and $0<u\leq N$, with probability at least $1-2\exp(-cu^{2})$ (see Corollary 4.4),

Moreover, unless $T$ is very small and $W$ is very large, $Q_{T,N}$ is the dominant term in $Q_{T,N,W}$. For example, consider the case in which $w$ is a centered Gaussian with variance $\sigma$ and $T$ is the set of $k$-sparse vectors on the unit sphere. Then, $\||w|^{p}\|_{\psi_{1}}/{\sqrt{N}}\sim\sigma^{p}/\sqrt{N}$, while $Q_{T,N}\sim\sqrt{k\log(en/k)}/\sqrt{N}$ which clearly is larger than $\||w|^{p}\|_{\psi_{1}}/{\sqrt{N}}$, as long as $k$ is large relative to $\sigma$.

We are now ready to state our main result. To this end recall the definition of $\kappa(s,t)$ given by (2.6), and let $\kappa_{T}=\inf_{s,t\in T}\kappa(s,t)$.

For every $\kappa>0$ and every $L\geq 1$ there exists constants $c_{1},c_{2},c_{3}$ and $c_{4}$ that depend only on $L$ and $\kappa$, for which the following holds. Let $a$ be distributed according to an isotropic, $L$-subgaussian measure, and assume that $\kappa_{T}\geq\kappa$. Assume further that $\|w\|_{\psi_{2}}<\infty$. For every integer $N$ set

Let ${\hat{x}}$ be chosen to satisfy (4.7). Then, for $u\geq c_{2}$, with probability at least $1-2\exp(-c_{3}u^{1/3})$,

Note that $\|w\|_{\psi_{2}}<\infty$ implies that $\|w\|_{\psi_{p}}<\infty$ for any $p\leq 2$.

If $k\log(en/k)\geq(\sigma+1)\log N$ (which is the reasonable range, as one expects $N\sim k$ up to logarithmic factors), then $\beta_{N}\sim k\log(en/k)$, and by Theorem 4.8,

To proceed, and as will be noted in Section 5, in the case of linear measurements, with high probability,

To compare the “quadratic” estimate with the linear one, note that if $N\leq(k\log(en/k))^{\gamma}$ for $\gamma\geq c_{1}$ and some constant $c_{1}\geq 1$, then recalling that for every $x$, $x^{1/\log x}\leq e$, it is evident that

where $C$ is an absolute constant. Therefore, with this choice of $N$,

and up to logarithmic factors scales as the estimate in the linear case.

Clearly, it suffices to take $N\gtrsim_{L,\gamma,\varepsilon}k\log(en/k)\log k$ to ensure that $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}\leq\varepsilon$, which is off only by a $\log k$ factor from the optimal estimate in the linear case.

For every $L\geq 1$ and $\kappa>0$ there exist constants $c_{1}$, $c_{2},c_{3}$ that depend only on $L$ and $\kappa$ and for which the following holds. Let $T$ be the set of $k$-sparse vectors on the sphere, set $a$ to be distributed according to an isotropic, $L$-subgaussian measure and assume that $\kappa_{T}\geq\kappa$. If the noise $w$ is $L$-subgaussian, $N\leq(k\log(en/k))^{\gamma}$ for $\gamma\geq c_{1}\geq 1$ and $u>c_{2}$, then with probability at least $1-2\exp(-c_{3}u^{1/3})$,

In particular, if $N\gtrsim_{L,\gamma,\varepsilon,\delta}k\log(en/k)\log k$ then $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}\leq\varepsilon$ with probability at least $1-\delta$.

3 Proof of Theorem 4.8

The proof of the theorem requires several preliminary facts about empirical and Bernoulli processes. We refer the reader to for more details on these processes.

Throughout this section, $(\Omega,\mu)$ is a probability space and $(X_{i})_{i=1}^{N}$ are iid, distributed according to $\mu$. Let $\varepsilon_{1},...,\varepsilon_{N}$ be independent, symmetric, $\{-1,1\}$-valued random variables, that are independent of $X_{1},...,X_{N}$.

The first result we require is the contraction inequality for Bernoulli processes.

The following symmetrization argument allows one to bound an empirical process using the Bernoulli process indexed by the random set $\{(h(X_{i}))_{i=1}^{N}:h\in H\}$.

We will use Theorem 4.10 and Theorem 4.11 with $F(x)=|x|^{q}$ for $q\geq 2$.

The final result we require is the Kahane-Khintchine inequality , on the moments of Bernoulli processes.

For every $L\geq 1$ there exist constants $c_{1},c_{2}$ and $c_{3}$ that depend only on $L$ for which the following holds. If $p$ is chosen as in Theorem 4.8, then for $u\geq c_{1}$, with probability at least $1-2\exp(-c_{2}u^{1/3})$, for every $x\in T$,

Proof. Fix $q\geq 2$. By the symmetrization theorem (Theorem 4.11) and the independence of $a$ and $W$,

and observe that for every realization of $(w_{i})_{i=1}^{N}$, the functions $y\to|y-w_{i}|^{p}-|w_{i}|^{p}$ vanish at and are Lipschitz on $[-b,b]$ with a constant $p(b+|w_{i}|)^{p-1}$. For b\leq\max_{1\leq i\leq N}\sup_{x\in T}|\bigl{<}a_{i},x-x_{0}\bigr{>}\bigl{<}a_{i},x+x_{0}\bigr{>}| this constant is proportional to $D_{\infty,N}^{p-1}$, since $p\leq 2$. Applying the contraction inequality (Theorem 4.10), conditioned on $w_{1},...,w_{N}$ and $a_{1},...,a_{N}$,

By the Kahane-Khintchine inequality, the Cauchy-Schwarz inequality, and Jensen’s inequality combined with reverse symmetrization (the other direction of Theorem 4.11),

where $\|\ \|_{L_{2q}}$ is taken with respect to the $N$-product measure $(a\otimes w)^{N}$.

and it remains to bound $\|D_{\infty,N}^{p-1}\|_{L_{2q}}$ and $B_{T,N,q}$.

Turning to $\|D_{\infty,N}^{p-1}\|_{L_{2q}}$, observe that pointwise

Set $p=1+1/\log\beta_{N}$. With this choice, combined with the moment characterization of the $\psi_{1}$ norm (4.2), it is evident that

for a suitable absolute constant $c_{5}$. Indeed,

With these two estimates, it is evident that there exists a constant $c_{6}$ that depends only on $L$ for which, for every $q\geq 2$,

With this $L_{q}$ estimate at hand, it is standard to show (see, e.g., for a similar argument), that for $u\geq 1$, with probability at least $1-2\exp(-c_{7}u^{1/3})$,

where $c_{7}$ and $c_{8}$ depend only on $L$.

Finally, in this case, for every $x\in T$

With Lemma 4.13 in mind, the choice of ${\hat{x}}$ becomes clearer. One would like to find any point in $T$ for which $P_{N}{\cal L}_{x}$ is, at most, of the same order of magnitude as the combined complexity term of the set $T$ and the noise

Given $x\in T$ set h_{x}=\bigl{<}a,x-x_{0}\bigr{>}\bigl{<}a,x+x_{0}\bigr{>} and recall that ${\cal L}_{x}=|h_{x}(a)-w|^{p}-|w|^{p}$. Since $w$ is a symmetric random variable, it is distributed as $\varepsilon|w|$, where $\varepsilon$ is a symmetric $\{-1,1\}$-valued random variable, independent of $w$ and of $a$. Therefore,

Observe that the function $f(t)=(t^{2}+(p-1)d^{2})^{p/2}-t^{p}$ is increasing for $t\geq 0$ and that $f(0)=(p-1)^{p/2}d^{p}$. Hence, for every $c,d$,

By the definition of $\kappa(s,t)$, for every $s,t$ and $p\geq 1$,

Combining this lower bound with (4.13), and recalling that $p=1+1/\log\beta_{N}$ completes the proof of the theorem.

4 Examples

Let us present some of the examples seen in Section 3.2, in the noisy setting. Other examples may be obtained with similar ease.

In all the examples below we will assume that $T\subset S^{n-1}$ and so $d(T)=1$. Since $w$ is symmetric and $L$-subgaussian, then $\|w\|_{\psi_{1}}\leq\|w\|_{\psi_{2}}\lesssim L\sigma$, where $\sigma$ is the noise variance. Also, since $1<p\leq 2$, $\||w|^{p}\|_{\psi_{1}}=\|w\|_{\psi_{p}}^{p}\lesssim(L\sigma)^{p}$.

for the regime of $N$ we are interested in, and

Suppose that $n\geq(\sigma+1)\log N$. Then, by Theorem 4.8,

where $c$ is an absolute constant. If $N\leq n^{\gamma}$ for $\gamma\geq c_{1}\geq 1$, then

for a suitable absolute constant $C$. Therefore, with this choice of $N$,

and it suffices to take $N\gtrsim_{L,\gamma,\kappa,\varepsilon,\delta}n\log n$ to ensure that $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}\leq\varepsilon$ with probability at least $1-\delta$.

For every $L\geq 1$ and $\kappa>0$ there exist constants $c_{1}$, $c_{2},c_{3}$ that depend only on $L$ and $\kappa$ and for which the following holds. If $\mu$, $a$ and $w$ are as above, $T=S^{n-1}$ and $N\leq n^{\gamma}$ for $\gamma\geq c_{1}\geq 1$, then for $u>c_{2}$ with probability at least $1-2\exp(-c_{3}u^{1/3})$,

4.2 Sparse Vectors

We already treated the case of sparse vectors in Corollary 4.9. The block-sparse setting can be treated in a similar manner, leading to the following corollary.

For every $L\geq 1$ and $\kappa>0$ there exist constants $c_{1}$, $c_{2},c_{3}$ that depend only on $L$ and $\kappa$ and for which the following holds. If $a$ and $w$ are as above, $T$ is the set of $k$-block sparse vectors of length $d$ on the sphere and $N\leq(k\log(en/dk)+dk)^{\gamma}$ for $\gamma\geq c_{1}\geq 1$, then for $u>c_{2}$ with probability at least $1-2\exp(-c_{3}u^{1/3})$,

In particular, if $N\gtrsim_{L,\gamma,\varepsilon,\delta}(k\log(en/kd)+dk)(\log k+\log d)$ then $\|{\hat{x}}-x_{0}\|_{2}\|{\hat{x}}+x_{0}\|_{2}\leq\varepsilon$ with probability at least $1-\delta$.

Connection with Results on Linear Estimation

It should come as no surprise that the methods used here are very similar in nature to the analogous “linear questions”. Both stability and noisy recovery are well understood in the linear case, and in a sharp way, as we will explain below.

Stability in a set $T$ for a random ensemble depends on the way in which a typical operator acts on the set

The study of the process (5.2), both for $T_{-}=S^{n-1}$ and for an arbitrary subset of the sphere has been extensive in recent years. A good starting point for the interested reader would be for subgaussian ensembles, for log-concave ensembles, and for ensembles with heavy tails (though this does not begin to cover the extensive literature on the topic).

In the context of this paper, subgaussian ensembles, the best estimate on (5.2) follows from Theorem 2.8, applied to the class F=H=\{\bigl{<}v,\cdot\bigr{>},\ v\in T_{-}\}. Moreover, in it was shown that under very mild assumptions on the set $T_{-}$, the estimate is sharp.

The best results to-date on linear regression that take into account the complexity of the indexing set $T$ can be found in . One may show that these estimates are sharp under very mild assumptions on $T$, and it turns out that these assumptions are satisfied in the examples that were presented here. Since our bounds in the “quadratic” case are of the same order of magnitude as in the easier, linear case, and since these bounds are optimal in the linear case, it is reasonable to expect that they are optimal in the quadratic scenario as well. Unfortunately, the methods required to prove this optimality are rather involved, and we will not explore this issue here. Rather we refer the reader to , in which the linear case is explored.

References