Tropp, Joel A. and Gilbert, Anna C. (2007) Signal Recovery from Random Measurements Via Orthogonal Matching Pursuit: The Gaussian Case. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20111010-134929077
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111010-134929077
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)|
|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|
|Subject Keywords:||Algorithms, approximation, Basis Pursuit, Compressed Sensing, group testing, Orthogonal Matching Pursuit, signal recovery, sparse approximation|
|Other Numbering System:|
|Classification Code:||2000 Mathematics Subject Classication. 41A46, 68Q25, 68W20, 90C27.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Kristin Buxton|
|Deposited On:||19 Oct 2011 18:01|
|Last Modified:||26 Dec 2012 14:15|
Repository Staff Only: item control page