Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Top Cited Papers
- 17 December 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 53 (12) , 4655-4666
- https://doi.org/10.1109/tit.2007.909108
Abstract
This paper demonstrates theoretically and empirically that a greedy algorithm called orthogonal matching pursuit (OMP) can reliably recover a signal with m nonzero entries in dimension d given O(m ln d) random linear measurements of that signal. This is a massive improvement over previous results, which require O(m2) measurements. The new results for OMP are comparable with recent results for another approach called basis pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.Keywords
This publication has 27 references indexed in Scilit:
- Random Sampling of Sparse Trigonometric Polynomials, II. Orthogonal Matching Pursuit versus Basis PursuitFoundations of Computational Mathematics, 2007
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solutionCommunications on Pure and Applied Mathematics, 2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Least angle regressionThe Annals of Statistics, 2004
- An affine scaling methodology for best basis selectionIEEE Transactions on Signal Processing, 1999
- Nonlinear approximationActa Numerica, 1998
- On the Probability That a Random ± 1-Matrix Is SingularJournal of the American Mathematical Society, 1995
- Matching pursuits with time-frequency dictionariesIEEE Transactions on Signal Processing, 1993