Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1183.68739
Needell, Deanna; Vershynin, Roman
Uniform uncertainty principle and signal recovery via Regularized orthogonal matching pursuit.
(English)
[J] Found. Comput. Math. 9, No. 3, 317-334 (2009). ISSN 1615-3375; ISSN 1615-3383/e

Summary: This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements---$\text L_{1}$-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 $\text L_{1}$-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.
MSC 2000:
*68W20 Randomized algorithms
65T50 Discrete and fast Fourier transforms
41A46 Approximation by arbitrary nonlinear expressions

Keywords: sparse signal recovery

Highlights
Master Server