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.
No comments:
Post a Comment