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.
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00544919
Contributor : Rémi Gribonval <>
Submitted on : Tuesday, February 8, 2011 - 9:28:40 PM
Last modification on : Friday, November 16, 2018 - 1:21:49 AM
Document(s) archivé(s) le : Monday, May 9, 2011 - 2:50:58 AM

File

2006_ICASSP_KrstulovicGribonva...
Files produced by the author(s)

Identifiers

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. pp.III-496 -- III-499, ⟨10.1109/ICASSP.2006.1660699⟩. ⟨inria-00544919⟩

Share

Metrics

Record views

443

Files downloads

502