MPTK: Matching Pursuit made Tractable

Sacha Krstulovic 1 Rémi Gribonval 1
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 : Matching Pursuit (MP) aims at finding sparse decompositions of signals over redundant bases of elementary waveforms. Traditionally, MP has been considered too slow an algorithm to be applied to real-life problems with high-dimensional signals. Indeed, in terms of floating points operations, its typical numerical implementations have a complexity of O(N^2) and are associated with impractical runtimes. In this paper, we propose a new architecture which exploits the structure shared by many redundant MP dictionaries, and thus decreases its complexity to O(N log N). This architecture is implemented in a new software toolkit, called MPTK (the Matching Pursuit Toolkit), which is able to reach, e.g., 0.25 x real time for a typical MP analysis scenario applied to a 1 hour long audio track. This substantial acceleration makes it possible, from now on, to ex- plore and apply MP in the framework of real-life, high-dimensional data processing problems.
Type de document :
Communication dans un congrès
Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, May 2006, Toulouse, France. IEEE, 3, pp.III-496 -- III-499, 2006, 〈10.1109/ICASSP.2006.1660699〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00544919
Contributeur : Rémi Gribonval <>
Soumis le : mardi 8 février 2011 - 21:28:40
Dernière modification le : jeudi 11 janvier 2018 - 06:20:09
Document(s) archivé(s) le : lundi 9 mai 2011 - 02:50:58

Fichier

2006_ICASSP_KrstulovicGribonva...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sacha Krstulovic, Rémi Gribonval. MPTK: Matching Pursuit made Tractable. Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, May 2006, Toulouse, France. IEEE, 3, pp.III-496 -- III-499, 2006, 〈10.1109/ICASSP.2006.1660699〉. 〈inria-00544919〉

Partager

Métriques

Consultations de la notice

370

Téléchargements de fichiers

391