Matematicheskie Zametki
General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Mat. Zametki:

Personal entry:
Save password
Forgotten password?

Mat. Zametki, 2007, Volume 82, Issue 6, Pages 829–837 (Mi mz4183)  

This article is cited in 39 scientific papers (total in 39 papers)

A Remark on Compressed Sensing

B. S. Kashina, V. N. Temlyakovb

a Steklov Mathematical Institute, Russian Academy of Sciences
b University of South Carolina

Abstract: Recently, a new direction in signal processing – “Compressed Sensing” is being actively developed. A number of authors have pointed out a connection between the Compressed Sensing problem and the problem of estimating the Kolmogorov widths, studied in the seventies and eighties of the last century. In this paper we make the above mentioned connection more precise.

Keywords: compressed sensing, signal processing, Kolmogorov width, Gelfand width, sparsity, restricted isometry property, combinatorial optimization problem


Full text: PDF file (501 kB)
References: PDF file   HTML file

English version:
Mathematical Notes, 2007, 82:6, 748–755

Bibliographic databases:

UDC: 517.5
Received: 15.08.2007

Citation: B. S. Kashin, V. N. Temlyakov, “A Remark on Compressed Sensing”, Mat. Zametki, 82:6 (2007), 829–837; Math. Notes, 82:6 (2007), 748–755

