Department of Mathematics
Uniform Uncertainty Principle and signal recovery via Regularized Orthogonal Matching
- Author(s): Needell, Deanna
- Vershynin, Roman
- et al.
Published Web Locationhttps://arxiv.org/pdf/0707.4203.pdf
This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements -- L_1-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 L_1-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.