CoSaMP: Iterative Signal Recovery From Incomplete and Inaccurate Samples

Authors

Deanna Needell, Claremont McKenna CollegeFollow
J. A. Tropp, California Institute of Technology

Document Type

Article - postprint

Department

Mathematics (CMC)

Publication Date

7-16-2008

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 calledCoSaMP 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(Nlog²N), where N is the length of the signal.

Comments

Selected as the ScienceWatch fast-breaking paper in mathematics, Aug. 2010.

2009 Top 3 Hottest ACHA Article
2010 Top 2 Hottest ACHA Article
2011 Top 4 Hottest ACHA Article
2012 Top 3 Hottest ACHA Article
2013 Top 1 Hottest ACHA Article

The publisher's pdf can be found at:

http://www.sciencedirect.com/science/article/pii/S1063520308000638

Rights Information

Copyright © 2009 Elsevier Inc. All rights reserved.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/j.acha.2008.07.002

Recommended Citation

Needell, D., Tropp, J. A., "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples," Applied and Computational Harmonic Analysis, vol. 26, num. 3, pp. 301-321, 2008. doi: 10.1016/j.acha.2008.07.002