Preprints in sparse recovery / compressed sensing

Papers, and projects close to completion





Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information

Emmanuel Candes

Justin Romberg

IEEE Inf. Theory 52 (2006) Vol 2., 489—509


Near Optimal Signal Recovery From Random Projections:  Universal Encoding Strategies?

Emmanuel Candes

IEEE Inf. Theory 52 (2006), 5406-5425


Decoding by Linear Programming

Emmanuel Candes

IEEE Inf. Theory 51 (2005), 4203-4215


Stable Signal Recovery from Incomplete and Inaccurate Measurements

Emmanuel Candes

Justin Romberg

Comm. Pure Appl. Math. 59 (2006), 1207-1223


Error Correction via Linear Programming

Emmanuel Candes

Mark Rudelson

Roman Vershynin

Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS05), IEEE, 2005.  pp. 295-308


The Dantzig selector: statistical estimation when $p$ is much larger than $n$

Emmanuel Candes

Annals of Statistics 35 (2007), 2313-2351



Reflections on compressed sensing

Emmanuel Candes

IEEE Information Theory Society Newsletter, Dec 2008 58 (4), 20-23


The power of matrix completion: near-optimal convex relaxation

Emmanuel Candes

To appear, IEEE Inf. Theory



See also the web pages of Emmanuel Candes and Justin Romberg for slides and other material related to these papers.

In order to clarify what is proved where, I have decided to make a little table of results.  All of the above results concern a measurement matrix A, of which we isolate five particular classes of interest:

These matrices can enjoy the following properties:

One has the following results as to which matrices obey which properties, in rough chronological order:

Results similar to the ERP and CRP in the Fourier ensemble (but with semi-random measurements rather than random, and with a much faster algorithm) have also been obtained by Gilbert, Muthukrishnan, Strauss, et al.

Short stories

These are generally very short, toy versions of real results due to other people, and are not publication-quality.  Caveat emptor.  All files other than figures are in dvi format.  Unlike the preprints, these articles are fluid and subject to new developments.  Please let me know if you have any comments, references, etc. on any of them.

Disclaimer: Many of the notes here are based on papers written by other people.  My intention here is not to try to "beat" these authors' work in any way, but rather to isolate the main ingredients of the argument, which are often very beautiful, and try to present them in as simple and brief a context as possible (often sacrificing generality, rigour, and/or details in order to do this).  Certainly I do not view these notes as worthy of publication in a refereed journal, and are definitely inferior to the original article in every single aspect, with the possible exception of brevity.

Compressed sensing and single-pixel cameras

Ostrowski lecture: the uniform uncertainty principle and compressed sensing

The uniform uncertainty principle and compressed sensing


Open questions