Article - postprint
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 Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of L1-minimization. Our algorithm, ROMP, reconstructs a sparse signal in a number of iterations linear in the sparsity, and the reconstruction is exact provided the linear measurements satisfy the uniform uncertainty principle.
© 2008 Springer-Verlag
Needell, D., Vershynin, R., "Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching Pursuit", Foundations of Computational Mathematics, vol. 9, num. 3, pp. 317-334, 2009. doi: 10.1007/s10208-008-9031-3