Corrupted Sensing: Novel Guarantees for Separating Structured Signals

I Introduction

In the corrupted sensing problem, our goal is to recover a structured signal from a collection of potentially corrupted measurements. Recent years have seen a flurry of interest in specific instances of this problem, including sparse vector recovery from sparsely corrupted measurements and the recovery of low-rank matrices from sparse corruption . The former arises in applications such as face recognition and in the analysis of sensor network data ; the latter arises in problems ranging from latent variable modeling to video background subtraction . In the present work, we are more broadly interested in the deconvolution of an arbitrary signal-corruption pair. While the problem is generally ill-posed, one might hope that recovery is possible when both signal and corruption are suitably structured.

for some bound $\delta$ on the noise level $\left\lVert{z}\right\rVert_{2}$. In the noiseless setting where $\delta=0$, the authors’ geometric analysis shows that

Our work extends that of Chandrasekaran et al. to a more challenging setting, in which signal measurements may not be trustworthy. Specifically, we allow our measurements

to be corrupted by an unknown but structured vector $v^{\star}$, and bound the sample size $n$ needed to recover $x^{\star}$ and $v^{\star}$ exactly or stably, using convex optimization. As an example, if $z=0$ and $v^{\star}$ is $(n\cdot\gamma)$-sparse, so that a fraction $\gamma$ of our linear measurements are arbitrarily corrupted, then our analysis guarantees exact recovery as soon as $n$ exceeds

plus an explicit smaller-order term. This provides a close parallel with Chandrasekaran et al. ’s result (1) for the corruption-free setting and gives an explicit scaling in terms of the corruption complexity $\gamma$. More generally, our analysis characterizes recovery from a wide variety of corruption structures, including block-sparse, low-rank, and binary corruption, by appealing to a unified geometric treatment of the complexity of the vector $v^{\star}$.

In the formal corrupted sensing problem, we observe a measurement vector $y=\Phi x^{\star}+v^{\star}+z$ comprised of four components:

as in . Throughout, we treat $x^{\star}$ and $v^{\star}$ as fixed vectors chosen independently of $\Phi$. In some settings, we can allow for $x^{\star}$ and $v^{\star}$ to be selected adversarially after the matrix $\Phi$ is generated with a similar theoretical analysis but do not present this work here. In the literature, Chandrasekaran et al. also treat the signal $x^{\star}$ as fixed, while McCoy and Tropp give an additional deconvolution guarantee that holds universally over all low-complexity signals via a union bound argument. However, the unstructured noise $z$ need not be independent of $\Phi$ and in particular may be chosen adversarially after $\Phi$ is generated.

Our goal is tractable estimation of $x^{\star}$ and $v^{\star}$ given knowledge of $y$, $\delta$, and $\Phi$. To this end, we consider two convex programming approaches to disentangling signal and corruption. The first approach penalizes a combination of signal and corruption complexity, subject to known measurement constraints:

We note that McCoy and Tropp study a similar, noiseless setting in which $n=p$ and

Our novel analysis treats both constrained and penalized optimization, provides stable recovery results in the presence of unstructured noise, and covers both the high-dimensional setting ($n<p$) and the overcomplete setting ($n\geq p$).

I-B Roadmap

The remainder of the paper is organized as follows. In Section II, we review several concepts from convex geometry that are used throughout the paper and discuss the notions of Gaussian complexity and Gaussian distance that form the main ingredients in our recovery results. Section III presents our main results for both constrained and penalized convex recovery and gives a brief sketch of our proof strategy. We apply these results to several specific problems in Section IV, including the problem of secure and robust channel coding, and compare our results with those in the literature. Our experiments with simulated data, summarized in Section V, demonstrate a close agreement between our theory and the phase transitions for successful signal recovery observed in practice. We conclude in Section VI with a discussion of our results and several directions for future research. All proofs are deferred to the appendices.

I-C Notation

Throughout, we write $\mu_{n}$ to represent the expected length of an $n$-dimensional vector with independent standard normal entries (equivalently, $\mu_{n}$ is the mean of the $\chi_{n}$ distribution)The same quantity was represented by $\lambda_{n}$ in .. It is known that $\mu_{1}=\sqrt{\nicefrac{{2}}{{\pi}}}$ while $\mu_{n}\approx\sqrt{n}$ for large $n$; in fact, the expectation is tightly bounded by

