Document Type
Article - postprint
Department
Mathematics (CMC)
Publication Date
6-5-2008
Abstract
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.
Rights Information
© 2008 Springer-Verlag
Terms of Use & License Information
DOI
10.1007/s10208-008-9031-3
Recommended Citation
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
Included in
Computer Sciences Commons, Mathematics Commons, Numerical Analysis and Computation Commons
