Harmonic Analysis and Applications

June 4-8, 2018


"Fast Matching Pursuit with Multi-Gabor Dictionaries"

Prusa, Zdenek

Finding the best K-sparse approximation of a signal in a redundant dictionary is an NP-hard problem. Suboptimal greedy matching pursuit algorithms are generally used for such task. In this work, we present an acceleration technique of the matching pursuit algorithm acting on a multi-Gabor dictionary; a concatenation of several Gabor-type time-frequency dictionaries; each of which consisting of translations and modulations of a possibly different prototype window and time and frequency shift parameters. The technique is based on pre-computing and thresholding inner products between atoms and on updating the residuum and the approximation error estimate directly in the coefficient domain i.e. without the round-trip to the signal domain.

« back