Published October 19, 2011
| Submitted
Report
Open
CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples
- Creators
-
Needell, D.
-
Tropp, J. A.
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.
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 simplified the proofs.Attached Files
Submitted - Caltech_ACM_TR_2008_01.pdf
Files
Caltech_ACM_TR_2008_01.pdf
Files
(463.4 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:56b127c4a7b33112c45941d529176151
|
463.4 kB | Preview Download |
Additional details
- Eprint ID
- 27169
- Resolver ID
- CaltechAUTHORS:20111011-160707642
- Created
-
2011-10-19Created from EPrint's datestamp field
- Updated
-
2020-02-14Created from EPrint's last_modified field
- Caltech groups
- Applied & Computational Mathematics
- Series Name
- ACM Technical Reports
- Series Volume or Issue Number
- 2008-01