Matching pursuit

Given a set of functions (dictionary) $D = \{g_1, g_2, \ldots, g_n\}$ such that $\vert\vert g_i\vert\vert=1$, we can define an optimal $M$-approximation as an expansion, minimizing the error $\epsilon$ of an approximation of signal $f(t)$ by $M$ waveforms:

$$\epsilon=\left\Vert f(t)-\sum_{i=1}^{M} w_i g_{\gamma_i}(t) \right\Vert$$ (1)

where $\{\gamma_i \}_{i=1..M}$ represents the indices of the chosen functions $g_{\gamma_i}$. Finding such an optimal approximation is an NP-hard problem [5]. A suboptimal expansion can be found by means of an iterative procedure, such as the matching pursuit algorithm (MP).

In the first step of MP, the waveform $g_{\gamma_0}$ which best matches the signal $f(t)$ is chosen. In each of the consecutive steps, the 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_{\g... ...i} \in D } \vert<R^nf, g_{\gamma_i}>\vert \end{array}\right .$$ (2)

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

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

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

From this equation we can derive a time-frequency distribution of the signal's energy, that is free of cross-terms, by adding Wigner distributions of selected functions:

$$E f (t, \omega) = \sum_{n=0}^M \vert<R^n f, \;g_{\gamma_n}>\vert^2 \; W g_{\gamma_n} (t, \omega)$$ (5)