Geodesic
Compressed sensing and best 𝑘-term approximation
Cohen, Albert1 ; Dahmen, Wolfgang2 ; DeVore, Ronald3
1 Laboratoire Jacques-Louis Lions, Université Pierre et Marie Curie 175, rue du Chevaleret, 75013 Paris, France
2 Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, D-52056 Aachen, Germany
3 Industrial Mathematics Institute, University of South Carolina, Columbia, South Carolina 29208
Journal of the American Mathematical Society, Tome 22 (2009) no. 1, pp. 211-231

Voir la notice de l'article provenant de la source American Mathematical Society

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$ 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.
DOI : 10.1090/S0894-0347-08-00610-3

Cohen, Albert 1 ; Dahmen, Wolfgang 2 ; DeVore, Ronald 3

1 Laboratoire Jacques-Louis Lions, Université Pierre et Marie Curie 175, rue du Chevaleret, 75013 Paris, France
2 Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, D-52056 Aachen, Germany
3 Industrial Mathematics Institute, University of South Carolina, Columbia, South Carolina 29208 
@article{10_1090_S0894_0347_08_00610_3,
     author = {Cohen, Albert and Dahmen, Wolfgang and DeVore, Ronald},
     title = {Compressed sensing and best {\dh}‘˜-term approximation},
     journal = {Journal of the American Mathematical Society},
     pages = {211--231},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2009},
     doi = {10.1090/S0894-0347-08-00610-3},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-08-00610-3/}
}
TY  - JOUR
AU  - Cohen, Albert
AU  - Dahmen, Wolfgang
AU  - DeVore, Ronald
TI  - Compressed sensing and best 𝑘-term approximation
JO  - Journal of the American Mathematical Society
PY  - 2009
SP  - 211
EP  - 231
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-08-00610-3/
DO  - 10.1090/S0894-0347-08-00610-3
ID  - 10_1090_S0894_0347_08_00610_3
ER  - 
%0 Journal Article
%A Cohen, Albert
%A Dahmen, Wolfgang
%A DeVore, Ronald
%T Compressed sensing and best 𝑘-term approximation
%J Journal of the American Mathematical Society
%D 2009
%P 211-231
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-08-00610-3/
%R 10.1090/S0894-0347-08-00610-3
%F 10_1090_S0894_0347_08_00610_3
Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald. Compressed sensing and best 𝑘-term approximation. Journal of the American Mathematical Society, Tome 22 (2009) no. 1, pp. 211-231. doi: 10.1090/S0894-0347-08-00610-3

[1] Candã¨S, Emmanuel J., Romberg, Justin, Tao, Terence Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information IEEE Trans. Inform. Theory 2006 489 509

[2] Candã¨S, Emmanuel J., Romberg, Justin K., Tao, Terence Stable signal recovery from incomplete and inaccurate measurements Comm. Pure Appl. Math. 2006 1207 1223

[3] Candes, Emmanuel J., Tao, Terence Decoding by linear programming IEEE Trans. Inform. Theory 2005 4203 4215

[4] Candes, Emmanuel J., Tao, Terence Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 2006 5406 5425

[5] Donoho, David L. Compressed sensing IEEE Trans. Inform. Theory 2006 1289 1306

[6] Garnaev, A. Yu., Gluskin, E. D. The widths of a Euclidean ball Dokl. Akad. Nauk SSSR 1984 1048 1052

[7] Gilbert, Anna C., Guha, Sudipto, Indyk, Piotr, Kotidis, Yannis, Muthukrishnan, S., Strauss, Martin J. Fast, small-space algorithms for approximate histogram maintenance 2002 389 398

[8] Gilbert, A. C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M. Near-optimal sparse Fourier representations via sampling 2002 152 161

[9] Gluskin, E. D. Norms of random matrices and diameters of finite-dimensional sets Mat. Sb. (N.S.) 1983

[10] Kaå¡In, B. S. The widths of certain finite-dimensional sets and classes of smooth functions Izv. Akad. Nauk SSSR Ser. Mat. 1977

[11] Lorentz, George G., Golitschek, Manfred V., Makovoz, Yuly Constructive approximation 1996

[12] Pajor, Alain, Tomczak-Jaegermann, Nicole Subspaces of small codimension of finite-dimensional Banach spaces Proc. Amer. Math. Soc. 1986 637 642

Cité par Sources :