Search

Let $A$ be an isotropic, sub-gaussian $m \times n$ matrix. We prove that theprocess $Z_x := \|Ax\|_2 - \sqrt m \|x\|_2$ has sub-gaussian increments. Usingthis, we show that for any bounded set $T \subseteq \mathbb{R}^n$, thedeviation of $\|Ax\|_2$ around its mean is uniformly bounded by the Gaussiancomplexity of $T$. We also prove a local version of this theorem, which allowsfor unbounded sets. These theorems have various applications, some of which arereviewed in this paper. In particular, we give a new result regarding modelselection in the constrained linear model.

We study the problem of signal estimation from non-linear observations whenthe signal belongs to a low-dimensional set buried in a high-dimensional space.A rough heuristic often used in practice postulates that non-linearobservations may be treated as noisy linear observations, and thus the signalmay be estimated using the generalized Lasso. This is appealing because of theabundance of efficient, specialized solvers for this program. Just as noise maybe diminished by projecting onto the lower dimensional space, the error frommodeling non-linear observations with linear observations will be greatlyreduced when using the signal structure in the reconstruction. We allow generalsignal structure, only assuming that the signal belongs to some set K in R^n.We consider the single-index model of non-linearity. Our theory allows thenon-linearity to be discontinuous, not one-to-one and even unknown. We assume arandom Gaussian model for the measurement matrix, but allow the rows to have anunknown covariance matrix. As special cases of our results, we recovernear-optimal theory for noisy linear observations, and also give the firsttheoretical accuracy guarantee for 1-bit compressed sensing with unknowncovariance matrix of the measurement vectors.

Many applications have benefited remarkably from low-dimensional models inthe recent decade. The fact that many signals, though high dimensional, areintrinsically low dimensional has given the possibility to recover them stablyfrom a relatively small number of their measurements. For example, incompressed sensing with the standard (synthesis) sparsity prior and in matrixcompletion, the number of measurements needed is proportional (up to alogarithmic factor) to the signal's manifold dimension. Recently, a new natural low-dimensional signal model has been proposed: thecosparse analysis prior. In the noiseless case, it is possible to recoversignals from this model, using a combinatorial search, from a number ofmeasurements proportional to the signal's manifold dimension. However, if weask for stability to noise or an efficient (polynomial complexity) solver, allthe existing results demand a number of measurements which is far removed fromthe manifold dimension, sometimes far greater. Thus, it is natural to askwhether this gap is a deficiency of the theory and the solvers, or if thereexists a real barrier in recovering the cosparse signals by relying only ontheir manifold dimension. Is there an algorithm which, in the presence ofnoise, can accurately recover a cosparse signal from a number of measurementsproportional to the manifold dimension? In this work, we prove that there is nosuch algorithm. Further, we show through numerical simulations that even in thenoiseless case convex relaxations fail when the number of measurements iscomparable to the manifold dimension. This gives a practical counter-example tothe growing literature on compressed acquisition of signals based on manifolddimension.

In one-bit compressed sensing, previous results state that sparse signals maybe robustly recovered when the measurements are taken using Gaussian randomvectors. In contrast to standard compressed sensing, these results are notextendable to natural non-Gaussian distributions without further assumptions,as can be demonstrated by simple counter-examples. We show that approximatelysparse signals that are not extremely sparse can be accurately reconstructedfrom single-bit measurements sampled according to a sub-gaussian distribution,and the reconstruction comes as the solution to a convex program.

We give the first computationally tractable and almost optimal solution tothe problem of one-bit compressed sensing, showing how to accurately recover ans-sparse vector x in R^n from the signs of O(s log^2(n/s)) random linearmeasurements of x. The recovery is achieved by a simple linear program. Thisresult extends to approximately sparse vectors x. Our result is universal inthe sense that with high probability, one measurement scheme will successfullyrecover all sparse vectors simultaneously. The argument is based on solving anequivalent geometric problem on random hyperplane tessellations.