Fast matching pursuit with a multiscale dictionary of Gaussian chirps

We introduce a modified matching pursuit algorithm, called fast ridge pursuit, to approximate N-dimensional signals with M Gaussian chirps at a computational cost O(MN) instead of the expected O(MN2 log N). At each iteration of the pursuit, the best Gabor atom is first selected, and then, its scale and chirp rate are locally optimized so as to get a "good" chirp atom, i.e., one for which the correlation with the residual is locally maximized. A ridge theorem of the Gaussian chirp dictionary is proved, from which an estimate of the locally optimal scale and chirp is built. The procedure is restricted to a sub-dictionary of local maxima of the Gaussian Gabor dictionary to accelerate the pursuit further. The efficiency and speed of the method is demonstrated on a sound signal.