Document Type
Conference Proceeding
Department
Mathematics (CMC)
Publication Date
7-23-2007
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 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, and the reconstruction is exact provided the linear measurements satisfy the Uniform Uncertainty Principle. In the case of inaccurate measurements and approximately sparse signals, the noise level of the recovery is proportional to √ log nkek2 where e is the error vector.
Rights Information
© 2008 SPIE
Terms of Use & License Information
Recommended Citation
Needell, D., Vershynin, R., "Greedy signal recovery and uncertainty principles", Computational Imaging VI, IS&T/SPIE 19th Annual Symposium, 2008. Proc. SPIE Vol. 6814, 68140J.