II Convex Geometry

The subdifferential of $\left\lVert{\cdot}\right\rVert$ at $x$ is the set of vectors

II-B Tangent cones and normal cones

Our analysis of recovery under corrupted sensing will revolve around two notions from convex geometry: the tangent cone and the normal cone. We define the tangent cone We adopt the same terminology for this cone as used by Chandrasekaran et al. ; McCoy and Tropp call it the “feasible cone” since it is the cone of feasible directions under the constraint $\left\lVert{x+w}\right\rVert\leq\left\lVert{x}\right\rVert$. This definition of “tangent cone” nearly coincides with the use of the term in convex geometry—considering the convex subset $\{\left\lVert{z}\right\rVert\leq\left\lVert{x}\right\rVert\}$ (that is, the unit ball of the norm $\left\lVert{\cdot}\right\rVert$, rescaled by $\left\lVert{x}\right\rVert$), the tangent cone as defined in convex geometry is given by $\overline{T}$, the closure of $T$. to $\left\lVert{\cdot}\right\rVert$ at $x$ as the set of descent (or non-ascent) directions of $\left\lVert{\cdot}\right\rVert$ at $x$:

By convexity of the norm $\left\lVert{\cdot}\right\rVert$, $T$ is a convex cone. In our running example, the tangent cone is given by

The normal cone to $\left\lVert{\cdot}\right\rVert$ at $x$ is the polar of the tangent cone, given by

and may equivalently be written as the conic hull of the subdifferential $\partial\left\lVert{x}\right\rVert$ :

II-C Gaussian complexity and Gaussian distance

To quantify the complexity of a structured vector, we adopt two geometric measures of size, the Gaussian complexity and the Gaussian distance:

We call the square root of this quantity, $\omega\left({C}\right)=\sqrt{\omega^{2}\left({C}\right)}$, the Gaussian complexity.

We call the square root of this quantity, $\eta\left({C}\right)=\sqrt{\eta^{2}\left({C}\right)}$, the Gaussian distance.

Indeed, many of the complexity bounds in are derived by bounding $\eta\left({t\cdot\partial\left\lVert{x}\right\rVert}\right)$ at a fixed value of $t$.

In Appendix A-G, we show that the best choice of $t$ typically yields a bound within a small additive constant of the Gaussian complexity:

Suppose that, for $x\neq 0$, $\partial\left\lVert{x}\right\rVert$ satisfies a weak decomposability assumption:

The weak decomposability assumption (7) is satisfied in all the examples considered in this paper and is weaker than the decomposability assumptions often found in the literature (see, e.g., ).

A complementary result relating Gaussian distance and Gaussian complexity appears in Amelunxen et al. [21, Thm. 4.5]:

We will show that the alternative scaling $t^{\prime}=\sqrt{2/\pi}(1-s/p)$ yields the bound

which is a tighter than (8) whenever $s\geq 0.07\cdot p$. Moreover, this new bound, unlike (8), is strictly less than $p$ for any $s<p$; this has important implications for the recovery of structured signals from nearly dense corruption.

Both bounds (8) and (9) are ultimately derived from the expected squared distance definition

The resulting bound on the Gaussian complexity is tighter than either (8) or (9), albeit without an interpretable closed form. We compare the distance bounds arising from these three calculations in Figure 2. Notice that the new closed-form bound (9) closely approximates the optimal squared distance bound (10) for a wide range of sparsity levels, while the prior closed-form bound (8) only dominates (9) in the extreme sparsity regime.

II-D Structured vectors and structure-inducing norms

While our analysis is applicable to any signal coupled with any norm, it is most profitable when the signal exhibits low complexity under its associated norm. In this section, we will highlight a number of important structured signal classes and norms under which these signals have low complexity (additional examples can be found in ):

where $V_{b}\subset\{1,\dots,p\}$ is the $b$th block.

Table I gives bounds on the squared complexity of the tangent cone for each of these structured settings (recall that $\mu_{k}$ is the mean of a $\chi_{k}$ distribution). These estimates will be useful for studying signal recovery via the constrained convex optimization problems (3) and (4). Table II highlights those results obtained by bounding the larger quantity $\eta^{2}\left({t\cdot\partial\left\lVert{x}\right\rVert}\right)$ for a fixed scaling $t$ of the subdifferential. We will make use of these Gaussian squared distance estimates and their associated settings of $t$ when studying penalized convex recovery via (2). The new results in Tables I and II are derived in Appendix A.

