In Example from Multiresolution analysis, we saw the Haar wavelet basis. This is the simplest wavelet one can imagine, but its approximation properties are not very good. Indeed, the accuracy of the approximation is somehow related to the regularity of the functions ψψ and ϕ.ϕ. We will show this for different settings: in case the function ff is continuous, belongs to a Sobolev or to a Hölder space. But first we introduce the notion of regularity of a MRA.
For wavelet bases (orthonormal or not), there is a link between the regularity of ψψ and the number of vanishing moments. More precisely, we have the following:
Let {ψj,k}{ψj,k} be an orthonormal basis (ONB) in L2(IR),L2(IR), with ψ∈C[0.1ex]0.05em1.25exm,ψ(l)ψ∈C[0.1ex]0.05em1.25exm,ψ(l) bounded for l≤ml≤m and |ψ(x)|≤C(1+|x|)-α|ψ(x)|≤C(1+|x|)-α for α>m+1.α>m+1. Then we have:
∫
x
l
ψ
(
x
)
d
x
=
0
for
l
=
0
,
1
,
...
,
m
.
∫
x
l
ψ
(
x
)
d
x
=
0
for
l
=
0
,
1
,
...
,
m
.
(1)
(this describes the “decay in frequency domain”).
This proposition implies the following corollary:
Suppose the {ψj,k}{ψj,k} are orthonormal. Then it is impossible that ψψ has exponential decay, and that ψ∈C[0.1ex]0.05em1.25ex∞,ψ∈C[0.1ex]0.05em1.25ex∞, with all the derivatives bounded, unless ψ≡0ψ≡0
This corollary tells us that a trade-off has to be done: we have to choose for exponential (or faster) decay in, either time or frequency domain; we cannot have both. We now come to the definition of a r-r-regular MRA (see Entry 5).
(Meyer, 1990)
A MRA is called r-regular (r∈INr∈IN) when ϕ∈C[0.1ex]0.05em1.25exrϕ∈C[0.1ex]0.05em1.25exr and for all m∈IN,m∈IN, there exists a constant Cm>0Cm>0 such that:
|
∂
α
ϕ
(
x
)
∂
x
α
|
≤
C
m
(
1
+
|
x
|
)
-
m
∀
α
≤
r
|
∂
α
ϕ
(
x
)
∂
x
α
|
≤
C
m
(
1
+
|
x
|
)
-
m
∀
α
≤
r
(2)
If one has a r-r-regular MRA, then the corresponding wavelet ψ(x)∈C[0.1ex]0.05em1.25exr,ψ(x)∈C[0.1ex]0.05em1.25exr, satisfies Equation 2 and has rr vanishing moments:
∫
x
k
ψ
(
x
)
d
x
=
0
,
k
=
0
,
1
,
...
,
r
.
∫
x
k
ψ
(
x
)
d
x
=
0
,
k
=
0
,
1
,
...
,
r
.
(3)
We now have the tools needed to measure the decay of approximation error when the resolution (or the finest level) increases.
Let {ψj,k}{ψj,k} come from a r-regular MRA. Then, we have, for a continuous function f∈C[0.1ex]0.05em1.25exs(0<s<r)f∈C[0.1ex]0.05em1.25exs(0<s<r)the following:
|
<
f
,
ψ
j
,
k
>
|
=
O
(
2
-
j
(
s
+
1
/
2
)
)
|
<
f
,
ψ
j
,
k
>
|
=
O
(
2
-
j
(
s
+
1
/
2
)
)
(4)
(s=1s=1).
As ∫ψ(x)¯=0∫ψ(x)¯=0 and |f(x)-f(k/2j)|≤C|x-k/2j|,|f(x)-f(k/2j)|≤C|x-k/2j|, (ff is Lipschitz continuous), we have:
|
<
f
,
ψ
j
,
k
>
|
=
|
2
j
/
2
∫
[
f
(
x
)
-
f
(
k
/
2
j
)
]
ψ
¯
(
2
j
x
-
k
)
d
x
|
,
k
∈
Z
Z
≤
C
2
j
/
2
∫
|
x
-
k
/
2
j
|
|
ψ
¯
(
2
j
x
-
k
)
|
d
x
=
C
2
-
j
/
2
∫
|
2
j
x
-
k
|
|
ψ
¯
(
2
j
x
-
k
)
|
d
x
(
let
u
=
2
j
x
-
k
)
=
2
-
j
(
1
+
1
/
2
)
C
∫
|
u
|
|
ψ
¯
(
u
)
|
d
u
<
∞
=
O
(
2
-
j
(
1
+
1
/
2
)
)
.
|
<
f
,
ψ
j
,
k
>
|
=
|
2
j
/
2
∫
[
f
(
x
)
-
f
(
k
/
2
j
)
]
ψ
¯
(
2
j
x
-
k
)
d
x
|
,
k
∈
Z
Z
≤
C
2
j
/
2
∫
|
x
-
k
/
2
j
|
|
ψ
¯
(
2
j
x
-
k
)
|
d
x
=
C
2
-
j
/
2
∫
|
2
j
x
-
k
|
|
ψ
¯
(
2
j
x
-
k
)
|
d
x
(
let
u
=
2
j
x
-
k
)
=
2
-
j
(
1
+
1
/
2
)
C
∫
|
u
|
|
ψ
¯
(
u
)
|
d
u
<
∞
=
O
(
2
-
j
(
1
+
1
/
2
)
)
.
(5)
For s>1,s>1, we use proposition Proposition 1 and we iterate. □□
Note that the reverse of Proposition 2 is true: Equation 4 entails that ff is in Cs.Cs.
Under the assumptions of
Proposition 2, the error of approximation of a function
f∈C[0.1ex]0.05em1.25exsf∈C[0.1ex]0.05em1.25exs at scale
VJVJ is given by:
|
|
f
-
∑
k
<
f
,
ϕ
J
,
k
>
ϕ
J
,
k
|
|
2
=
O
(
2
-
J
s
)
|
|
f
-
∑
k
<
f
,
ϕ
J
,
k
>
ϕ
J
,
k
|
|
2
=
O
(
2
-
J
s
)
(6)
|
|
f
-
P
J
f
|
|
2
=
|
|
∑
j
≥
J
∑
k
<
f
,
ψ
j
,
k
>
ψ
j
,
k
|
|
2
≤
∑
j
≥
J
C
2
-
j
(
s
+
1
/
2
)
|
|
∑
k
ψ
j
,
k
|
|
2
|
|
f
-
P
J
f
|
|
2
=
|
|
∑
j
≥
J
∑
k
<
f
,
ψ
j
,
k
>
ψ
j
,
k
|
|
2
≤
∑
j
≥
J
C
2
-
j
(
s
+
1
/
2
)
|
|
∑
k
ψ
j
,
k
|
|
2
(7)
Now, if we suppose that |ψ(k)|≤C'(1+|k|)-m,(m≥s+1),|ψ(k)|≤C'(1+|k|)-m,(m≥s+1), we obtain:
|
|
∑
k
ψ
j
,
k
|
|
2
≤
C
'
2
j
/
2
|
|
∑
k
ψ
j
,
k
|
|
2
≤
C
'
2
j
/
2
(8)
Putting inequalities Equation 7 and Equation 8 together, we have:
|
|
f
-
P
J
f
|
|
2
≤
C
'
'
∑
j
≥
J
2
-
j
s
=
C
'
'
(
1
-
2
-
s
)
-
1
2
-
J
s
=
O
(
2
-
J
s
)
□
|
|
f
-
P
J
f
|
|
2
≤
C
'
'
∑
j
≥
J
2
-
j
s
=
C
'
'
(
1
-
2
-
s
)
-
1
2
-
J
s
=
O
(
2
-
J
s
)
□
(9)
Hence, we verify with this last corollary that, as JJ increases, the approximation of ff becomes more accurate.
Let us first recall the definition of weak differentiability, for this notion intervenes in the definition of a Sobolev space.
Let ff be a function defined on the real line which is integrable on every bounded interval. If there exists a function gg defined on the real line which is integrable on every bounded interval such that:
∀
x
≤
y
,
∫
x
y
g
(
u
)
d
u
=
f
(
y
)
-
f
(
x
)
,
∀
x
≤
y
,
∫
x
y
g
(
u
)
d
u
=
f
(
y
)
-
f
(
x
)
,
(10)
then the function ff is called weakly differentiable. The function gg is defined almost everywhere, is called the weak derivative of ff and will be denoted by f'f'.
A function ff is NN-times weakly differentiable if it has derivatives f,f',...,f(N-1)f,f',...,f(N-1) which are continuous and f(N)f(N) which is a weak derivative.
We are now able to define Sobolev spaces.
Let 1≤p<∞,m∈{0,1,...}.1≤p<∞,m∈{0,1,...}. The function f∈Lp(IR)f∈Lp(IR) belongs to the Sobolev space Wpm(IR)Wpm(IR) if it is m-times weakly differentiable, and if f(m)∈Lp(IR).f(m)∈Lp(IR). In particular, Wp0(IR)=Lp(IR).Wp0(IR)=Lp(IR).
The approximation properties of wavelet expansions on Sobolev spaces are
given, among other, in Härdle et.al (see Entry 3).
Suppose we have at our disposal a scaling function ϕϕ which generates a MRA. The approximation theorem can be stated as follows:
(Approx. in Sobolev space)
Let ϕϕ be a scaling function such that {ϕ(.-k),k∈ZZ}{ϕ(.-k),k∈ZZ} is an ONB and the corresponding spaces VjVj are nested. In addition, let ϕϕ be such that
∫
|
ϕ
(
x
)
|
|
x
|
N
+
1
d
x
<
∞
,
∫
|
ϕ
(
x
)
|
|
x
|
N
+
1
d
x
<
∞
,
(11)
and let at least one of the following assumptions hold:
-
ϕ
∈
W
q
N
(
I
R
)
for
some
1
≤
q
<
∞
ϕ
∈
W
q
N
(
I
R
)
for
some
1
≤
q
<
∞
(12)
- ∫xnψ(x)dx=0,n=0,1,...,N,∫xnψ(x)dx=0,n=0,1,...,N, where ψψ is the mother wavelet associated to ϕ.ϕ.
Then, if ff belongs to the Sobolev space WpN+1(IR),WpN+1(IR), we have:
|
|
P
j
f
-
f
|
|
p
=
O
(
2
-
j
(
N
+
1
)
)
,
as
j
→
∞
,
|
|
P
j
f
-
f
|
|
p
=
O
(
2
-
j
(
N
+
1
)
)
,
as
j
→
∞
,
(13)
where PjPj is the projection operator onto Vj.Vj.
Here we assume for simplicity that ψψ has compact support and is C[0.1ex]0.05em1.25ex1C[0.1ex]0.05em1.25ex1 (the formulation of the theorems are slightly different for more general ψψ).
If ff is Hölder continuous with exponent α,0<α<1α,0<α<1 at x0,x0, then
max
k
{
|
<
f
,
ψ
j
,
k
>
|
d
i
s
t
(
x
0
,
s
u
p
p
(
ψ
j
,
k
)
)
-
α
}
=
O
(
2
-
j
(
1
/
2
+
α
)
)
max
k
{
|
<
f
,
ψ
j
,
k
>
|
d
i
s
t
(
x
0
,
s
u
p
p
(
ψ
j
,
k
)
)
-
α
}
=
O
(
2
-
j
(
1
/
2
+
α
)
)
(14)
The reverse of theorem Theorem 1 does not exactly hold: we must modify condition Equation 14 slightly. More precisely, we have the following:
Define, for ϵ>0ϵ>0, the set
S
(
x
0
,
j
,
ϵ
)
=
{
k
∈
Z
Z
|
s
u
p
p
(
ψ
j
,
k
)
∩
]
x
0
-
ϵ
,
x
0
+
ϵ
[
≠
∅
}
.
S
(
x
0
,
j
,
ϵ
)
=
{
k
∈
Z
Z
|
s
u
p
p
(
ψ
j
,
k
)
∩
]
x
0
-
ϵ
,
x
0
+
ϵ
[
≠
∅
}
.
(15)
If, for some ϵ>0ϵ>0 and some α(0<α<1),α(0<α<1),
max
k
∈
S
(
x
0
,
j
,
ϵ
)
|
<
f
,
ψ
j
,
k
>
|
=
O
(
2
-
j
(
1
/
2
+
α
)
)
,
max
k
∈
S
(
x
0
,
j
,
ϵ
)
|
<
f
,
ψ
j
,
k
>
|
=
O
(
2
-
j
(
1
/
2
+
α
)
)
,
(16)
then ff is Hölder continuous with exponent αα at x0.x0.
