More Web Proxy on the site http://driver.im/

research-article

Free access

CoSaMP: iterative signal recovery from incomplete and inaccurate samples

Authors:

Deanna Needell,

Joel A. TroppAuthors Info & Claims

Communications of the ACM, Volume 53, Issue 12

Pages 93 - 100

https://doi.org/10.1145/1859204.1859229

Published: 01 December 2010 Publication History

All formats PDF

Abstract

Compressive sampling (CoSa) is a new paradigm for developing data sampling technologies. It is based on the principle that many types of vector-space data are compressible, which is a term of art in mathematical signal processing. The key ideas are that randomized dimension reduction preserves the information in a compressible signal and that it is possible to develop hardware devices that implement this dimension reduction efficiently. The main computational challenge in CoSa is to reconstruct a compressible signal from the reduced representation acquired by the sampling device. This extended abstract describes a recent algorithm, called, <code>CoSaMP</code>, that accomplishes the data recovery task. It was the first known method to offer near-optimal guarantees on resource usage.

References

[1]

Candès E, Romberg J., Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete Fourier information. IEEE Trans. Info. Theory 52, 2 (Feb. 2006), 489--509.

Digital Library

[2]

Candès, E. J. The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris, Serie I 346 (2008), U589--U592.

[3]

Candès, E. J., Romberg, J., Tao, T. Stable signal recovery from incomplete and inaccurate measurements. Commun. Pur. Appl. Math. 59, 8 (2006), 1207--1223.

[4]

Candès, E. J., Tao, T. Decoding by linear programming. IEEE Trans. Info. Theory 51 (2005), 4203--4215.

Digital Library

[5]

Candès, E. J., Tao, T. Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Info. Theory 52, 12 (Dec. 2006), 5406--5425.

Digital Library

[6]

Cohen, A., Dahmen, W., DeVore, R. Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22, 1 (2009) 211--231.

[7]

Cormen, T., Lesierson, C., Rivest, L., Stein, C. Introduction to Algorithms, 2nd edition, MIT Press, Cambridge, MA, 2001.

Digital Library

[8]

Cormode, G., Muthukrishnan, S. Combinatorial algorithms for compressed sensing. Technical report, DIMACS, 2005.

[9]

Dai, W., Milenkovic, O. Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Info. Theory 55, 5 (2009).

Digital Library

[10]

Donoho, D. L. Compressed sensing. IEEE Trans. Info. Theory 52, 4 (Apr. 2006), 1289--1306.

Digital Library

[11]

Donoho, D. L., Stark, P. B. Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49, 3 (June 1989) 906--931.

Digital Library

[12]

Donoho, D. L., Tsaig, Y., Drori, I., Starck, J.-L. Sparse solution of underdetermined linear equations by stagewise Orthogonal Matching Pursuit (StOMP). Submitted for publication (2007)

[13]

Foucart, S. A note on guaranteed sparse recovery via &ell;₁-minimization. Appl. Comput. Harmon. Anal. (2010). To appear.

[14]

Gilbert, A., Strauss M., Tropp J., Vershynin R. Algorithmic linear dimension reduction in the &ell;₁ norm for sparse vectors. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing (Sept. 2006).

[15]

Gilbert, A., Strauss, M., Tropp, J., Vershynin, R. One sketch for all: fast algorithms for compressed sensing. In Proceedings of the 39th ACM Symposium. Theory of Computing (San Diego, June 2007).

Digital Library

[16]

Gilbert, A. C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M. J. Near-optimal sparse Fourier representations via sampling. In Proceedings of the 2002 ACM Symposium on Theory of Computing STOC (2002), 152--161.

Digital Library

[17]

Kim, S.-J., Koh, K., Lustig, M., Boyd, S., Gorinevsky, D. An interiorpoint method for large-scale &ell;₁-regularized least squares. IEEE J. Sel. Top. Signa. 1, 4 (2007) 606--617.

[18]

Needell, D., Tropp, J. A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. ACM Technical Report 2008--01, California Institute of Technology, Pasadena, July 2008.

[19]

Needell, D., Tropp, J. A. CoSaMP: Iterative signal recovery from noisy samples. Appl. Comput. Harmon. Anal. 26, 3 (2008), 301--321.

[20]

Needell, D., Vershynin, R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE J. Sel. Top. Signa. (2007). To appear.

[21]

Nesterov, Y. E., Nemirovski, A. S. Interior Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994.

[22]

Paige, C. C., Saunders, M. A. LSQR: An algorithm for sparse linear equations and sparse least squares. TOMS 8, 1 (1982), 43--71.

Digital Library

[23]

Rudelson, M., Vershynin, R. Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements. In Proceedings of the 40th Annual Conference on Info. Sciences and Systems, Princeton, Mar. 2006.

[24]

Tropp, J. A., Gilbert, A. C. Signal recovery from random measurements via Orthogonal Matching Pursuit. IEEE Trans. Info. Theory 53, 12 (2007), 4655--4666.

Digital Library

Cited By

