Matching Pursuit

Matching pursuit (MP) was proposed in [9] and [12]. The former publication by S. Mallat and Z. Zhang was accompanied by a freely available software implementation [8]. Below we briefly recall the basic ideas: we are looking for a linear expansion approximating the analyzed signal s(t):

$$s(t)\approx\sum_{i=1}^M a_i g_i(t)$$ (1)

in terms of functions $g_i$ chosen from a large and redundant set (dictionary D). The problem of choosing M functions, which explain the largest part of energy of a given signal, is NP-hard, i.e. computationally intractable. MP offers a sub-optimal solution, obtained by means of an iterative algorithm. In the first step of the iterative procedure we choose the vector which gives the largest product with the signal. The iterative procedure is repeated on the subsequent residua $R^n s$:

$$\left \{ \begin{array}{l} R^0s = s\\ R^ns = <R^ns... ...in D } \vert<R^ns, g_{\gamma_i}>\vert \end{array} \right .$$ (2)

The procedure converges to $s$

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

and conserves signal's energy

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