CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
arXiv:0803.2392
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 many cases of interest, the running time is just O(N*log^2(N)), where N is the length of the signal.
30 pages. Revised. Presented at Information Theory and Applications, 31 January 2008, San Diego
References in corpus (1)
Cited by in corpus (10)
- Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
- Guaranteed Rank Minimization via Singular Value Projection
- Projection-Based and Look Ahead Strategies for Atom Selection
- Manifold-Based Signal Recovery and Parameter Estimation from Compressive Measurements
- Compressive Sensing Using Low Density Frames
- Efficient and Guaranteed Rank Minimization by Atomic Decomposition
- Sparsity Pattern Recovery in Bernoulli-Gaussian Signal Model
- Bayesian Hypothesis Testing for Sparse Representation
- Solve-Select-Scale: A Three Step Process For Sparse Signal Estimation
- Compressive Imaging of Subwavelength Structures