Approximation with highly redundant dictionaries

Rémi Gribonval 1 Morten Nielsen 2
1 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Ten years ago, Mallat and Zhang proposed the Matching Pursuit algorithm : since then, the dictionary approach to signal processing has been a very active field. In this paper, we try to give an overview of a series of recent results in the field of sparse decompositions and nonlinear approximation with redundant dictionaries. We discuss sufficient conditions on a decomposition to be the unique and simultaneous sparsest \ell^\tau expansion for all \tau,0 \leq \tau \leq 1. In particular, we prove that any decomposition has this nice property if the number of its nonzero coefficients does not exceed a quantity which we call the spread of the dictionary. After a brief discussion of the interplay between sparse decompositions and nonlinear approximation with various families of algorithms, we review several recent results that provide sufficient conditions for the Matching Pursuit, Orthonormal Matching Pursuit, and Basis Pursuit algorithms to have good recovery properties. The most general conditions are not straightforward to check, but weaker estimates based on the notions of coherence of the dictionary are recalled, and we discuss how these results can be applied to approximation and sparse decompositions with highly redundant incoherent dictionaries built by taking the union of several orthonormal bases. Eventually, based on Bernstein inequalities, we discuss how much approximation power can be gained by replacing a single basis with such redundant dictionaries.
Type de document :
Communication dans un congrès
Unser, M. and Aldroubi, A. and Laine, A~.F. Proc. SPIE '03, Aug 2003, San Diego, CA, United States. Society of Photo-Optical Instrumentation Engineers, 5207 Wavelets: Applications in Signal and Image Processing X, pp. 216-227, 2003, 〈10.1117/12.504776〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00576208
Contributeur : Rémi Gribonval <>
Soumis le : dimanche 13 mars 2011 - 16:19:06
Dernière modification le : mardi 24 avril 2018 - 16:16:02
Document(s) archivé(s) le : mardi 14 juin 2011 - 02:30:09

Fichier

2003_SPIE_GribonvalEtAl_NonLin...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Rémi Gribonval, Morten Nielsen. Approximation with highly redundant dictionaries. Unser, M. and Aldroubi, A. and Laine, A~.F. Proc. SPIE '03, Aug 2003, San Diego, CA, United States. Society of Photo-Optical Instrumentation Engineers, 5207 Wavelets: Applications in Signal and Image Processing X, pp. 216-227, 2003, 〈10.1117/12.504776〉. 〈inria-00576208〉

Partager

Métriques

Consultations de la notice

446

Téléchargements de fichiers

248