Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 53, Issue 12, Pages 4655-4666Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2007.909108
Keywords
algorithms; approximation; basis pursuit; compressed sensing; group testing; orthogonal matching pursuit; signal recovery; sparse approximation
Ask authors/readers for more resources
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 1n 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.
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