Compressed Sensing: It's not just L1 anymore, greed can get you there too.

With all the talk about L1 minimization being the only way to reconstruct signals in Compressed Sensing, here is an important landmark: Deanna Needell and Roman Vershynin, just submitted this paper on Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit. The commentary on the paper is here.

The abstract is pretty self explanatory:

This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements – L1- minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of the Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of the L1-minimization. Our algorithm ROMP reconstructs a sparse signal in a number of iterations linear in the sparsity (in practice even logarithmic), and the reconstruction is exact provided the linear measurements satisfy the Uniform Uncertainty Principle.

A basic code for ROMP can be found on Deenna Needell's page.

The difference between greedy algorithms like ROMP and L1 minimization (which require more cumbersome optimization/ linear programming approach) is touched on in this Q&A at IMA in 2005 by Emmanuel Candes and it all comes down to reducing the sampling needed to obtain good reconstruction.