Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]