Compressed sensing and best term approximation
Authors:
Albert Cohen, Wolfgang Dahmen and Ronald DeVore
Journal:
J. Amer. Math. Soc. 22 (2009), 211231
MSC (2000):
Primary 94A12, 94A15, 68P30, 41A46, 15A52
Published electronically:
July 31, 2008
MathSciNet review:
2449058
Fulltext 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, Databasefriendly random projections, Proc. ACM Symposium on the Principles of Database Systems, pp. 274281, 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/s003650079003x.
 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
(2007e:94020), http://dx.doi.org/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
(2007f:94007), http://dx.doi.org/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
(2007b:94313), http://dx.doi.org/10.1109/TIT.2005.858979
 6.
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
(2008c:94009), http://dx.doi.org/10.1109/TIT.2006.885507
 7.
G. Cormode and S. Muthukrishnan, Towards an algorithmic theory of compressed sensing, Technical Report 200525, DIMACS, 2005, also Proc. SIROCCO, 2006.
 8.
David
L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory
52 (2006), no. 4, 1289–1306. MR 2241189
(2007e:94013), http://dx.doi.org/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
(85m:46023)
 10.
A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss, How to summarize the universe: Dynamic maintenance of quantiles, Proc. VLDB, 2002, 454465.
 11.
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, http://dx.doi.org/10.1145/509907.509966
 12.
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, http://dx.doi.org/10.1145/509907.509933
 13.
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
(84g:41021)
 14.
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
(58 #1891)
 15.
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 (97k:41002)
 16.
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
(87i:46040), http://dx.doi.org/10.1090/S00029939198608459808
 17.
J. A. Tropp and A. C. Gilbert, Signal recovery from partial information via orthogonal matching pursuit, preprint, April 2005.
 1.
 D. Achilioptas, Databasefriendly random projections, Proc. ACM Symposium on the Principles of Database Systems, pp. 274281, 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/s003650079003x.
 3.
 E. J. Candès, J. Romberg, and T. Tao, Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information, IEEE Trans. Inf. Theory, 52(2006), 489509. MR 2236170 (2007e:94020)
 4.
 E. Candès, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure and Appl. Math., 59(2006), 12071223. MR 2230846 (2007f:94007)
 5.
 E. Candès, and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory 51(2005), 42034215. MR 2243152 (2007b:94313)
 6.
 E. Candès and T. Tao, Near optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inf. Theory 52(2006), 54065425. MR 2300700 (2008c:94009)
 7.
 G. Cormode and S. Muthukrishnan, Towards an algorithmic theory of compressed sensing, Technical Report 200525, DIMACS, 2005, also Proc. SIROCCO, 2006.
 8.
 D. Donoho, Compressed Sensing, EEE Trans. Information Theory, 52 (2006), 12891306. MR 2241189 (2007e:94013)
 9.
 A. Garnaev and E. D. Gluskin, The widths of a Euclidean ball, Doklady AN SSSR, 277 (1984), 10481052. MR 759962 (85m:46023)
 10.
 A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss, How to summarize the universe: Dynamic maintenance of quantiles, Proc. VLDB, 2002, 454465.
 11.
 A. Gilbert, S. Guha, Y. Kotidis, P. Indyk, S. Muthukrishnan, and M. Strauss, Fast, small space algorithm for approximate histogram maintenance, ACM STOC, 2002, 389398. MR 2121164
 12.
 A. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, Nearoptimal sparse Fourier estimation via sampling, ACM STOC, 2002, 152161. MR 2121138
 13.
 E. D. Gluskin, Norms of random matrices and widths of finitedimensional sets, Math. USSR Sbornik, 48(1984), 173182. MR 0687610 (84g:41021)
 14.
 B. Kashin, The widths of certain finite dimensional sets and classes of smooth functions, Izvestia 41(1977), 334351. MR 0481792 (58:1891)
 15.
 G. G. Lorentz, M. von Golitschek, and Yu. Makovoz, Constructive Approximation: Advanced Problems, Springer Grundlehren, vol. 304, Springer, Berlin, Heidelberg, 1996. MR 1393437 (97k:41002)
 16.
 A. Pajor and N. TomczakJaegermann, Subspaces of small codimension of finite dimensional Banach spaces, Proc. Amer. Math. Soc., vol. 97, 1986, pp. 637642. MR 845980 (87i:46040)
 17.
 J. A. Tropp and A. C. Gilbert, Signal recovery from partial information via orthogonal matching pursuit, preprint, April 2005.
Similar Articles
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 JacquesLouis 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, D52056 Aachen, Germany
Email:
dahmen@igpm.rwthaachen.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/S0894034708006103
PII:
S 08940347(08)006103
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 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
Article copyright:
© Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
