Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Compressed sensing and best $k$-term approximation
HTML articles powered by AMS MathViewer

by Albert Cohen, Wolfgang Dahmen and Ronald DeVore
J. Amer. Math. Soc. 22 (2009), 211-231
Published electronically: July 31, 2008


Compressed sensing is a new concept in signal processing where one seeks to minimize the number of measurements to be taken from signals while still retaining the information necessary to approximate them well. The ideas have their origins in certain abstract results from functional analysis and approximation theory by Kashin but were recently brought into the forefront by the work of Candès, Romberg, and Tao and of Donoho who constructed concrete algorithms and showed their promise in application. There remain several fundamental questions on both the theoretical and practical sides of compressed sensing. This paper is primarily concerned with one of these theoretical issues revolving around just how well compressed sensing can approximate a given signal from a given budget of fixed linear measurements, as compared to adaptive linear measurements. More precisely, we consider discrete signals $x\in \mathbb {R}^N$, allocate $n<N$ linear measurements of $x$, and we describe the range of $k$ for which these measurements encode enough information to recover $x$ in the sense of $\ell _p$ to the accuracy of best $k$-term approximation. We also consider the problem of having such accuracy only with high probability.
Similar Articles
Bibliographic Information
  • Albert Cohen
  • Affiliation: Laboratoire Jacques-Louis Lions, Université Pierre et Marie Curie 175, rue du Chevaleret, 75013 Paris, France
  • MR Author ID: 308419
  • Email:
  • Wolfgang Dahmen
  • Affiliation: Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, D-52056 Aachen, Germany
  • MR Author ID: 54100
  • Email:
  • Ronald DeVore
  • Affiliation: Industrial Mathematics Institute, University of South Carolina, Columbia, South Carolina 29208
  • Email:
  • Received by editor(s): July 26, 2006
  • Published electronically: July 31, 2008
  • Additional Notes: This research was supported by the Office of Naval Research Contracts ONR-N0s0014-03-1-0051, ONR/DEPSCoR N00014-03-1-0675 and ONR/DEPSCoR N00014-00-1-0470; DARPA Grant N66001-06-1-2001; the Army Research Office Contract DAAD 19-02-1-0028; the AFOSR Contract UF/USAF F49620-03-1-0381; the NSF contracts DMS-0221642 and DMS-0200187; the French-German PROCOPE contract 11418YB; and by the European Community’s Human Potential Programme under contract HPRN-CT-202-00286, BREAKING COMPLEXITY
  • © Copyright 2008 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: J. Amer. Math. Soc. 22 (2009), 211-231
  • MSC (2000): Primary 94A12, 94A15, 68P30, 41A46, 15A52
  • DOI:
  • MathSciNet review: 2449058