Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2009 | public
Journal Article Open

CoSaMP: Iterative signal recovery from incomplete and inaccurate samples


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

Additional Information

© 2008 Elsevier. Received 18 March 2008; revised 16 July 2008; accepted 17 July 2008. Available online 22 July 2008. Communicated by Charles K. Chui. 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 simplified the proofs.

Attached Files

Submitted - 0803.2392.pdf


Files (327.0 kB)
Name Size Download all
327.0 kB Preview Download

Additional details

August 21, 2023
August 21, 2023