C. Bennett and R. Sharpley, Interpolation of operators, 1988.

J. Bergh and J. Löfström, Interpolation Spaces, an introduction. Number 223 in Comprehensive Studies in Mathematics, 1976.

D. Bertsekas, Non-Linear Programming, Athena Scientific, 1995.

A. R. Calderbank, P. J. Cameron, W. M. Kantor, and J. J. Seidel, -Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets, Proc. London Math. Soc. (3), pp.436-480, 1997.
DOI : 10.1112/S0024611597000403
URL : https://hal.archives-ouvertes.fr/hal-00084952

C. K. Chui, W. He, and J. Stöckler, Compactly supported tight and sibling frames with maximum vanishing moments, Applied and Computational Harmonic Analysis, vol.13, issue.3, pp.224-262, 2002.
DOI : 10.1016/S1063-5203(02)00510-9

I. Daubechies, B. Han, A. Ron, and Z. Shen, Framelets: MRA-based constructions of wavelet frames, Applied and Computational Harmonic Analysis, vol.14, issue.1, pp.1-46, 2003.
DOI : 10.1016/S1063-5203(02)00511-0

L. Daudet, Représentations structurelles de signaux audiophoniques : méthodes hybrides pour des applicationsàapplicationsà la compression, 2000.

L. Daudet and B. Torrésani, Hybrid representations for audiophonic signal encoding. Signal Processing , special issue on Image and Video Coding Beyond Standards, pp.1595-1617, 2002.
URL : https://hal.archives-ouvertes.fr/hal-01300317

R. A. Devore, B. Jawerth, and V. Popov, Compression of Wavelet Decompositions, American Journal of Mathematics, vol.114, issue.4, pp.737-785, 1992.
DOI : 10.2307/2374796

R. A. Devore and G. G. Lorentz, Constructive approximation, 1993.

D. Donoho and E. J. Candès, Curvelets: A surprisingly effective nonadaptive representation of objects with edges, 1999.

D. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via ??1 minimization, Proceedings of the National Academy of Sciences, vol.100, issue.5, pp.2197-2202, 2003.
DOI : 10.1073/pnas.0437847100
URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC153464

D. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, vol.47, issue.7, pp.2845-2862, 2001.
DOI : 10.1109/18.959265
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.161.9300

M. Elad and A. Bruckstein, A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Transactions on Information Theory, vol.48, issue.9, pp.2558-2567, 2002.
DOI : 10.1109/TIT.2002.801410

H. Feichtinger and G. Zimmermann, An Exotic Minimal Banach Space of Functions, Mathematische Nachrichten, vol.239, issue.1, pp.239-24042, 2002.
DOI : 10.1002/1522-2616(200206)239:1<42::AID-MANA42>3.0.CO;2-#

A. Feuer and A. Nemirovsky, On sparse representation in pairs of bases, IEEE Transactions on Information Theory, vol.49, issue.6, pp.1579-1581, 2003.
DOI : 10.1109/TIT.2003.811926

D. Field and B. Olshausen, Emergence of simple-cell receptive field properties by learning a sparse code for natural images This is the author version of an article published in an Elsevier journal. The original publication is available at www, Nature, vol.381, pp.607-609, 1996.

J. Fuchs, Une approchè a l'estimation et l'identification simultanées, Actes duseizì eme colloque GRETSI, pp.1273-1276, 1997.

J. Fuchs, Detection and estimation of superimposed signals, Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181), pp.1649-1652, 1998.
DOI : 10.1109/ICASSP.1998.681771

J. Fuchs, On Sparse Representations in Arbitrary Redundant Bases, IEEE Transactions on Information Theory, vol.50, issue.6, pp.1341-1344, 2004.
DOI : 10.1109/TIT.2004.828141

A. Gilbert, S. Muthukrishnan, and M. Strauss, Approximation of functions over redundant dictionaries using coherence, The 14th ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pp.243-252, 2003.