III Recovery from Corrupted Gaussian Measurements

We begin by analyzing the constrained convex recovery procedures

corrupted measurements suffice to recover $(x^{\star},v^{\star})$ exactly in the absence of noise $(\delta=0)$ and stably in the presence of noise $(\delta\neq 0)$, via either of the procedures (11) or (12).

If $(\widehat{x},\widehat{v})$ solves either of the constrained optimization problems (11) or (12), then

with probability at least $1-e^{-(\mu_{n}-\tau-\epsilon\sqrt{n})^{2}/2}$, as long as $\mu_{n}-\epsilon\sqrt{n}$ exceeds the success threshold

In the noiseless setting where $\delta=0$, Theorem 1 entails exact recovery of $(x^{\star},v^{\star})$ with probability at least $1-e^{-(\mu_{n}-\tau)^{2}/2}$ as long as $\mu_{n}\geq\tau$. When $n=p$ and $\delta=0$, this conclusion closely resembles the recent results of . See Section IV-D for a more detailed discussion of these related works.

III-B Recovery via penalized optimization

with penalty parameter $\lambda$. Our next result provides sufficient conditions for exact and stable penalized recovery and demonstrates how to set the penalty parameter $\lambda$ in practice.

with probability at least $1-e^{-(\mu_{n}-\tau-\epsilon\sqrt{n})^{2}/2}$, as long as $\mu_{n}-\epsilon\sqrt{n}$ exceeds the success threshold

In the noiseless setting ($\delta=0$), Theorem 2 entails exact recovery of $(x^{\star},v^{\star})$ with probability at least $1-e^{-(\mu_{n}-\tau)^{2}/2}$ as long as $\mu_{n}\geq\tau$.

In analogy to Theorem 1, one might expect that

would suffice for high probability penalized recovery. Indeed, our recovery result would have this form under a more symmetric observation model in which the corruption vector is also multiplied by a random Gaussian matrix (i.e., $y=\Phi x^{\star}+\Psi v^{\star}+z$, where $\Phi$ and $\Psi$ are independent). Our experimental results (see Figure 6) suggest that while (14) is nearly the right threshold for recovery, a visible asymmetry exists between signal and corruption, stemming from the fact that only the signal vector is modulated by a Gaussian matrix under our observation model.

To make use of Theorem 2, it suffices to bound the Gaussian distance terms

III-C Proof overview

In each of the optimization problems above, the recovery target $(x^{\star},v^{\star})$ and estimate $(\widehat{x},\widehat{v})$ both lie in the feasible set $\{(x,v):\left\lVert{y-(\Phi x+v)}\right\rVert_{2}\leq\delta\}$, and hence the error $(\widehat{x}-x^{\star},\widehat{v}-v^{\star})$ satisfies $\left\lVert{\Phi(\widehat{x}-x^{\star})+(\widehat{v}-v^{\star})}\right\rVert_{2}\leq 2\delta$. In Appendix C, we bound the size of this error with high probability by lower bounding

for either of the two constrained recovery procedures, or the weaker requirement

IV Applications and Related Work

In this section, we apply the general theory of Section III to specific signal and corruption structures of interest, drawing comparisons to existing literature where relevant. All results in this section are proved in Appendix B.

To exemplify the constrained recovery setting, we analyze a communications protocol for secure and robust channel coding proposed by Wyner and studied by McCoy and Tropp . The aim is to transmit a binary signal securely across a communications channel while tolerating sparse communication errors. The original protocol applied a random rotation to the binary signal and thereby constrained the length of the transmitted message to equal the length of the input message. Here, we take $n$ random Gaussian measurements $\Phi$ for $n$ not necessarily equal to $p$. This offers the flexibility of transmitting a shorter, cheaper message with reduced tolerance to corruption, or a longer message with increased corruption tolerance. In addition, unlike past work, we allow our measurements to be perturbed by dense, unstructured noise.

To recover the signal $x^{\star}$ after observing the sparsely corrupted and densely perturbed message $y=\Phi x^{\star}+v^{\star}+z$ with $\left\lVert{z}\right\rVert_{2}\leq\delta$, we solve the constrained optimization problem

