Matching Pursuit algorithm

MP (introduced in [Mallat and Zhang, 1993]) is an iterative, non-linear procedure which decomposes signal into a linear expansion of waveforms chosen from a redundant dictionary. In the first step, waveform $g_{\gamma_0}$ matching best the signal $f$ is chosen, and in each of consecutive steps waveform $g_{\gamma_n}$ is matched to signal's residuum $R^n f$, left after subtracting results of previous iterations:

$$\left \{ \begin{array}{l} R^0f=f; \\ R^nf=<R^nf,g_{\gamma_n... ..._i} \in G } \vert<R^nf, g_{\gamma_i}>\vert \end{array}\right .$$ (4)

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$$ (5)

If the dictionary is complete, which is usually the case, the procedure converges to $f$, i.e.

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