DAFx-2020 - Vienna (virtual)

Matching pursuit (MP) algorithms are widely used greedy methods to find K-sparse signal approximations in redundant dictionaries. 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, consisting of translations and modulations of possibly different windows, time- and frequency-shift parameters. The proposed acceleration 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. Previously, coefficient-domain residual updates have been dismissed as having prohibitive memory requirements. By introducing an approximate update step, we can overcome this restriction and greatly improve the performance of matching pursuit at a modest cost in terms of approximation quality per selected atom. An implementation in C with Matlab and GNU Octave interfaces is available, outperforming the standard Matching Pursuit Toolkit (MPTK) by a factor of 3.5 to 70 in the tested conditions. Additionally, we provide experimental results illustrating the convergence of the implementation.

Download