2.4 Greedy algorithms

We now turn to the questions of generating good approximations for $n$ term approximation from a general dictionary We shall assume that the dictionary $\mathcal{D}$ is complete in the Hilbert space $\mathbb{H}$ . This means that every element in $\mathbb{H}$ can be approximated arbitrarily well by linear combinations of the elements of $\mathcal{D}$ . Since the dictionary is no longer an orthogonal basis as was considered above, we need to revisit howto find good $n$ term approximations. Because of redundancy within the dictionary, we cannot simply pick the largestcoefficients as we saw with a basis. Greedy algorithms are a method to generate good $n$ term approximations.

• General Greedy Algorithm Given $f$ , we want to generate an $n$ -term approximation to $f$ .
  $$f\to s=\sum _{s=1}^n{c}_j{g}_j$$
  The general steps are as follows:
  • Initialize: (approximation) $s_0=0$ , (residual) $r_0=f$ , approximation collection ${\Lambda }_0=\varnothing$
  • Search $\mathcal{D}$ for some $g\in \mathcal{D}$ , then add $g$ to the set $\Lambda$ .
  • Use $\{g_1,g_2,...,g_n\}$ to find new approximation for $s_n$ .
  At stage $n$ , we have $s_n$ , $r_n=f-s_n$ , and ${\Lambda }_n=\{g_1,g_2,...,g_n\}$ . There are many types of greedy algorithms. We describe the threemost common in the case $\mathbb{S}$ is a Hilbert space. However, there are anlaogues of these for $L_p$ .
• Pure Greedy Algorithm (PGA) Note:>From $r_n$ choose $g_{n+1}:=\mathrm{argmax}|〈r_n,\left(f\right),,,g〉|$ (the $g$ that causes the largest inner product).
  $$s_{n+1}=s_n+〈r_n,\left(f\right),,,g〉g$$
  $$r_{n+1}=f-s_n-〈f,-,s_n,,,g〉g=f-s_{n+1}$$
  This method is similar to a steepest decent algorithm for decreasing the error.
• Orthogonal Greedy Algorithm (OGA)>From $r_n$ choose $g_{n+1}:=\mathrm{argmax}|〈r_n,\left(f\right),,,g〉|$ as in the PGA.
  $$V_{n+1}:=sp\{g_1,g_2,...,g_{n+1}\}$$
  $$s_{n+1}:=p_{V_{n+1}}f=\sum _{j=1}^{n+1}{\alpha }_j{g}_j$$
  where $P_V$ denotes the orthogonal projection onto the space $V$ . We can find $s_{n+1}=P_{V_{n+1}}f$ by solving the linear system of equations
  $$〈\sum _{j=1}^{n+1},{\alpha }_j,g_j,,,g_k〉=〈f,,,g_k〉.$$
  Then, $r_{n+1}=f-s_{n+1}$ .
• Relaxed Greedy Algorithm (RGA)>From $r_n$ choose $g_{n+1}$ in some way (for example, our earlier methods) and then define
  $$s_{n+1}\left(f\right)=\alpha s_n+\beta g_{n+1}$$
  Unlike PGA, here we do not make a full step in the correct direction. For example, one way to proceed is to define
  $${\mathrm{arginf}}_{\alpha ,\beta ,g}\parallel f-\alpha s_n+\beta g_n\parallel =:{\alpha }^{*},{\beta }^{*},g^{*}$$
  This type of greedy algorithm is known to perform the best as compred with the previous two.

Measuring performance

Given $\mathbb{X}$ , $\mathcal{D}$ , it is not practical to minimize ${\sigma }_n(f{)}_{\mathbb{X}}$ by searching over all the possibilities.The greedy approximation gives an $n$ -term solution with less computation, but does it perform well?

Let

where the smallest $M$ is the ${\mathcal{L}}^1$ norm of $f$ .

For OGA or RGA as described above, we have

Remark 5 This is similar to ${\sigma }_n(x{)}_{l_2}\le n^{-\frac{1}{2}}\parallel x{\parallel }_{l_1}$ ( $n$ -term approximation) but its not always quite as good.