Citation in format AMSBIB
\by B.~S.~Kashin, V.~N.~Temlyakov
\paper A Remark on Compressed Sensing
\jour Mat. Zametki
\yr 2007
\vol 82
\issue 6
\pages 829--837
\jour Math. Notes
\yr 2007
\vol 82
\issue 6
\pages 748--755

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Xu W., Hassibi B., “Compressed sensing over the Grassmann manifold: A unified analytical framework”, 2008 46th Annual Allerton Conference on Communication, Control, and Computing, v. 1–3, IEEE, 2008, 562–567  crossref  isi  scopus
    2. Zhang F., Pfister H.D., “Compressed sensing and linear codes over real numbers”, 2008 Information Theory and Applications Workshop, IEEE, 2008, 278–281  isi
    3. Guruswami V., Lee J.R., Wigderson A., “Expander codes over reals, Euclidean sections, and compressed sensing”, 2009 47th Annual Allerton Conference on Communication, Control, and Computing, v. 1, 2, IEEE, 2009, 1231–1234  crossref  isi  scopus
    4. Xu W., Hassibi B., “On sharp performance bounds for robust sparse signal recoveries”, 2009 IEEE International Symposium on Information Theory Proceedings (ISIT), v. 1–4, IEEE, 2009, 493–497  isi
    5. O. N. Granichin, D. V. Pavlenko, “Randomization of data acquisition and $\ell_1$-optimization (recognition with compression)”, Autom. Remote Control, 71:11 (2010), 2259–2282  mathnet  crossref  mathscinet  zmath  isi  elib
    6. Guruswami V., Lee J.R., Razborov A., “Almost Euclidean subspaces of $\ell^N_1$ via expander codes”, Combinatorica, 30:1 (2010), 47–68  crossref  mathscinet  isi  elib  scopus
    7. Xu W., Tang A.K., “On the dynamics of $\ell_1$ decoding: a microscopic approach”, 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), IEEE, 2010, 1588–1592  crossref  isi  scopus
    8. Barg A.M., Mazumdar A., “Small ensembles of sampling matrices constructed from coding theory”, 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), IEEE, 2010, 1963–1967  crossref  isi  scopus
    9. Adamczak R., Litvak A.E., Pajor A., Tomczak-Jaegermann N., “Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling”, Constr. Approx., 34:1 (2011), 61–88  crossref  mathscinet  zmath  isi  elib  scopus
    10. Xu W., Hassibi B., “Precise stability phase transitions for $\ell_1$ minimization: a unified geometric framework”, IEEE Trans. Inform. Theory, 57:10 (2011), 6894–6919  crossref  mathscinet  zmath  isi  elib  scopus
    11. Nelson J.L., Temlyakov V.N., “On the size of incoherent systems”, J. Approx. Theory, 163:9 (2011), 1238–1245  crossref  mathscinet  zmath  isi  scopus
    12. Karnin Z.S., “Deterministic construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$”, STOC'11—Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, 645–654  mathscinet  zmath  adsnasa  isi
    13. Mazumdar A., Barg A., “General constructions of deterministic (S)RIP matrices for compressive sampling”, 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), IEEE, 2011, 678–682  crossref  isi  scopus
    14. E. D. Livshits, “On the efficiency of the Orthogonal Matching Pursuit in compressed sensing”, Sb. Math., 203:2 (2012), 183–195  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    15. Tabibiazar A., Basir O., “Energy-efficient compressive state recovery from sparsely noisy measurements”, IEEE Trans. Instrum. Meas., 61:9 (2012), 2392–2400  crossref  isi  elib  scopus
    16. Minakov E.I., Seregin P.S., “Sravnitelnyi analiz metodov parallelnoi rekonstruktsii izobrazhenii magnitno-rezonansnoi tomografii”, Tsifrovaya obrabotka signalov, 2012, no. 3, 23–28  elib
    17. Granichin O.N., “Obratnye svyazi, usrednenie i randomizatsiya v upravlenii i izvlechenii znanii”, Stokhasticheskaya optimizatsiya v informatike, 8:2 (2012), 3–48  elib
    18. S. V. Konyagin, Yu. V. Malykhin, C. S. Rjutin, “On Exact Recovery of Sparse Vectors from Linear Measurements”, Math. Notes, 94:1 (2013), 107–114  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    19. Donoho D.L., Javanmard A., Montanari A., “Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing”, IEEE Trans. Inf. Theory, 59:11 (2013), 7434–7464  crossref  mathscinet  zmath  isi  scopus
    20. Kueng R., Gross D., “Ripless Compressed Sensing From Anisotropic Measurements”, Linear Alg. Appl., 441:SI (2014), 110–123  crossref  mathscinet  zmath  isi  scopus
    21. S. G. Vlăduţ, G. A. Kabatiansky, V. V. Lomakov, “On error correction with errors in both the channel and syndrome”, Problems Inform. Transmission, 51:2 (2015), 132–138  mathnet  crossref  isi  elib
    22. Barg A., Mazumdar A., Wang R., “Restricted Isometry Property of Random Subdictionaries”, IEEE Trans. Inf. Theory, 61:8 (2015), 4440–4450  crossref  mathscinet  zmath  isi  scopus
    23. Chavez-Dominguez J.A., Kutzarova D., “Stability of Low-Rank Matrix Recovery and Its Connections To Banach Space Geometry”, J. Math. Anal. Appl., 427:1 (2015), 320–335  crossref  mathscinet  zmath  isi  scopus
    24. Rostami M., Michailovich O.V., Wang Zh., “Surface Reconstruction in Gradient-Field Domain Using Compressed Sensing”, IEEE Trans. Image Process., 24:5 (2015), 1628–1638  crossref  mathscinet  isi  elib  scopus
    25. Chen X., Wang R., “Tightness of Stability Bounds By Null Space Property”, Wavelets and Sparsity Xvi, Proceedings of Spie, 9597, eds. Papadakis M., Goyal V., VanDeVille D., Spie-Int Soc Optical Engineering, 2015, 95970E  crossref  isi  scopus
    26. Batenkov D. Friedland O. Yomdin Y., “Sampling, Metric Entropy, and Dimensionality Reduction”, SIAM J. Math. Anal., 47:1 (2015), 786–796  crossref  mathscinet  zmath  isi  elib  scopus
    27. Gao Y., Peng J., Yue Sh., Zhao Yu., “on the Null Space Property of l(Q)-Minimization For 0 < Q <= 1 in Compressed Sensing”, J. Funct. space, 2015, 579853  crossref  mathscinet  zmath  isi  elib  scopus
    28. Naidu R.R., “Construction of Sparse Binary Sensing Matrices Using Set Systems”, Mathematical Analysis and its Applications, Springer Proceedings in Mathematics & Statistics, Springer Proceedings in Mathematics & Statistics, 143, eds. Agrawal P., Mohapatra R., Singh U., Srivastava H., Springer, 2015, 267–273  crossref  mathscinet  zmath  isi  scopus
    29. Malek-Mohammadi M., Koochakzadeh A., Babaie-Zadeh M., Jansson M., Rojas C.R., “Successive Concave Sparsity Approximation for Compressed Sensing”, IEEE Trans. Signal Process., 64:21 (2016), 5657–5671  crossref  mathscinet  isi  elib  scopus
    30. Hinrichs A., Kolleck A., Vybiral J., “Carl's inequality for quasi-Banach spaces”, J. Funct. Anal., 271:8 (2016), 2293–2307  crossref  mathscinet  zmath  isi  scopus
    31. Cahill J., Chen X., Wang R., “The gap between the null space property and the restricted isometry property”, Linear Alg. Appl., 501 (2016), 363–375  crossref  mathscinet  zmath  isi  elib  scopus
    32. Kaporin I.E., “Deterministic bounds for restricted isometry in compressed sensing matrices”, Dokl. Math., 93:3 (2016), 273–275  crossref  mathscinet  zmath  isi  elib  scopus
    33. I. E. Kaporin, “Bounding the restricted isometry constants for a tight frame”, Sb. Math., 208:11 (2017), 1646–1660  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    34. Li L., Xu D., Peng H., Kurths J., Yang Y., “Reconstruction of Complex Network Based on the Noise Via Qr Decomposition and Compressed Sensing”, Sci Rep, 7 (2017), 15036  crossref  isi  scopus
    35. Bach F., “Parcimony and Sub-Determined Linear Systems [By Emmanuel Candes]”, Asterisque, 2017, no. 390, 409–426  mathscinet  zmath  isi
    36. Bandeira A.S., Lewis M.E., Mixon D.G., “Discrete Uncertainty Principles and Sparse Signal Processing”, J. Fourier Anal. Appl., 24:4 (2018), 935–956  crossref  mathscinet  isi  scopus
    37. Li G., Yan J., Gu Yu., “Information Theoretic Lower Bound of Restricted Isometry Property Constant”, 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (Icassp), International Conference on Acoustics Speech and Signal Processing Icassp, IEEE, 2019, 5297–5301  isi
    38. Roulet V., Boumal N., d'Aspremont A., “Computational Complexity Versus Statistical Performance on Sparse Recovery Problems”, Inf. Inference, 9:1 (2020), 1–32  crossref  mathscinet  isi
    39. E. E. Egorova, G. A. Kabatyanskii, “Razdelimye kody dlya zaschity multimedia ot nelegalnogo kopirovaniya koalitsiyami”, Probl. peredachi inform., 57:2 (2021), 90–111  mathnet  crossref
  • Математические заметки Mathematical Notes
    Number of views:
    This page:1776
    Full text:442
    First page:121

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021