We shall next discuss some notions related to best nn-term
approximation.
- Let XX be a Hilbert space. Given ff, let
Λ ϵ (f)={j:|c j (f)|>ϵ}Λ ϵ (f)={j:|c j (f)|>ϵ}.
The thresholding operator T ϵ T ϵ is defined by
T ϵ f=∑ j∈Λ ϵ (f) C j (f)φ j .T ϵ f=∑ j∈Λ ϵ (f) C j (f)φ j .(1)
It is easy to see that for each ϵϵ, T ϵ fT ϵ f is
the best approximation to ff using NN terms where NN is the
cardinality of Λ ϵ Λ ϵ :
∥f-T ϵ ∥ X =σ N (f) X .∥f-T ϵ ∥ X =σ N (f) X .(2)
Thresholding is
easily implemented on a computer.
- The thresholding scheme above can be generalized if
XX is not a Hilbert space provided the dictionary has
some specific structure. For example, when
- The dictionary is the wavelet basis and X=L p X=L p ,
1<p<∞1<p<∞.
- X=l p X=l p and the dictionary is
the canonical basis δ j =φ j δ j =φ j . ex: (0,0,...,1,0)(0,0,...,1,0)
- For a general Banach space XX and the
dictionary (φ j )(φ j ) is a greedy basis.
We briefly describe the notion of greedy basis.
Given XX, we say (φ j )(φ j ) is a greedy basis
for XX if for each ϵ>0ϵ>0,
∥f-T ϵ f∥ X ≤C(X)σ N (f) X ∥f-T ϵ f∥ X ≤C(X)σ N (f) X (3)
where NN is the cardinality of Λ ϵ Λ ϵ .
A basis φ j φ j is said to be unconditional if
∥∑±c j φ j ∥ X ≤C∥∑c j φ j ∥ X ∥∑±c j φ j ∥ X ≤C∥∑c j φ j ∥ X (4)
or equivalently
∥∑c j φ j ∥ X ≤C∥∑d j φ j ∥ X where |c j |≤|d j |.∥∑c j φ j ∥ X ≤C∥∑d j φ j ∥ X where |c j |≤|d j |.(5)
This is an older concept from functional analysis. In words, this
definition says that if the terms c j c j are rearranged, the series
∑c j φ j ∑c j φ j will still converge. This is not generally
true for all bases.
A basis φ j φ j is said to be democratic if
∥∑ j∈Λ φ j ∥≤C∥∑ j∈Λ ' φ j ∥,∥∑ j∈Λ φ j ∥≤C∥∑ j∈Λ ' φ j ∥,(6)
where the cardinality of Λ ' Λ ' equals the cardinality of
ΛΛ.
(φ j )(φ j ) greedy ↔↔ (φ j )(φ j ) is both
unconditional and democratic.
Some examples involving the last two definitions:
- The fourier basis in L p L p is not democratic, but is
unconditional for l<p<∞l<p<∞.
- The wavelet basis
contains both of these properties, and is therefore greedy.
If X=L p X=L p has (φ j )(φ j ) greedy, B={φ j }B={φ j },
f=∑ j=1 ∞ c j (f)φ j f=∑ j=1 ∞ c j (f)φ j ,
c j (f)=f,ψ j c j (f)=f,ψ j where ψ j ψ j is a dual basis,
f∈A r (B)↔(c j (f))∈w l τ ,1 τ=r+1 pf∈A r (B)↔(c j (f))∈w l τ ,1 τ=r+1 p(7)
and
∥f∥ A r ≈∥c j (f)∥ l τ ∥f∥ A r ≈∥c j (f)∥ l τ (8)
Let us now consider a specific setting that we shall be concerned
with a lot in this course. We shall examine some of the concepts
we have introduced in the finite dimensional space of of all
sequence (points) in R N R N . Recall that we can put many
different norms on this space including the ℓ p ℓ p norms and the
weak ℓ p ℓ p norms.
Given a vector =(x 1 ,x 2 ,...,x N )∈R N =(x 1 ,x 2 ,...,x N )∈R N . The best
approximation to xx from Σ n Σ n in the ℓ p ℓ p norm is to
take the vector in Σ n Σ n which shares the nn largest values
of xx. Its error of approximation satisfies
σ n (x) ℓ p ≤Cn -r ∥x∥ w l τ ,1 τ=r+1 pσ n (x) ℓ p ≤Cn -r ∥x∥ w l τ ,1 τ=r+1 p(9)
∥x∥ w l τ ≤∥x∥ l τ ,1 τ=r+1 p∥x∥ w l τ ≤∥x∥ l τ ,1 τ=r+1 p.
For p=1p=1 and r=3r=3, σ n (x) ℓ 1 ≤Cn -3 ∥x∥ w l τ σ n (x) ℓ 1 ≤Cn -3 ∥x∥ w l τ and 1 τ=41 τ=4. In words,
this equation shows what kind of ττ is needed for a given
decay rate (or given some ττ, what kind of decay rate will be
achieved) to approximate with certain ability.
Show σ n (x) l p ≤Cn -r ∥x∥ l τ σ n (x) l p ≤Cn -r ∥x∥ l τ holds with C=1C=1.
Proof: Let Λ n :={i:|x i | largest }Λ n :={i:|x i | largest },
σ n (x) l p p =∑ i∉Λ n |x i | p σ n (x) l p p =∑ i∉Λ n |x i | p (10)
≤∑ i∉Λ n |x i | p-τ |x i | τ ≤∑ i∉Λ n |x i | p-τ |x i | τ (11)
≤(∥x∥ w l τ n -1 τ ) p-τ (∑|x i | τ )≤(∥x∥ w l τ n -1 τ ) p-τ (∑|x i | τ )(12)
≤∥x∥ l τ p-τ ∥x∥ l τ τ n=n -rp ∥x∥ l τ p ≤∥x∥ l τ p-τ ∥x∥ l τ τ n=n -rp ∥x∥ l τ p (13)
and so
σ n (x) l p p ≤n -rp ∥x∥ l τ p σ n (x) l p p ≤n -rp ∥x∥ l τ p (14)
σ n (x) l p ≤n -r ∥x∥ l τ σ n (x) l p ≤n -r ∥x∥ l τ
For X=L p X=L p , {φ j }{φ j } a wavelet basis, we can say
wavelet coefficients of ff are in l p l p is equivalent to ff
is in a certain Besov class (roughly speaking ff has rr
derivatives and f (r) ∈L τ f (r) ∈L τ ). We refer the reader to
(Reference) for precise formulations of results of this type.
