Matching pursuit

Matching Pursuit (MP) is an iterative procedure, proposed by Mallat and Zhang [6] in 1993. In the first step of MP, the waveform $g_{\gamma_0}$ which best matches the signal $f(t)$ is chosen from a large and redundant set (a dictionary). In each of the consecutive steps, waveform $g_{\gamma_n}$ is matched to the signal $R^n f$, which is the residual left after subtracting results of previous iterations:

$$\left \{ \begin{array}{l} R^0f = f\\ R^nf = <R^nf,g_{\ga... ...i} \in D } \vert<R^nf, g_{\gamma_i}>\vert \end{array}\right .$$ (1)

Orthogonality of $R^{n+1} f$ and $g_{\gamma_n}$ in each step implies energy conservation:

$$\vert\vert f\vert\vert^2 =\sum_{n=0}^{m-1} {\vert<R^n f, \;g_{\gamma_n}>\vert^2} + \vert\vert R^m f\vert\vert^2$$ (2)

For a complete dictionary the procedure converges to $f$:

$$f=\sum_{n=0}^\infty {<R^n f,\; g_{\gamma_n}> g_{\gamma_n} }$$ (3)

Results of the above procedure depend on the set of functions available for the decomposition, i.e. the dictionary. We use Gabor functions (sine-modulated Gaussian), which provide optimal joint time-frequency localization. A real Gabor function can be expressed as:

$$g_\gamma (t) = K(\gamma)e^{-\pi{ \left( {t-u} \over {s} \right) }^2} \sin\left(\omega(t-u)+\phi\right)$$ (4)

$K(\gamma)$ is such that $\vert\vert g_{\gamma}\vert\vert=1$. $\gamma=\{ u,\omega, s, \phi \}$ denotes parameters of possible dictionary's functions (time-frequency atoms).

However, within ranges of these continuous parameters no particular sampling is a priori defined, so we are confronted with a potentially infinite dictionary size. Therefore, in practical implementations, we use subsets of the possible dictionary functions. In choosing such subset, any fixed subsampling of the parameter space introduces a statistical bias in the resulting parametrization. Free of bias parametrization is possible with stochastic dictionaries, where the parameters of a dictionary's atoms are randomized before each decomposition. Further details can be found in [3].

In general, mathematics related to the non-linear MP algorithm can be quite complicated. Nevertheless, for a reasonable application if its results, it is basically enough to understand that structures present in the signal are explained in terms of functions $g_{\gamma_i}$ (equation (3)), chosen for its representation from the dictionary. In case of the Gabor dictionary, each of these structures will be described by it's time and frequency positions, time spread, amplitude and phase.