Tropp, Joel A. and Gilbert, Anna C. (2007) Signal Recovery from Random Measurements Via Orthogonal Matching Pursuit: The Gaussian Case. ACM Technical Reports, 2007-01. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20111010-134929077
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 329kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111010-134929077
Abstract
This report 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(mln 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.
| Item Type: | Report or Paper (Technical Report) | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| ORCID: |
| ||||||
| Additional Information: | Date: 11 April 2005. Revised 8 November 2006 and 15 August 2007. JAT has been supported by NSF DMS 0503299 and ACG has been supported by NSF DMS 0354600. | ||||||
| Group: | Applied & Computational Mathematics | ||||||
| Funders: |
| ||||||
| Subject Keywords: | Algorithms, approximation, Basis Pursuit, Compressed Sensing, group testing, Orthogonal Matching Pursuit, signal recovery, sparse approximation | ||||||
| Series Name: | ACM Technical Reports | ||||||
| Issue or Number: | 2007-01 | ||||||
| Classification Code: | 2000 Mathematics Subject Classication. 41A46, 68Q25, 68W20, 90C27. | ||||||
| DOI: | 10.7907/EG9R-Y984 | ||||||
| Record Number: | CaltechAUTHORS:20111010-134929077 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111010-134929077 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 27144 | ||||||
| Collection: | CaltechACMTR | ||||||
| Deposited By: | Kristin Buxton | ||||||
| Deposited On: | 19 Oct 2011 18:01 | ||||||
| Last Modified: | 03 Oct 2019 03:21 |
Repository Staff Only: item control page
