Technical Program

Paper Detail

Paper:	SPTM-P6.12
Session:	Non-stationary Signals and Time-Frequency Analysis
Time:	Wednesday, May 17, 16:30 - 18:30
Presentation:	Poster
Topic:	Signal Processing Theory and Methods: Non-stationary Signals and Time-Frequency Analysis
Title:	MPTK: Matching Pursuit made Tractable
Authors:	Sacha Krstulovic, Rémi Gribonval, IRISA / INRIA, France
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 times 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 explore and apply MP in the framework of real-life, high-dimensional data processing problems.