Matching pursuit

Remarks

By construction $f = f_k + r_k$, and $f_k$ is an n-term approximant with $n = k$. Since $r_k$ is orthogonal to $g_k$, $\norm{r_k}^2 = \norm{r_{k-1}}^2 - \abs{\ip{r_{k-1}}{g_k}}^2$, so the residual norms never increase. When the supremum in clause 2 is not attained, one uses a weak version that only asks for a fixed fraction $t \in (0, 1]$ of it. Example: in $\R^2$ with $\mathcal{D} = \set{e_1, e_2, u}$, $u = (1, 1)/\sqrt{2}$, and $f = (2, 1)$. The correlations are $2$, $1$ and $3/\sqrt{2} \approx 2.12$, so $g_1 = u$, $f_1 = (3/2, 3/2)$ and $r_1 = (1/2, -1/2)$. Then $\ip{r_1}{u} = 0$ and $\abs{\ip{r_1}{e_1}} = \abs{\ip{r_1}{e_2}} = 1/2$; choosing $g_2 = e_1$ gives $r_2 = (0, -1/2)$, and $g_3 = e_2$ gives $r_3 = 0$. Non-example: choosing $g_1 = e_1$ at the first step fails clause 2, since $\abs{\ip{f}{e_1}} = 2 < 3/\sqrt{2}$. Orthogonal matching pursuit replaces clause 3 by taking $f_k$ to be the orthogonal projection of $f$ onto the span of $g_1, \dots, g_k$ and $r_k = f - f_k$.