where we take advantage of the prior knowledge that $\left\lVert{x}\right\rVert_{\infty}=1$ for any binary signal. The following result, which follows from Theorem 1, provides sufficient conditions for exactly reconstructing $x^{\star}$ using the convex program (16).

Suppose that $x^{\star}\in\{+1,-1\}^{p}$ and that $v^{\star}$ is supported on at most $n\cdot\gamma$ entries. Suppose the number of measurements satisfies

Then with probability at least $1-e^{-(\mu_{n}-2\delta-\tau)^{2}/2}$, the binary vector $x^{\star}$ is exactly equal to $\operatorname{sign}(\widehat{x})$, where $(\widehat{x},\widehat{v})$ is any solution to the constrained recovery procedure (16).

IV-B General penalized recovery from block-sparse corruption and unstructured noise

As a first application of our penalized recovery result, Theorem 2, we consider a setting in which the corruption is entry-wise or block-wise sparse, and the signal exhibits an arbitrary structure. While past work has analyzed corruption-free block-sparse signal recovery in the setting of compressed sensing , to our knowledge, Corollary 2 is the first result to analyze structured signal recovery from block-sparse corruption.

Let $m$ denote the number of disjoint measurement blocks and $k=n/m$ represent the common block size. Suppose that no more than $s$ measurement blocks have been corrupted and that the identities of the corrupted blocks are unknown. We consider a “dense” corruption regime where the proportion of corruptions $\gamma=\frac{s}{m}$ may lie anywhere in $(0,1)$. The following corollary bounds the number of measurements needed for exact or stable recovery, using the penalized program

measurements suffice for exact recovery of a structured signal $x^{\star}$.

for $\alpha_{k}=1-\sqrt{1-\mu_{k}^{2}/k}$, then with probability at least $1-\beta$,

In the noiseless setting, where $\delta=0$, Corollary 2 entails exact recovery with probability $1-\beta$ whenever $\sqrt{n}$ is at least as large as

measurements suffice to recover $x^{\star}$ exactly or stably, respectively, with high probability, using the convex program

with $\lambda=(1-\gamma)/\sqrt{\pi\log(p/s)}$. This result is particularly well suited to recovery from dense entrywise corruption and accords with the best sparse recovery from sparse corruption results in the literature. For example, Li [1, Thm. 1.1] establishes stable recovery via (19) using the penalty parameter $\lambda=1/\sqrt{\log(p/n)+1}$, whenever the signal and corruption sparsity levels satisfy

for an unspecified universal constant $C>0$. Our result admits a guarantee of this form, while providing an explicit trade-off between the sparsity levels of the signal and the corruption.

Specifically, Corollary 2 yields a stable recovery result (derived in Appendix B-B) under the conditions

for any corruption proportion bound $\gamma<1$ and

(Recall that $\alpha_{1}=1-\sqrt{1-\nicefrac{{2}}{{\pi}}}\approx 0.4$.) The associated setting of the penalty parameter $\lambda=(1-\gamma)/{\sqrt{\pi\log(\nicefrac{{p}}{{s_{\gamma}}})}}$ is parameterized only by $\gamma$ and, like Li’s result, requires no prior knowledge of the signal sparsity level $\left\lVert{x^{\star}}\right\rVert_{0}$. Our setting has the added advantage of allowing the user to specify an arbitrary upper bound on the corruption level.

IV-C Penalized recovery when signal and corruption are both extremely sparse

and the number of measurements $n$ satisfies

then with probability at least $1-e^{-(\mu_{n}-\tau-\epsilon\sqrt{n})^{2}/2}$,

When the noise level equals zero, we recover a result due to Laska et al. , which establishes high probability exact recovery of a sparse signal from sparsely corrupted measurements via the convex program

measurements suffice for high probability recovery. We omit the details here.

IV-D Additional related work

We conclude this section with a summary of some existing results in the vicinity of this work.

