Compressed sensing and best $k$term approximation
HTML articles powered by AMS MathViewer
 by Albert Cohen, Wolfgang Dahmen and Ronald DeVore HTML  PDF
 J. Amer. Math. Soc. 22 (2009), 211231 Request permission
Abstract:
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.References

A D. Achilioptas, Databasefriendly random projections, Proc. ACM Symposium on the Principles of Database Systems, pp. 274281, 2001.
BDDW R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, A simple proof of the restricted isometry property for random matrices, available as “online first”, Constr. Approx. 28 (3) (2008), DOI.10.1007/s003650079003x.
 Emmanuel J. Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489–509. MR 2236170, DOI 10.1109/TIT.2005.862083
 Emmanuel J. Candès, Justin K. Romberg, and Terence Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math. 59 (2006), no. 8, 1207–1223. MR 2230846, DOI 10.1002/cpa.20124
 Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI 10.1109/TIT.2005.858979
 Emmanuel J. Candes and Terence Tao, Nearoptimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406–5425. MR 2300700, DOI 10.1109/TIT.2006.885507 Mu G. Cormode and S. Muthukrishnan, Towards an algorithmic theory of compressed sensing, Technical Report 200525, DIMACS, 2005, also Proc. SIROCCO, 2006.
 David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
 A. Yu. Garnaev and E. D. Gluskin, The widths of a Euclidean ball, Dokl. Akad. Nauk SSSR 277 (1984), no. 5, 1048–1052 (Russian). MR 759962 GKMS A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss, How to summarize the universe: Dynamic maintenance of quantiles, Proc. VLDB, 2002, 454–465.
 Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss, Fast, smallspace algorithms for approximate histogram maintenance, Proceedings of the ThirtyFourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 389–398. MR 2121164, DOI 10.1145/509907.509966
 A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, Nearoptimal sparse Fourier representations via sampling, Proceedings of the ThirtyFourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 152–161. MR 2121138, DOI 10.1145/509907.509933
 E. D. Gluskin, Norms of random matrices and diameters of finitedimensional sets, Mat. Sb. (N.S.) 120(162) (1983), no. 2, 180–189, 286 (Russian). MR 687610
 B. S. Kašin, The widths of certain finitedimensional sets and classes of smooth functions, Izv. Akad. Nauk SSSR Ser. Mat. 41 (1977), no. 2, 334–351, 478 (Russian). MR 0481792
 George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz, Constructive approximation, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 304, SpringerVerlag, Berlin, 1996. Advanced problems. MR 1393437, DOI 10.1007/9783642609329
 Alain Pajor and Nicole TomczakJaegermann, Subspaces of small codimension of finitedimensional Banach spaces, Proc. Amer. Math. Soc. 97 (1986), no. 4, 637–642. MR 845980, DOI 10.1090/S00029939198608459808 TG J. A. Tropp and A. C. Gilbert, Signal recovery from partial information via orthogonal matching pursuit, preprint, April 2005.
Additional Information
 Albert Cohen
 Affiliation: Laboratoire JacquesLouis Lions, Université Pierre et Marie Curie 175, rue du Chevaleret, 75013 Paris, France
 MR Author ID: 308419
 Email: cohen@ann.jussieu.fr
 Wolfgang Dahmen
 Affiliation: Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, D52056 Aachen, Germany
 MR Author ID: 54100
 Email: dahmen@igpm.rwthaachen.de
 Ronald DeVore
 Affiliation: Industrial Mathematics Institute, University of South Carolina, Columbia, South Carolina 29208
 Email: devore@math.sc.edu
 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 ONRN0s00140310051, ONR/DEPSCoR N000140310675 and ONR/DEPSCoR N000140010470; DARPA Grant N660010612001; the Army Research Office Contract DAAD 190210028; the AFOSR Contract UF/USAF F496200310381; the NSF contracts DMS0221642 and DMS0200187; the FrenchGerman PROCOPE contract 11418YB; and by the European Community’s Human Potential Programme under contract HPRNCT20200286, 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), 211231
 MSC (2000): Primary 94A12, 94A15, 68P30, 41A46, 15A52
 DOI: https://doi.org/10.1090/S0894034708006103
 MathSciNet review: 2449058