Tropp, Joel A. and Gilbert, Anna C. (2007) Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 53 (12). pp. 4655-4666. ISSN 0018-9448. doi:10.1109/TIT.2007.909108. https://resolver.caltech.edu/CaltechAUTHORS:TROieeetit07
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 958kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:TROieeetit07
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 $ {rm O}(m ln d)$ random linear measurements of that signal. This is a massive improvement over previous results, which require ${rm 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.
| Item Type: | Article | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| ORCID: |
| ||||||
| Additional Information: | © Copyright 2007 IEEE. Reprinted with permission. Manuscript received April 20, 2005; revised August 15, 2007. [osted online: 2007-12-17] The work of J.A. Tropp was supported by the National Science Foundation under Grant DMS 0503299. The work of A.C. Gilbert was supported by the National Science Foundation under Grant DMS 0354600. The authors wish to thank Martin Strauss for his insight on algorithms, Justin Romberg for sharing his expertise on Basis Pursuit, and Michael Wakin for his perspective on the empirical results. They also appreciate the careful comments of the anonymous reviewers. | ||||||
| Subject Keywords: | Algorithms, approximation, basis pursuit, compressed sensing, group testing, orthogonal matching pursuit, signal recovery, sparse approximation | ||||||
| Issue or Number: | 12 | ||||||
| DOI: | 10.1109/TIT.2007.909108 | ||||||
| Record Number: | CaltechAUTHORS:TROieeetit07 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:TROieeetit07 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 9490 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Archive Administrator | ||||||
| Deposited On: | 26 Jan 2008 | ||||||
| Last Modified: | 08 Nov 2021 20:59 |
Repository Staff Only: item control page
