A Caltech Library Service

Signal Recovery from Random Measurements Via Orthogonal Matching Pursuit: The Gaussian Case

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)

See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
Tropp, Joel A.0000-0003-1024-1791
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 AgencyGrant Number
NSFDMS 0503299
NSFDMS 0354600
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.
Record Number:CaltechAUTHORS:20111010-134929077
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27144
Deposited On:19 Oct 2011 18:01
Last Modified:03 Oct 2019 03:21

Repository Staff Only: item control page