CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

By Joel A. Tropp, Deanna Needell. arXiv.org, 2008

4,917 citations recorded by the source corpus.

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.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f37fb5f2ec9624f1c8e2e8ace17b71fc3fc32f56

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Secure and Robust Iris Recognition Using Random Projections and Sparse Representations (2011, methodology): “using greedy pursuit algorithms such as CoSaMP [51].”
Compressive Sensing with structured random matrices (2012, background): “We will concentrate here on the latter and refer the reader to the literature [40, 58, 78, 90, 91, 103, 131, 127] for further information concerning greedy methods.”
Generalized Orthogonal Matching Pursuit (2011, background): “Algorithms in this category include orthogonal matching pursuit (OMP) [11], regulariz ed OMP (ROMP) [2], stagewise OMP (StOMP) [13], subspace pursuit (SP) [18], and compressive s ampling matching pursuit (CoSaMP) [19].”
Spectral compressive sensing (2013, methodology): “Further work includes integrating our frequency inhibition and line spectral estimation approaches into more powerful greedy [46], iterative [71], and `1-norm minimization [72] recovery algorithms, as well as obtaining a full performance characterization for the line spectral estimators used in the ”
Grant-Free Non-Orthogonal Multiple Access for IoT: A Survey (2019, methodology): “The sparse signal recovery algorithms in CS can be used to realize user activity detection by identifying the positions of non-zero elements, for which a compressive sampling matching pursuit (CoSaMP, [162]) algorithm is used due to its low complexity and excellent robustness to noise.”
Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance (2010, methodology): “For example, convex optimisation can be used to find near optimal estimates of x [7] and similar bounds have been derived for estimates found by greedy algorithms such as Compressed Sensing Matching Pursuit (CoSaMP) [8], Subspace Pursuit [9], Iterative Hard Thresholding [10] and the method in [11].”
Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices (2009, neutral): “is operator. Parallel implementation on GPUs or distributed implementation across multiple machines are other interesting avenues for future improvements. Finally, in the spirit of the recent work of [25] on sparse reconstruction and [23] on rank minimization, it may be possible to nd ecient greedy ”
Exploiting sparsity of interconnections in spatio-temporal wind speed forecasting using Wavelet Transform (2016, methodology): “such as Orthogonal Matching Pursuit (OMP) [33] and Compressive Sampling Matching Pursuit (CoSaMP) [34].”
Learning sparse models for a dynamic Bayesian network classifier of protein secondary structure (2011, background): “Methods for encouraging sparsity have been the subject of much recent work in the statistical machine learning community [18-20] because these methods have the potential to learn the trade-off between over-and under-fitting a given data set.”
Compressive sensing: From theory to applications, a survey (2013, methodology): “For such situations, improved versions of OMP have been devised like regularized OMP [33], stagewise OMP [34], compressive sampling matching pursuits (CoSaMP) [35], subspace pursuits [36], gradient pursuits [37], and orthogonal multiple matching pursuit [38].”
ADMiRA: Atomic Decomposition for Minimum Rank Approximation (2009, background): “2:For the vector case, the term analogous to the atomic band is t he component band [19] defined by Bj , {k ∈ {1, .”
Compressed Synthetic Aperture Radar (2010, result): “In Section VIII, we show some of the experimental results, and present the concluding remarks in Section IX.”
Structured Compressed Sensing: From Theory to Applications (2011, methodology): “Other greedy techniques that have a similar ﬂavor to OMP include CoSaMP [56], detailed as Algorithm 2, and subspace pursuit (SP) [57].”
Compressed Sensing (2014, neutral): “Una primer opción, que no será analizada en este trabajo, es utilizar algoritmos de tipo “Greedy”, entre los que destacan: “Orthogonal Matching Pursuit (OMP)” [58], OMP Regularizado (ROMP) [54], “Iterative hard thresholding (IHT)” [10] y “Compressive Sampling Matching Pursuit” (CoSaMP) [53].”