R. Baraniuk, M. Davenport, R. Devore, and M. Wakin, A Simple Proof of the Restricted Isometry Property for Random Matrices, Constructive Approximation, vol.159, issue.2, 2008.
DOI : 10.1007/s00365-007-9003-x

D. Baron, M. Duarte, S. Sarvotham, M. Wakin, and R. Baraniuk, An information-theoretic approach to distributed compressed sensing, Proc. 45rd Conference on Communication, Control, and Computing, 2005.

D. Baron, M. Wakin, M. Duarte, S. Sarvotham, and R. Baraniuk, Distributed compressed sensing of jointly sparse signals, Signals, Systems and Computers, pp.1537-1541, 2005.

E. Candès, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, vol.346, issue.9-10, 2008.
DOI : 10.1016/j.crma.2008.03.014

E. Candès, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, vol.7, issue.8, pp.1207-1223, 2006.
DOI : 10.1002/cpa.20124

E. Candes and T. Tao, Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?, IEEE Transactions on Information Theory, vol.52, issue.12, pp.5406-5425, 2006.
DOI : 10.1109/TIT.2006.885507
URL : http://arxiv.org/abs/math/0410542

J. Chen and X. Huo, Sparse representations for multiple measurement vectors (MMV) in an over-complete dictionary, International Conference on Acoustics, Speech and Signal Processing (ICASSP-2005), 2005.

J. Chen and X. Huo, Theoretical Results on Sparse Representations of Multiple-Measurement Vectors, IEEE Transactions on Signal Processing, vol.54, issue.12, pp.4634-4643, 2006.
DOI : 10.1109/TSP.2006.881263

D. Donoho and M. Elad, Maximal sparsity representation via l 1 minimization, Proc. Nat. Acad. Sci, pp.369-388, 2003.

D. Donoho, M. Elad, and V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Transactions on Information Theory, vol.52, issue.1, pp.6-18, 2006.
DOI : 10.1109/TIT.2005.860430

D. Donoho, M. Vetterli, R. A. Devore, and I. Daubechies, Data compression and harmonic analysis, IEEE Transactions on Information Theory, vol.44, issue.6, pp.391-432, 1998.
DOI : 10.1109/18.720544
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.3818

R. Gribonval, R. M. Figueras, P. Ventura, and . Vandergheynst, A simple test to check the optimality of sparse signal approximations, EURASIP Signal Processing, special issue on Sparse Approximations in Signal and Image Processing, pp.496-510, 2006.
URL : https://hal.archives-ouvertes.fr/inria-00564503

R. Gribonval and M. Nielsen, Sparse representations in unions of bases, IEEE Transactions on Information Theory, vol.49, issue.12, pp.3320-3325, 2003.
DOI : 10.1109/TIT.2003.820031
URL : https://hal.archives-ouvertes.fr/inria-00570057

R. Gribonval and M. Nielsen, Beyond sparsity : recovering structured representations by 1 minimization and greedy algorithms This is the author version of an article published in a Springer journal. The original publication is available at springerlink.com with DOI: 10.1007/s00041-008-9044-y, Advances in Computational Mathematics, vol.2815, issue.1, pp.23-41, 2005.

R. Gribonval, H. Rauhut, K. Schnass, and P. Vandergheynst, Average case analysis of multichannel thresholding and greedy algorithms, ICASSP07, 2007.

G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, 2001.

M. Ledoux, The Concentration of Measure Phenomenon, 2001.
DOI : 10.1090/surv/089

M. Ledoux and M. Talagrand, Probability in Banach spaces. Isoperimetry and processes, 1991.

Z. Luo, M. Gaspar, J. Liu, and A. Swami, Distributed signal processing in sensor networks, IEEE Signal processing magazine, vol.23, issue.4, pp.14-15, 2006.

H. Rauhut, Stability Results for Random Sampling of Sparse Trigonometric Polynomials, IEEE Transactions on Information Theory, vol.54, issue.12
DOI : 10.1109/TIT.2008.2006382

H. Rauhut, K. Schnass, and P. Vandergheynst, Compressed Sensing and Redundant Dictionaries, IEEE Transactions on Information Theory, vol.54, issue.5, 2008.
DOI : 10.1109/TIT.2008.920190
URL : http://arxiv.org/abs/math/0701131

M. Rudelson and R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, 2006 40th Annual Conference on Information Sciences and Systems, 2006.
DOI : 10.1109/CISS.2006.286463
URL : http://arxiv.org/abs/math/0602559

K. Schnass and P. Vandergheynst, Average Performance Analysis for Thresholding, IEEE Signal Processing Letters, vol.14, issue.11, pp.828-831, 2007.
DOI : 10.1109/LSP.2007.903248

K. Schnass and P. Vandergheynst, Dictionary preconditiong for greedy algorithms, IEEE Transactions on Signal Processing, 2008.

D. Taubman and W. Marcellin, JPEG2000: Image compression fundamentals, standards, and practice, 2002.
DOI : 10.1007/978-1-4615-0799-4

J. Tropp, Greed is Good: Algorithmic Results for Sparse Approximation, IEEE Transactions on Information Theory, vol.50, issue.10, pp.2231-2242, 2004.
DOI : 10.1109/TIT.2004.834793

J. Tropp, Topics in sparse approximation, 2004.

J. Tropp, Just relax: Convex programming methods for subset selection and sparse approximation, IEEE Transactions on Information Theory, vol.51, issue.3, pp.1030-1051, 2006.
DOI : 10.1109/tit.2005.864420
URL : http://authors.library.caltech.edu/9040/1/TROieeetit06.pdf

J. Tropp, On the conditioning of random subdictionaries, Applied and Computational Harmonic Analysis, vol.25, issue.1, 2008.
DOI : 10.1016/j.acha.2007.09.001

J. Tropp, A. Gilbert, and M. Strauss, Algorithms for simultaneous sparse approximations. Part I: Greedy pursuit. Signal Processing, special issue " Sparse approximations in signal and image processing, pp.572-588, 2006.

U. Rennes, I. Irisa, . Campus, and . Beaulieu, 35042 Rennes cedex, France e-mail: remi.gribonval@irisa.fr University of Bonn

. Ecole-polytechnique-fédérale-de-lausanne, This is the author version of an article published in a Springer journal. The original publication is available at springerlink.com with DOI: 10, Signal Processing Institute -ITS, 1015 Lausanne, pp.41-49, 1007.