Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 58, Issue 2, Pages 1094-1121Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2011.2173241
Keywords
Compressed sensing; decoding error-correcting codes; false alarm rate; false discovery rate; iterative thresholding; l(1) minimization; mutual access interference; phase transition; sparse overcomplete representation; stepwise regression
Funding
- NIH
- ONR-MURI
- DARPA BAA
- NSF [DMS 00-77261, DMS 01-40698, DMS 05-05303]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [0906812] Funding Source: National Science Foundation
Ask authors/readers for more resources
Finding the sparsest solution to underdetermined systems of linear equations y = Phi x is NP-hard in general. We show here that for systems with typical/random Phi, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra. Our proposal, Stagewise Orthogonal Matching Pursuit (StOMP), successively transforms the signal into a negligible residual. Starting with initial residual, r(0) = y, at the s-th stage it forms the matched filter Phi(T)r(s-1), identifies all coordinates with amplitudes exceeding a specially chosen threshold, solves a least-squares problem using the selected coordinates, and subtracts the least-squares fit, producing a new residual. After a fixed number of stages (e.g., 10), it stops. In contrast to Orthogonal Matching Pursuit (OMP), many coefficients can enter the model at each stage in StOMP while only one enters per stage in OMP; and StOMP takes a fixed number of stages (e.g., 10), while OMP can take many (e.g., n). We give both theoretical and empirical support for the large-system effectiveness of StOMP. We give numerical examples showing that StOMP rapidly and reliably finds sparse solutions in compressed sensing, decoding of error-correcting codes, and overcomplete representation.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available