where $A^{(i)}$ is the $i$th column of $A$, and $v^{\star}$ has uniformly random signs. Nguyen and Tran establish stable or exact recovery of $(x^{\star},v^{\star})$ from $y=Ax^{\star}+v^{\star}+z$, where $A$ has columns sampled uniformly from an orthonormal matrix, $x^{\star}$ has uniformly random signs, $v^{\star}$ has uniformly distributed support, and $z$ is a bounded noise vector. Pope et al. analyze the exact recovery of $x^{\star}$ and $v^{\star}$ from $y=Ax^{\star}+Bv^{\star}$, where $A$ and $B$ are known. The authors require uniform randomness in the support set of $x^{\star}$ or $v^{\star}$ and rely on certain incoherence properties of $A$ and $B$. In contrast to these works, we analyze the recovery of deterministic signal and corruption vectors from Gaussian measurements, derive small, explicit constants, and generalize to arbitrary structured signals and structured corruption vectors.

IV-D2 Structured signal recovery from structured corruption

Hegde and Baraniuk analyze a nonconvex procedure for deconvolving a pair of signals lying on incoherent manifolds when the measurement matrix satisfies a restricted isometry property. Here, we focus on convex procedures for which global minima can be found in polynomial time.

V Experimental Evaluation

In this section, we verify and complement the theoretical results of Section III with a series of synthetic corrupted sensing experiments. We present both constrained and penalized recovery experiments for several types of structured signals and corruptions in the presence or absence of noise. Our goals are twofold: first, to test the agreement between our constrained recovery theory and empirial recovery behavior and, second, to evaluate the utility of the penalty parameter settings suggested in Theorem 2 when using penalized recovery. In each experiment, we employ the CVX Matlab package to specify and solve our convex recovery programs.

Sample a binary vector $x^{\star}$ uniformly from $\{\pm 1\}^{p}$.

Solve the constrained optimization problem (16) with $y=\Phi x^{\star}+v^{\star}$ and $\delta=0$.

Declare success if $\left\lVert{\widehat{x}-x^{\star}}\right\rVert_{2}/\left\lVert{x^{\star}}\right\rVert_{2}<10^{-3}$.

Solve the following constrained optimization problem with $y=\Phi x^{\star}+v^{\star}$:

Declare success if $\left\lVert{\widehat{x}-x^{\star}}\right\rVert_{2}/\left\lVert{x^{\star}}\right\rVert_{2}<10^{-3}$.

V-B Phase transitions from penalized recovery

V-C Stable recovery error

Solve the following constrained optimization problem with $y=\Phi x^{\star}+v^{\star}$:

will give rise to quantity bounded by a universal constant, independent of $n$ or $p$. This is precisely what we observe in Figure 7. Here we have plotted, for each setting of $p$ and $n$, the average recovery error and the average rescaled recovery error across 20 iterations. We have used the optimal squared distance bound (10) to estimate the complexities in the scaling factor (21). We see that while the absolute error curves vary with the choice of $p$, the rescaled error curves converge to a common value, as predicted by the results of Theorem 1.

VI Conclusions and Future Work

We have presented a geometric approach to analyzing the recovery of structured signals from corrupted and noisy measurements. We analyzed both penalized and constrained convex programs and, in each case, provided conditions for exact signal recovery from structured corruption and stable signal recovery from structured corruption with added unstructured noise. Our analysis revolved around two geometric measure of signal complexity, the Gaussian complexity and the Gaussian distance, for which we developed new interpretable bounds. The utility of our theory was borne out in our simulations, which demonstrated close agreement between our theoretical recovery bounds and the sharp phase transitions observed in practice. We envision several interesting directions for future work:

In Section V, we observed that the penalized convex program (13) with canonical choice of penalty parameter performed nearly as well empirically as the constrained convex program (12) with side information. This suggests that our penalized recovery theory could be sharpened to more closely match that obtainable in the constrained recovery setting.

It would be of great practical interest to analyze the fully penalized convex program

when no prior bound $\delta$ on the noise level is available.

Finally, an important open question is to what extent the results of this work extend to corrupted sensing problems with non-Gaussian measurements, either stochastic or deterministic, with suitable incoherence conditions.

Appendix A Tangent Cone Complexity Bounds

Our complexity and distance bounds will be based on two fundamental relationships among Gaussian complexity, Gaussian distance, and a third measure of size known as the Gaussian width:

The first relation, established in , upper bounds the Gaussian complexity of a constrained tangent cone in terms of the Gaussian distance and the expected squared distance to the scaled subdifferential

Our bounds on the right-hand side of (22) will provide specific settings of the subdifferential scale $t$ that can then be used in choosing a penalty parameter for penalized optimization (see Theorem 2).

