Tropp, Joel A. and Gilbert, Anna C.
Signal Recovery from Random Measurements Via Orthogonal Matching Pursuit: The Gaussian Case.
California Institute of Technology
, Pasadena, CA.
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
|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|
|Funding Agency||Grant Number|
|Subject Keywords:||Algorithms, approximation, Basis Pursuit, Compressed Sensing, group testing, Orthogonal
Matching Pursuit, signal recovery, sparse approximation|
|Other Numbering System:|
|Other Numbering System Name||Other Numbering System ID|
|Applied & Computational Mathematics Technical Report||2007-01|
|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 On:||19 Oct 2011 18:01|
|Last Modified:||06 Mar 2015 23:11|
Repository Staff Only: item control page