Compressed sensing and best -term approximation

Authors:
Albert Cohen, Wolfgang Dahmen and Ronald DeVore

Journal:
J. Amer. Math. Soc. **22** (2009), 211-231

MSC (2000):
Primary 94A12, 94A15, 68P30, 41A46, 15A52

Published electronically:
July 31, 2008

MathSciNet review:
2449058

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 , allocate linear measurements of , and we describe the range of for which these measurements encode enough information to recover in the sense of to the accuracy of best -term approximation. We also consider the problem of having such accuracy only with high probability.

**1.**D. Achilioptas, Database-friendly random projections, Proc. ACM Symposium on the Principles of Database Systems, pp. 274-281, 2001.**2.**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/s00365-007-9003-x.**3.**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**, 10.1109/TIT.2005.862083**4.**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**, 10.1002/cpa.20124**5.**Emmanuel J. Candes and Terence Tao,*Decoding by linear programming*, IEEE Trans. Inform. Theory**51**(2005), no. 12, 4203–4215. MR**2243152**, 10.1109/TIT.2005.858979**6.**Emmanuel J. Candes and Terence Tao,*Near-optimal signal recovery from random projections: universal encoding strategies?*, IEEE Trans. Inform. Theory**52**(2006), no. 12, 5406–5425. MR**2300700**, 10.1109/TIT.2006.885507**7.**G. Cormode and S. Muthukrishnan, Towards an algorithmic theory of compressed sensing, Technical Report 2005-25, DIMACS, 2005, also Proc. SIROCCO, 2006.**8.**David L. Donoho,*Compressed sensing*, IEEE Trans. Inform. Theory**52**(2006), no. 4, 1289–1306. MR**2241189**, 10.1109/TIT.2006.871582**9.**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****10.**A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss, How to summarize the universe: Dynamic maintenance of quantiles,*Proc. VLDB*, 2002, 454-465.**11.**Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss,*Fast, small-space algorithms for approximate histogram maintenance*, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 389–398. MR**2121164**, 10.1145/509907.509966**12.**A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss,*Near-optimal sparse Fourier representations via sampling*, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 152–161. MR**2121138**, 10.1145/509907.509933**13.**E. D. Gluskin,*Norms of random matrices and diameters of finite-dimensional sets*, Mat. Sb. (N.S.)**120(162)**(1983), no. 2, 180–189, 286 (Russian). MR**687610****14.**B. S. Kašin,*The widths of certain finite-dimensional sets and classes of smooth functions*, Izv. Akad. Nauk SSSR Ser. Mat.**41**(1977), no. 2, 334–351, 478 (Russian). MR**0481792****15.**George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz,*Constructive approximation*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 304, Springer-Verlag, Berlin, 1996. Advanced problems. MR**1393437****16.**Alain Pajor and Nicole Tomczak-Jaegermann,*Subspaces of small codimension of finite-dimensional Banach spaces*, Proc. Amer. Math. Soc.**97**(1986), no. 4, 637–642. MR**845980**, 10.1090/S0002-9939-1986-0845980-8**17.**J. A. Tropp and A. C. Gilbert, Signal recovery from partial information via orthogonal matching pursuit, preprint, April 2005.

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
94A12,
94A15,
68P30,
41A46,
15A52

Retrieve articles in all journals with MSC (2000): 94A12, 94A15, 68P30, 41A46, 15A52

Additional Information

**Albert Cohen**

Affiliation:
Laboratoire Jacques-Louis Lions, Université Pierre et Marie Curie 175, rue du Chevaleret, 75013 Paris, France

Email:
cohen@ann.jussieu.fr

**Wolfgang Dahmen**

Affiliation:
Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, D-52056 Aachen, Germany

Email:
dahmen@igpm.rwth-aachen.de

**Ronald DeVore**

Affiliation:
Industrial Mathematics Institute, University of South Carolina, Columbia, South Carolina 29208

Email:
devore@math.sc.edu

DOI:
http://dx.doi.org/10.1090/S0894-0347-08-00610-3

Keywords:
Compressed sensing,
best $k$-term approximation,
instance optimal decoders,
Gelfand width,
null space property,
restricted isometry property,
random matrices,
Gaussian and Bernoulli ensembles,
$\ell _1$-minimization,
mixed instance optimality,
instance optimality in probability.

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

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.