  Finding the best K-sparse approximation of a signal in a redundant dictionary
is an NP-hard problem. Suboptimal greedy matching pursuit (MP) algorithms are
generally used for this task. In this work, we present an acceleration
technique and an implementation of the matching pursuit algorithm acting on a
multi-Gabor dictionary, i.e., a concatenation of several Gabor-type
time-frequency dictionaries, each of which consisting of translations and
modulations of a possibly different window and time and frequency shift
parameters. The technique is based on pre-computing and thresholding inner
products between atoms and on updating the residual directly in the coefficient
domain, i.e., without the round-trip to the signal domain. Since the proposed
acceleration technique involves an approximate update step, we provide
theoretical and experimental results illustrating the convergence of the
resulting algorithm. The implementation is written in C (compatible with C99
and C++11) and we also provide Matlab and GNU Octave interfaces. For some
settings, the implementation is up to 70 times faster than the standard
Matching Pursuit Toolkit (MPTK).
