Share Email Print

Proceedings Paper

Greedy signal recovery and uncertainty principles
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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 &sqrt;log n parallel e parallel 2 where e is the error vector.

Paper Details

Date Published: 20 March 2008
PDF: 12 pages
Proc. SPIE 6814, Computational Imaging VI, 68140J (20 March 2008); doi: 10.1117/12.776996
Show Author Affiliations
Deanna Needell, Univ. of California, Davis (United States)
Roman Vershynin, Univ. of California, Davis (United States)

Published in SPIE Proceedings Vol. 6814:
Computational Imaging VI
Charles A. Bouman; Eric L. Miller; Ilya Pollak, Editor(s)

© SPIE. Terms of Use
Back to Top