In fact, the second fundamental relation provides such a bound on the expected squared distance, in terms of the Gaussian width of the subdifferential, via the following result (proved in Appendix A-F):

We will see that the subdifferentials of many structured norms admit simple lower bounds that lead to tight upper bounds on the Gaussian squared distance and Gaussian squared complexity via Proposition 3.

A-B Sparse vectors

for $t=\sqrt{2\log(\frac{p}{s})}$. Using Proposition 3, we obtain a second bound

for $t^{\prime}=\sqrt{\nicefrac{{2}}{{\pi}}}(1-\nicefrac{{s}}{{p}})$. This follows from our more general treatment of block-sparse vectors in Proposition 4 below.

A-C Block-sparse vectors

Suppose that the indices $\{1,\dots,p\}$ have been partitioned into disjoint blocks $V_{1},\dots,V_{m}$ and that $x$ is supported only on $s$ of these blocks. Then it is natural to consider a norm that encourages block sparsity, e.g.,

Proposition 4 presents our two new bounds on Gaussian distance and hence on Gaussian complexity in this setting.

For element-wise sparsity ($k=1$), the bound (25) specializes to the bound (23) given above. The advantage of exploiting block-sparse structure is evident when one compares the factor of $\frac{\mu_{k}^{2}}{k}$ in the bound (25) to the term $\frac{2}{\pi}=\mu_{1}^{2}$ found in (23). The former is larger and approaches $1$ as the block size $k=p/m$ grows, and hence fewer measurements will suffice to recover from these block-sparse corruptions.

Throughout, let $\mathcal{B}$ denote the block indices on which $x$ is supported, with $|\mathcal{B}|=s^{\prime}\leq s$, let $\mathcal{T}$ be the space of vectors with support only on those blocks in $\mathcal{B}$, and let $a\in\mathcal{T}$ be the vector satisfying

We begin by establishing the bound (25) based on the Gaussian width of the subdifferential. For each $b$, $\left\lVert{\mathcal{P}_{{V_{b}}}\left({g}\right)}\right\rVert_{2}$ is $\chi_{k}$ distributed. Using the form of the subdifferential stated above,

Now we turn to the bound (24). By (22), it suffices to bound the expected squared distance

where $\xi$ is a $\chi_{k}$ random variable. We will bound each summand in this expression.

where the penultimate inequality follows from the chi-squared tail bound [35, Lem. 1],

and the final inequality follows from a bound on the Gaussian Q-function

A-D Binary vectors

We note that a bound based on Proposition 3 is typically looser in this setting.

A-E Low-rank matrices

Let $U\Sigma V^{\top}$ be the compact singular value decomposition of $x$, and let $\mathcal{T}$ be the space of matrices in the column or row space of $x$. The subdifferential is given by

where $\left\lVert{{w}}\right\rVert_{\operatorname{op}}$ is the operator norm, i.e. the largest singular value, of $w$.

since the trace norm is unitarily invariant. Furthermore, since $U^{\prime}$ and $V^{\prime}$ each have orthonormal columns, the entries of $U^{\prime}{}^{\top}\Gamma V^{\prime}$ are i.i.d. standard Gaussian. We now apply the following lemma (proved in Appendix D):

Finally, we apply Proposition 3 to obtain the desired bound. ∎

A-F Proof of subdifferential distance bound

We begin with a definition and a lemma (proved in Appendix D). The dual norm to $\left\lVert{\cdot}\right\rVert$ is defined as

Now we prove our Gaussian distance bound that is based on the subdifferential. We use the fact that $\left\lVert{w}\right\rVert^{*}=1$ for all $w\in\partial\left\lVert{x}\right\rVert$.

(Since $\partial\left\lVert{x}\right\rVert$ is closed and is in the unit sphere of the norm $\left\lVert{\cdot}\right\rVert^{*}$, it is compact, and so the maximum must be attained at some $w_{0}$.) Then for any $t$,

where the last step comes from Lemma 2. Taking expectations,

A-G Relating Gaussian distance and Gaussian complexity

Suppose that, for $x\neq 0$, $\partial\left\lVert{x}\right\rVert$ satisfies a weak decomposability assumption:

We will use the following lemma (proved in Appendix D):

