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

MPTK: Matching Pursuit made Tractable

(1) , (1)
1

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.
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)
Loading...

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More