MPTK: Matching Pursuit made Tractable - Archive ouverte HAL Access content directly
Conference Papers Year : 2006

MPTK: Matching Pursuit made Tractable

(1) , (1)


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.
Fichier principal
Vignette du fichier
2006_ICASSP_KrstulovicGribonval_MPTK.pdf (251.08 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00544919 , version 1 (08-02-2011)



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⟩
364 View
620 Download



Gmail Facebook Twitter LinkedIn More