Suppose that, for $x\neq 0$, $\partial\left\lVert{x}\right\rVert$ satisfies (27). Let $t_{g}$ be defined as in (28). Then $g\mapsto t_{g}$ is a $\frac{1}{\left\lVert{w_{0}}\right\rVert_{2}}$-Lipschitz function of $g$.

Therefore, applying a bound due to Ledoux [37, (2.8)],

Now suppose that $\mathcal{E}$ holds. Find $w\in\partial\left\lVert{x}\right\rVert$ such that $t_{g}\cdot w$ is the projection of $g$ to $N$, that is,

Since the subdifferential $\partial\left\lVert{x}\right\rVert$ is convex, we have

where the last step comes from the definition of the event $\mathcal{E}$. Therefore,

is a $1$-Lipschitz function of $g$. We will now make use of the following lemma (proved in Appendix D):

Appendix B Proofs of Application Results

First we prove our result on constrained recovery of a binary signal corrupted with sparse noise.

This implies that $x^{\star}$ is the nearest binary vector to $\widehat{x}$, that is, we can exactly recover $x^{\star}$ by setting $x^{\star}=\operatorname{sign}(\widehat{x})$. Letting $\epsilon$ approach $2\delta$, we see that this is true with probability at least $1-e^{-(\mu_{n}-2\delta\sqrt{n}-\tau)^{2}/2}$. ∎

Next we prove our result on penalized recovery of a structured signal observed with a high frequency of block-wise corruptions.

Theorem 2 implies stable recovery with error at most $2\delta/\epsilon$ and probability at least $1-\beta$ once

Since $\mu_{n}>\sqrt{n-1/2}\geq\sqrt{n}-(1-1/\sqrt{2})$ for all $n\geq 1$, it is sufficient to have

is sufficient for recovery. To obtain the final form of our statement, we note that

Finally we prove our result on penalized recovery of an extremely sparse signal observed under extremely sparse corruptions.

To establish the result with $\lambda=1$, we choose

To compute the relevant expected squared distances, we use the fact that, by (10),

The result then follows by applying Theorem 2. ∎

B-B Scaling for sparse signal and dense corruption

Fix any corruption proportion $\gamma<1$ and let $s_{\gamma}$ be defined as in (20). If $x^{\star}$ and $v^{\star}$ have at most $s_{\gamma}$ and $n\cdot\gamma$ nonzero entries, respectively, and $(\widehat{x},\widehat{v})$ is a solution to

then with probability at least $0.9$, the recovery error satisfies

If $s_{\gamma}=0$, then $\lambda=0$, $\widehat{x}=x^{\star}=0$, and $\left\lVert{y-(\Phi\widehat{x}+\widehat{v})}\right\rVert_{2}=\left\lVert{v^{\star}+z-\widehat{v}}\right\rVert_{2}\leq\delta$. Hence, with probability 1, $\sqrt{\left\lVert{\widehat{x}-x^{\star}}\right\rVert^{2}_{2}+\left\lVert{\widehat{v}-v^{\star}}\right\rVert^{2}_{2}}\leq 2\delta\leq 2\delta/\epsilon$.

suffices to achieve the desired recovery guarantee. Since $s_{\gamma}\geq 1$, we have

is sufficient for recovery. One can check that the chosen $s_{\gamma}$ always satisfies this bound. ∎

Appendix C Proofs of Main Results

We will refer to the signal and corruption tangent cones

Given a penalty parameter $\lambda\in(0,\infty)$, we write a joint penalty function

and define the joint tangent cone given by

Consider either version of the constrained estimation problem:

In both optimization problems, our solution $(\widehat{x},\widehat{v})$ will necessarily satisfy

Below, we will derive a high probability lower bound on

Consider the penalized optimization problem

Our solution $(\widehat{x},\widehat{v})$ will satisfy the weaker condition

Following the same reasoning as in the constrained case, we obtain the estimation error bound

C-B Preliminaries

In both the constrained and the penalized setting, we begin by relating $\min_{(a,b)\in\Omega}\left\lVert{\Phi a+b}\right\rVert_{2}$ to a second Gaussian functional via the following lemma (proved in Appendix D):

Next, consider the matrix $\sqrt{n}\cdot\Phi$, which has i.i.d. standard Gaussian entries. We know that $\sqrt{n}\cdot\min_{(a,b)\in\Omega}\left\lVert{\Phi a+b}\right\rVert_{2}$ is a $1$-Lipschitz function of the matrix $\sqrt{n}\cdot\Phi$, because of the assumption that $\left\lVert{a}\right\rVert_{2}\leq 1$ for all $a\in\Omega$. Therefore, applying a bound of Ledoux [37, (2.8)], we see that with probability at least $1-\beta$,

