Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

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, w...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2007-12, Vol.53 (12), p.4655-4666
Main Authors: Tropp, J.A., Gilbert, A.C.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
approximation
Back propagation
basis pursuit
Blood
Compressed sensing
Detection, estimation, filtering, equalization, prediction
Dimensional measurements
Electrical engineering
Electronics
Empirical analysis
Exact sciences and technology
Greedy algorithms
group testing
Information theory
Information, signal and communications theory
Matching
Matching pursuit algorithms
Mathematics
Measurement
Miscellaneous
orthogonal matching pursuit
Performance evaluation
Recovery
Reliability theory
Signal and communications theory
Signal processing
signal recovery
Signal, noise
sparse approximation
Telecommunications and information theory
Testing
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (m 2 ) 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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2007.909108