A. Gilbert, S. Muthukrishnan, M. Strauss, and J. Tropp, Improved sparse approximation over quasiincoherent dictionaries, Int. Conf. on Image Proc. (ICIP'03), pp.37-40, 2003.

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, Approximation with highly redundant dictionaries, Wavelets: Applications in Signal and Image Processing X, pp.216-227, 2003.
DOI : 10.1117/12.504776
URL : https://hal.archives-ouvertes.fr/inria-00576208

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, Nonlinear Approximation with Dictionaries I. Direct Estimates, Journal of Fourier Analysis and Applications, vol.10, issue.1, pp.51-71, 2004.
DOI : 10.1007/s00041-004-8003-5
URL : https://hal.archives-ouvertes.fr/inria-00567266

R. Gribonval and P. Vandergheynst, On the exponential convergence of matching pursuits in quasi-incoherent dictionaries, IEEE Transactions on Information Theory, vol.52, issue.1, pp.255-261, 2006.
DOI : 10.1109/TIT.2005.860474
URL : https://hal.archives-ouvertes.fr/inria-00544945

K. Gröchenig, Foundations of Time-Frequency Analysis Applied and Numerical Harmonic Analysis, 2001.

K. Gröchenig, Localized frames are finite unions of riesz sequences, Advances in Computational Mathematics, vol.18, issue.2/4, pp.149-157, 2003.
DOI : 10.1023/A:1021368609918

K. Gröchenig, Localization of frames, Banach frames, and the invertibility of the frame operator, J. Fourier Anal. Appl, vol.10, issue.2, 2004.

K. Gröchenig and S. Samarah, Nonlinear Approximation with Local Fourier Bases, Constructive Approximation, vol.16, issue.3, pp.317-332, 2000.
DOI : 10.1007/s003659910014

K. Kreutz-delgado, B. Rao, K. Engan, T. Lee, and T. Sejnowski, Convex/schur-convex (csc) logpriors and sparse coding, 6th Joint Symposium on Neural Computation, pp.65-71, 1999.

S. Mallat, A Wavelet Tour of Signal Processing, 1998.

S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing, vol.41, issue.12, pp.3397-3415, 1993.
DOI : 10.1109/78.258082

K. A. Okoudjou, Embeddings of some classical Banach spaces into modulation spaces, Proc. Amer, pp.1639-1647, 2004.

B. D. Rao, Signal processing with the sparseness constraint, Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181), pp.1861-1864, 1998.
DOI : 10.1109/ICASSP.1998.681826

A. Ron and Z. Shen, Affine systems inL 2 (??? d ) II: Dual systems, The Journal of Fourier Analysis and Applications, vol.89, issue.5, pp.617-637, 1997.
DOI : 10.1007/BF02648888

A. Ron and Z. Shen, Affine Systems inL2(Rd): The Analysis of the Analysis Operator, Journal of Functional Analysis, vol.148, issue.2, pp.408-447, 1997.
DOI : 10.1006/jfan.1996.3079

A. Shrijver, Theory of Linear and Integer Programming, 1998.

J. Starck, M. Elad, and D. Donoho, Image decomposition: separation of texture from piecewise smooth content, Wavelets: Applications in Signal and Image Processing X, 2003.
DOI : 10.1117/12.507447

T. Strohmer and R. Heath, Grassmannian frames with applications to coding and communication, Applied and Computational Harmonic Analysis, vol.14, issue.3, pp.257-275, 2003.
DOI : 10.1016/S1063-5203(03)00023-X
URL : http://doi.org/10.1016/s1063-5203(03)00023-x

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

M. Zibulevsky and B. Pearlmutter, Blind Source Separation by Sparse Decomposition in a Signal Dictionary, Neural Computation, vol.1, issue.4, pp.863-882, 2001.
DOI : 10.1016/S0042-6989(97)00169-7

I. and C. Beaulieu, F-35042 Rennes CEDEX, France E-mail address: Remi.Gribonval@inria.fr Department of Mathematical Sciences, Aalborg University, Fredrik Bajers Vej 7G, DK-9220 Aalborg East, Denmark E-mail address: mnielsen@math.auc.dk c This is the author version of an article published in an Elsevier journal. The original publication is available at www, 2007.