Sparse recovery via non-convex optimization

Abstract: The sparse recovery problem has received a lot of attention, both because of its role in transform coding with redundant dictionaries, and more importantly because it has inspired "compressed sensing". The main questions are:

Suppose we have a "sparse" vector x in R^n (i.e., x has only a few non-zero entries). Given b=Ax where A is a short matrix (m-by-n with m<n), can we recover x? Under what conditions on A? In a computationally tractable way? If there is noise? If x is not sparse, but can be well-approximated by a sparse vector (i.e., x is "compressible")?

It has been recently shown by Candes-Romberg-Tao and independently by Donoho that one can recover estimates of sparse and compressible signals from an "incomplete" set of noisy measurements via one-norm minimization methods under certain conditions on the "measurement matrix" A. These conditions are satisfied (asymptotically optimally) when the matrix A is a random matrix whose entries are drawn i.i.d. from a Gaussian distribution.

In this talk, we present the theoretical recovery guarantees obtained when decoding by p-quasinorm minimization with 0<p<1 in the setting described above, and we prove that the corresponding guarantees are significantly better than those one can obtain in the case of one-norm minimization. In particular, we show that decoders based on p-quasinorm minimization are (l²,l^p) instance optimal. Moreover, these decoders are (l²,l²) instance optimal in probability (this latter relates to a result on Banach-Mazur distances of p-convex bodies to their convex hulls). Finally, we comment on algorithmic issues.

This is joint work with Rayan Saab.

Refreshments will be served at 2:45 p.m. (Math Lounge, MATX 1115).