On the exponential convergence of Matching Pursuits in quasi-incoherent dictionaries

Rémi Gribonval 1 Pierre Vandergheynst 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
2 LTS2 - EPFL
Abstract : The purpose of this correspondence is to extend results by Villemoes and Temlyakov about exponential convergence of Matching Pursuit (MP) with some structured dictionaries for "simple" functions in finite or infinite dimension. The results are based on an extension of Tropp's results about Orthogonal Matching Pursuit (OMP) in finite dimension, with the observation that it does not only work for OMP but also for MP. The main contribution is a detailed analysis of the approximation and stability properties of MP with quasi-incoherent dictionaries, and a bound on the number of steps sufficient to reach an error no larger than a penalization factor times the best m-term approximation error.
Keywords : OMP approximation error exponential convergence finite dimension greedy algorithm nonlinear approximation orthogonal matching pursuit quasiincoherent dictionary sparse representation stability property approximation theory greedy algorithms image processing iterative methods numerical stability sparse matrices time-frequency analysis
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2006, 52 (1), pp.255--261. 〈10.1109/TIT.2005.860474〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00544945
Contributeur : Rémi Gribonval <>
Soumis le : samedi 11 décembre 2010 - 17:31:34
Dernière modification le : mercredi 11 avril 2018 - 01:57:39
Document(s) archivé(s) le : samedi 12 mars 2011 - 02:25:17

Fichier

2006_IEEE_TIT_GribVandergheyns...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

INRIA | IRISA | IRISA-D5 | UR1-UFR-ISTIC | UNIV-RENNES | INRIA-RENGRE

Citation

Rémi Gribonval, Pierre Vandergheynst. On the exponential convergence of Matching Pursuits in quasi-incoherent dictionaries. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2006, 52 (1), pp.255--261. 〈10.1109/TIT.2005.860474〉. 〈inria-00544945〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

335

Téléchargements de fichiers

459

Contact


archive-ouverte@inria.fr