C-C Lower bound: constrained setting

In this section we derive a lower bound on

be shorthand for the two relevant Gaussian squared complexities.

We will combine Lemma 5 with a lower bound for

If $\sqrt{\widehat{\omega}^{2}+\widehat{\omega}^{\prime}{}^{2}}>\left\lVert{h}\right\rVert_{2}$, then

where for the last step, we use the fact that $\sqrt{\widehat{\omega}^{2}+\widehat{\omega}^{\prime}{}^{2}}\leq\left\lVert{h}\right\rVert_{2}$, and apply the following lemma (proved in Appendix D):

For any $a,b,C\geq 0$ such that $a^{2}+b^{2}\leq C^{2}$,

In either case, then, we have proved that

Finally, we take expectations. To bound the first subtracted term, we have

by definition of the Gaussian squared complexity. To bound the second subtracted term, we use the following lemma (proved in Appendix D):

Finally, applying Lemma 5, this gives us the desired lower bound. ∎

C-D Lower bound: penalized setting

In this section we derive a lower bound on

We will combine Lemma 5 with a lower bound for

We know that for each choice of signs $\sigma_{1},\sigma_{2}\in\{\pm 1\}$,

Maximizing the right-hand side over the signs,

Appendix D Proofs for lemmas

Let $\sigma_{1}\geq\dots\geq\sigma_{k}\geq 0$ be the singular values of $h$. Davidson and Szarek [38, Thm. II.13] establishes that

In the general case where $\frac{4}{9}m_{2}$ might not be an integer, we also use the fact that

Since this is true for any $x$, this proves the desired bound. ∎

Suppose that, for $x\neq 0$, $\partial\left\lVert{x}\right\rVert$ satisfies (27). Let $t_{g}$ be defined as in (28). Then $g\mapsto t_{g}$ is a $\frac{1}{\left\lVert{w_{0}}\right\rVert_{2}}$-Lipschitz function of $g$.

Consider any $g$ and $g^{\prime}$. Find $w,w^{\prime}\in\partial\left\lVert{x}\right\rVert$ such that

we see that $t_{g}\cdot w$ and $t_{g^{\prime}}\cdot w^{\prime}$ are the projections of $g$ and of $g^{\prime}$, respectively, onto the cone $N$. Since $N$ is convex and projection onto a convex set is nonexpansive, it follows that

because $\langle{w-w_{0}},{w_{0}}\rangle=\langle{w^{\prime}-w_{0}},{w_{0}}\rangle=0$. ∎

Choose any $\epsilon$ satisfying $0<\epsilon<p_{0}$. By Ledoux [37, (2.8)], we know that

where $\nu\sim N(0,1)$ is independent from the other random variables. Then $\{X_{(a,b),w}\}$ and $\{Y_{(a,b),w}\}$ are both centered Gaussian processes, with

with equality if $(a,b)=(a^{\prime},b^{\prime})$. Therefore, applying Theorem 1.1 of Gordon to these Gaussian processes, we know that for any scalars $\{c_{(a,b),w}\}$,

and same for the $Y$ process. This proves that

or in other words, by maximizing over $w$ on each side,

Finally, since $\left\lVert{a}\right\rVert_{2}\in$ for all $(a,b)\in\Omega$, we see that

For any $a,b,C\geq 0$ such that $a^{2}+b^{2}\leq C^{2}$,

By rescaling, we can assume without loss of generality that $C=1$ and $a^{2}+b^{2}\leq 1$. First, suppose $a^{2}+b^{2}=1$. Then

This proves the claim whenever $a^{2}+b^{2}=1$. Now suppose that $a^{2}+b^{2}=c^{2}$ for some $c\in$, and let $a^{\prime}=\frac{a}{c}$ and $b^{\prime}=\frac{b}{c}$. Then

where the last step is true for all $c,d\in$ as follows:

where the last inequality holds for all $n\geq 1$.

Acknowledgments

The authors thank Emmanuel Candès for helpful suggestions on the presentation of this work. R.F. was supported by NSF grant DMS-1203762.

References