We now turn to the questions of generating good approximations for
nn term approximation from a general dictionary We shall assume
that the dictionary DD is complete in the Hilbert
space HH. This means that every element in HH
can be approximated arbitrarily well by linear combinations of the
elements of DD. Since the dictionary is no longer an
orthogonal basis as was considered above, we need to revisit how
to find good nn term approximations. Because of redundancy
within the dictionary, we cannot simply pick the largest
coefficients as we saw with a basis. Greedy algorithms are a
method to generate good nn term approximations.
- General Greedy Algorithm
Given ff, we want to generate an nn-term approximation to ff.
f→s=∑ s=1 n c j g j f→s=∑ s=1 n c j g j (1)
The general steps are as follows:
- Initialize: (approximation) s 0 =0s 0 =0, (residual) r 0 =fr 0 =f,
approximation collectionΛ 0 =∅Λ 0 =∅
- Search
DD for some g∈Dg∈D, then add gg to the
set ΛΛ.
- Use {g 1 ,g 2 ,...,g n }{g 1 ,g 2 ,...,g n } to find new
approximation for s n s n .
- Pure Greedy Algorithm (PGA)
Note:
>From r n r n choose g n+1 := argmax |r n (f),g|g n+1 := argmax |r n (f),g| (the gg that causes the largest inner product).
s n+1 =s n +r n (f),ggs n+1 =s n +r n (f),gg(2)
r n+1 =f-s n -f-s n ,gg=f-s n+1 r n+1 =f-s n -f-s n ,gg=f-s n+1 (3)
This method is similar to a steepest decent algorithm for
decreasing the error.
- Orthogonal Greedy Algorithm (OGA)
>From r n r n choose g n+1 := argmax |r n (f),g|g n+1 := argmax |r n (f),g| as in the PGA.
V n+1 :=sp{g 1 ,g 2 ,...,g n+1 }V n+1 :=sp{g 1 ,g 2 ,...,g n+1 }(4)
s n+1 :=p V n+1 f=∑ j=1 n+1 α j g j s n+1 :=p V n+1 f=∑ j=1 n+1 α j g j (5)
where P V P V denotes the orthogonal projection onto the space VV.
We can find s n+1 =P V n+1 fs n+1 =P V n+1 f by solving the linear system of
equations
∑ j=1 n+1 α j g j ,g k =f,g k .∑ j=1 n+1 α j g j ,g k =f,g k .(6)
Then, r n+1 =f-s n+1 r n+1 =f-s n+1 .
- Relaxed Greedy Algorithm (RGA)
>From r n r n choose g n+1 g n+1 in some way (for example, our earlier methods) and then define
s n+1 (f)=αs n +βg n+1 s n+1 (f)=αs n +βg n+1 (7)
Unlike PGA, here we do not make a full step in the correct
direction. For example, one way to proceed is to define
arginf α,β,g ∥f-αs n +βg n ∥=:α * ,β * ,g * arginf α,β,g ∥f-αs n +βg n ∥=:α * ,β * ,g * (8)
This type of greedy algorithm is known to perform the best as
compred with the previous two.
Given XX, DD, it is not practical to
minimize σ n (f) X σ n (f) X by searching over all the
possibilities.
The greedy approximation gives an nn-term
solution with less computation, but does it perform well?
Let
L 1 (D):={f∈X:∑c g g,∑ g∈D |c g |≤M}L 1 (D):={f∈X:∑c g g,∑ g∈D |c g |≤M}(9)
where the smallest MM is the L 1 L 1 norm of ff.
For OGA or RGA as described above, we have
∥f-s n f∥≤Cn -1 2 |f| L 1 .∥f-s n f∥≤Cn -1 2 |f| L 1 .(10)
Remark 5 This is similar to σ n (x) l 2 ≤n -1 2 ∥x∥ l 1 σ n (x) l 2 ≤n -1 2 ∥x∥ l 1 (nn-term approximation) but its
not always quite as good.
