CaltechAUTHORS
  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. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20111010-134929077

[img]
Preview
PDF
See Usage Policy.

321Kb

Use this Persistent URL to link to this item: http://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:
URLURL TypeDescription
http://resolver.caltech.edu/CaltechAUTHORS:TROieeetit07OtherUNSPECIFIED
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:
Funding AgencyGrant Number
NSFDMS 0503299
NSFDMS 0354600
Subject Keywords:Algorithms, approximation, Basis Pursuit, Compressed Sensing, group testing, Orthogonal Matching Pursuit, signal recovery, sparse approximation
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Applied & Computational Mathematics Technical Report2007-01
Classification Code:2000 Mathematics Subject Classication. 41A46, 68Q25, 68W20, 90C27.
Record Number:CaltechAUTHORS:20111010-134929077
Persistent URL:http://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:26 Dec 2012 14:15

Repository Staff Only: item control page