CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples

Needell, D. and Tropp, J. A. (2008) CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20111011-160707642

Preview

PDF
See Usage Policy.
452Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111011-160707642

Abstract

Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix-vector multiplies with the sampling matrix. For compressible signals, the running time is just O(N log^2 N), where N is the length of the signal.

Item Type:

Report or Paper (Technical Report)

Additional Information:

Date: 16 March 2008. Revised 16 April 2008. Initially presented at Information Theory and Applications, 31 January 2008, San Diego. We would like to thank Martin Strauss for many inspiring discussions. He is ultimately responsible for many of the ideas in the algorithm and analysis. We would also like to thank Roman Vershynin for suggestions that drastically simplifi�ed the proofs.

Group:

Applied & Computational Mathematics

Subject Keywords:

Algorithms, approximation, basis pursuit, compressed sensing, orthogonal matching pursuit, restricted isometry property, signal recovery, sparse approximation, uncertainty principle.

Other Numbering System:

Other Numbering System Name	Other Numbering System ID
Applied & Computational Mathematics Technical Report	2008-01

Classification Code:

2000 Mathematics Subject Classication. 41A46, 68Q25, 68W20, 90C27.

Record Number:

CaltechAUTHORS:20111011-160707642

Persistent URL:

http://resolver.caltech.edu/CaltechAUTHORS:20111011-160707642

Usage Policy:

No commercial reproduction, distribution, display or performance rights in this work are provided.

ID Code:

27169

Collection:

CaltechACMTR

Deposited By:

Kristin Buxton

Deposited On:

19 Oct 2011 18:06

Last Modified:

26 Dec 2012 14:15

Repository Staff Only: item control page