Ye MLi SCheng CXian J(2025) Analyses of the tail- minimization for fast and enhanced sparse selections Signal Processing10.1016/j.sigpro.2024.109728227(109728)Online publication date: Feb-2025
https://doi.org/10.1016/j.sigpro.2024.109728
Li YJiang MWei DDeng Y(2024)A Novel Image Encryption Algorithm Based on Compressive Sensing and a Two-Dimensional Linear Canonical TransformFractal and Fractional10.3390/fractalfract80200928:2(92)Online publication date: 31-Jan-2024
https://doi.org/10.3390/fractalfract8020092
Omara A(2024)ICe: interior cevian initialization for enhanced reconstruction methodsJournal of Electrical Systems and Information Technology10.1186/s43067-024-00174-w11:1Online publication date: 4-Nov-2024
https://doi.org/10.1186/s43067-024-00174-w
Show More Cited By

Index Terms

CoSaMP: iterative signal recovery from incomplete and inaccurate samples
1. Mathematics of computing
  1. Information theory
    1. Coding theory
  2. Mathematical software
2. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Recommendations

Stochastic CoSaMP: Randomizing Greedy Pursuit for Sparse Signal Recovery
ECML PKDD 2016: European Conference on Machine Learning and Knowledge Discovery in Databases - Volume 9851

In this paper, we formulate the K-sparse compressed signal recovery problem with the $$L_0$$ norm within a Stochastic Local Search SLS framework. Using this randomized framework, we generalize the popular sparse recovery algorithm CoSaMP, creating ...
Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In ...
Image Adaptive Reconstruction Based on Compressive Sensing via CoSaMP
ICISCE '15: Proceedings of the 2015 2nd International Conference on Information Science and Control Engineering

Compressive Sampling Matching Pursuit (CoSaMP) is a new iterative recovery algorithm which has splendid theoretical guarantees for convergence and delivers the same guarantees as the best optimization-based approaches. In this paper, we propose a new ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 53, Issue 12

December 2010

127 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/1859204

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2010

Published in CACM Volume 53, Issue 12

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

274
Total Citations
View Citations
7,294
Total Downloads

Downloads (Last 12 months)629
Downloads (Last 6 weeks)124

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ye MLi SCheng CXian J(2025) Analyses of the tail- minimization for fast and enhanced sparse selections Signal Processing10.1016/j.sigpro.2024.109728227(109728)Online publication date: Feb-2025
https://doi.org/10.1016/j.sigpro.2024.109728
Li YJiang MWei DDeng Y(2024)A Novel Image Encryption Algorithm Based on Compressive Sensing and a Two-Dimensional Linear Canonical TransformFractal and Fractional10.3390/fractalfract80200928:2(92)Online publication date: 31-Jan-2024
https://doi.org/10.3390/fractalfract8020092
Omara A(2024)ICe: interior cevian initialization for enhanced reconstruction methodsJournal of Electrical Systems and Information Technology10.1186/s43067-024-00174-w11:1Online publication date: 4-Nov-2024
https://doi.org/10.1186/s43067-024-00174-w
Nareddy KKamath ASeelamantula C(2024)Tight-Frame-Like Analysis-Sparse Recovery Using Nontight Sensing MatricesSIAM Journal on Imaging Sciences10.1137/23M162584617:3(1587-1618)Online publication date: 17-Jul-2024
https://doi.org/10.1137/23M1625846
Xia GXiao PLi BZhang YZhou H(2024)Joint Beamforming and Compressed Sensing for Uplink Grant-Free AccessIEEE Transactions on Wireless Communications10.1109/TWC.2024.337347423:9_Part_1(10575-10591)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TWC.2024.3373474
Lien ZLee C(2024)Deep Neural Network Based Active User Detection for Grant-Free Multiple AccessIEEE Transactions on Vehicular Technology10.1109/TVT.2024.338691273:9(13007-13022)Online publication date: Sep-2024
https://doi.org/10.1109/TVT.2024.3386912
Nguyen UPhan NTan PTa HNguyen L(2024)Coupled Quadratic Congruential Random Number Generator-Aided Measurement Matrix ConstructionIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2023.333870273(1-8)Online publication date: 2024
https://doi.org/10.1109/TIM.2023.3338702
Wu YZhang ZQiu XZhao YYu W(2024)MF-JMoDL-Net: A Sparse SAR Imaging Network for Undersampling Pattern Design Toward Suppressed Azimuth AmbiguityIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.339782662(1-18)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3397826
Lu YCai PYu JShi SLi MGe HFu X(2024)Compressed Sensing Signal Reconstruction for Real-Time Machine Vision Systems2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC54092.2024.10831568(1504-1509)Online publication date: 6-Oct-2024
https://doi.org/10.1109/SMC54092.2024.10831568
Sun ZWang SJia KPan S(2024)A Beamspace-Based Orthogonal Matching Pursuit DOA Estimation Algorithm2024 7th International Conference on Information Communication and Signal Processing (ICICSP)10.1109/ICICSP62589.2024.10809217(85-89)Online publication date: 21-Sep-2024
https://doi.org/10.1109/ICICSP62589.2024.10809217
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents