We now look at how well f∈Xf∈X can be approximated by
nn functions in the dictionary DD.
We define the error of nn-term approximation
of ff by the elements of the dictionary DD as
(1)σn(f)X:=σn(f,D)X:=infs∈Σn∥f-s∥X.(1)σn(f)X:=σn(f,D)X:=infs∈Σn∥f-s∥X.
We also define the class of rr-smooth signals in DD as(2)Ar:=Ar(D):={f∈X,σn(f)≤Mn-r
for some
M}(2)Ar:=Ar(D):={f∈X,σn(f)≤Mn-r
for some
M},
with the corresponding norm
∥
f
∥
A
r
=
sup
n
=
1
,
2
,
…
n
r
σ
n
(
f
)
X
∥
f
∥
A
r
=
sup
n
=
1
,
2
,
…
n
r
σ
n
(
f
)
X
.
In general, the larger rr is, the 'smoother' the function s∈Ar(D)Xs∈Ar(D)X. Note also that
Ar⊆Ar′Ar⊆Ar′ if r>r′r>r′. Given ff,
let r(f)=sup{r:f∈Ar}r(f)=sup{r:f∈Ar} be a measure of the
"smoothness" of ff, i.e. a quantification of compressibility.
Let X=HX=H, a Hilbert space such as X=L2(R)X=L2(R), and assume
D=BD=B - an orthonormal basis on XX; i.e. if
B={ϕi}iB={ϕi}i, then ϕi,ϕj=δi,jϕi,ϕj=δi,j, where δi,jδi,j is the Kronecker delta. This
also means that each f∈Xf∈X has an expansion f=∑jcj(f)ϕjf=∑jcj(f)ϕj, where cj(f)=f,ϕjcj(f)=f,ϕj. We
also have ∥f∥X2=∑j=1∞|cj(f)|2∥f∥X2=∑j=1∞|cj(f)|2.
Recall the definition of ℓpℓp spaces: let (aj)∈R(aj)∈R; then (aj)∈ℓp(aj)∈ℓp if
∥
(
a
j
)
∥
ℓ
p
<
∞
∥
(
a
j
)
∥
ℓ
p
<
∞
with
∥
(
a
j
)
∥
ℓ
p
=
(
∑
j
|
a
j
|
p
)
1
/
p
∥
(
a
j
)
∥
ℓ
p
=
(
∑
j
|
a
j
|
p
)
1
/
p
for p<∞p<∞ and
∥
(
a
j
)
∥
ℓ
p
=
sup
j
|
a
j
|
∥
(
a
j
)
∥
ℓ
p
=
sup
j
|
a
j
|
for p=∞p=∞. We also recall
that for LpLp spaces on compact sets, Lp⊂Lp′Lp⊂Lp′ if
p>p′p>p′. The opposite is true for ℓpℓp spaces: ℓp⊂ℓp′ℓp⊂ℓp′ if p<p′p<p′. Hence, the smaller the value of
pp is, the “smaller” ℓpℓp is.
Does there exist a sequence (aj)(aj) with
∥
(
a
j
)
∥
ℓ
1
=∑j|aj|<∞
∥
(
a
j
)
∥
ℓ
1
=∑j|aj|<∞
but with
∥
(
a
j
)
∥
ℓ
p
=(∑j|aj|p)1p=∞
∥
(
a
j
)
∥
ℓ
p
=(∑j|aj|p)1p=∞ for all 0<p<10<p<1? Consider the sequence an=1n(logn)1+δan=1n(logn)1+δ. We see that (an)∈ℓ1(an)∈ℓ1
but
∥
(
a
n
)
∥
ℓ
p
=∞
∥
(
a
n
)
∥
ℓ
p
=∞ for all 0<p<10<p<1.
A sequence (an)(an) is in ℓpℓp if the sorted magnitudes of the
anan decay faster than n-1pn-1p.
Define an*an* as the element of the sequence (an)(an) with the
nthnth largest magnitude, and denote (an*)(an*) as the
decreasing rearrangement of (an)(an). It is easy to show that
k
(
a
k
*
)
p
≤
∑
n
(
a
n
)
p
k
(
a
k
*
)
p
≤
∑
n
(
a
n
)
p
for all kk; also, if (an)∈ℓp(an)∈ℓp, then
a
k
*
≤
∥
(
a
n
)
∥
ℓ
p
k
-
1
p
a
k
*
≤
∥
(
a
n
)
∥
ℓ
p
k
-
1
p
.
A sequence (an)(an) is in weak ℓpℓp, denoted
(an)∈wℓp(an)∈wℓp, if ak*≤Mk-1pak*≤Mk-1p. We also
define the quasinorm
∥
(
a
n
)
∥
w
ℓ
p
∥
(
a
n
)
∥
w
ℓ
p
as the
smallest M>0M>0 such that ak*≤Mk-1pak*≤Mk-1p for each
kk.
The sequence an=1nan=1n is in weak
ℓ1ℓ1 but not in ℓ1ℓ1.
For pp,p′p′ such that p′>pp′>p, we have ℓp⊂wℓp⊂ℓp′ℓp⊂wℓp⊂ℓp′.
Let D=BD=B be an orthonormal basis for the Hilbert space
X=HX=H. For f∈Xf∈X with representation in B=[ϕ1,ϕ2,…]B=[ϕ1,ϕ2,…] as f=∑ncn(f)ϕnf=∑ncn(f)ϕn, we have f∈Ar(B)Xf∈Ar(B)X if and only if the sequence
(cn(f))∈wℓτ(cn(f))∈wℓτ, with 1τ=r+121τ=r+12.
Moreover, there exist C0,C0′∈RC0,C0′∈R such that
C0′∥(cn(f))∥wℓτ≤∥f∥Ar≤C0∥(cn(f))∥wℓτC0′∥(cn(f))∥wℓτ≤∥f∥Ar≤C0∥(cn(f))∥wℓτ.
Let r=12r=12. f∈A12f∈A12 if and only if (cn(f))∈wℓτ
(cn(f))∈wℓτ
,
i.e. if cn*(f)≤Mn-1=Mncn*(f)≤Mn-1=Mn.
We prove the converse statement; the forward
statement proof is left to the reader. We would like to show that
if (cn(f))∈wℓτ(cn(f))∈wℓτ, then f∈Arf∈Ar, with r=1τ-12r=1τ-12. The best nn-term approximation of
ff in BB is of the form s=∑k∈Λakϕk,♯Λ≤ns=∑k∈Λakϕk,♯Λ≤n. Therefore, we have:
(3)
σ
n
(
f
)
X
=
inf
s
∈
Σ
n
∥
f
-
s
∥
X
=
inf
s
∈
Σ
n
∥
∑
k
∈
Λ
(
c
k
(
f
)
-
a
k
)
ϕ
k
+
∑
k
∉
Λ
c
k
(
f
)
ϕ
k
∥
X
=
inf
s
∈
Λ
∑
k
∈
Λ
(
c
k
(
f
)
-
a
k
)
2
+
∑
k
∉
Λ
(
c
k
(
f
)
)
2
=
∑
k
=
n
+
1
∞
|
c
k
*
(
f
)
|
2
≤
M
2
∑
k
=
n
+
1
∞
k
-
2
τ
≤
M
2
∑
k
=
n
+
1
∞
k
-
2
r
-
1
(since
(
c
n
(
f
)
)
∈
w
ℓ
p
)
,
(3)
σ
n
(
f
)
X
=
inf
s
∈
Σ
n
∥
f
-
s
∥
X
=
inf
s
∈
Σ
n
∥
∑
k
∈
Λ
(
c
k
(
f
)
-
a
k
)
ϕ
k
+
∑
k
∉
Λ
c
k
(
f
)
ϕ
k
∥
X
=
inf
s
∈
Λ
∑
k
∈
Λ
(
c
k
(
f
)
-
a
k
)
2
+
∑
k
∉
Λ
(
c
k
(
f
)
)
2
=
∑
k
=
n
+
1
∞
|
c
k
*
(
f
)
|
2
≤
M
2
∑
k
=
n
+
1
∞
k
-
2
τ
≤
M
2
∑
k
=
n
+
1
∞
k
-
2
r
-
1
(since
(
c
n
(
f
)
)
∈
w
ℓ
p
)
,
where M:=∥(cn(f)∥wℓpM:=∥(cn(f)∥wℓp.
We prove the converse statement; the forward
statement proof is left to the reader. We would like to show that
if (cn(f))∈wℓτ(cn(f))∈wℓτ, then f∈Arf∈Ar, with r=
