We will still use the relationship between the functions spaces VjVj and WjWj to find a fast wavelet transform (FWT). We start by recalling that, since both the scaling function ϕ∈V0ϕ∈V0 and the wavelet ψ∈W0ψ∈W0 are in V1,V1, and since V1V1 is generated by ϕ1,k=2ϕ(2x-k),k∈ZZ,ϕ1,k=2ϕ(2x-k),k∈ZZ,
there exist two sequences {hk}{hk} and {gk}∈l2{gk}∈l2 such that
ϕ
(
x
)
=
2
∑
k
h
k
ϕ
(
2
x
-
k
)
ϕ
(
x
)
=
2
∑
k
h
k
ϕ
(
2
x
-
k
)
(1)
ψ
(
x
)
=
2
∑
k
g
k
ϕ
(
2
x
-
k
)
ψ
(
x
)
=
2
∑
k
g
k
ϕ
(
2
x
-
k
)
(2)for all x∈IR.x∈IR.
On the other hand, we know that V1=V0⊕W0V1=V0⊕W0 and as we consider the orthogonal case, it follows immediately that :
2
ϕ
(
2
x
)
=
∑
k
[
h
-
2
k
ϕ
(
x
-
k
)
+
g
-
2
k
ψ
(
x
-
k
)
]
2
ϕ
(
2
x
)
=
∑
k
[
h
-
2
k
ϕ
(
x
-
k
)
+
g
-
2
k
ψ
(
x
-
k
)
]
(3)
2
ϕ
(
2
x
-
1
)
=
∑
k
[
h
1
-
2
k
ϕ
(
x
-
k
)
+
g
1
-
2
k
ψ
(
x
-
k
)
]
.
2
ϕ
(
2
x
-
1
)
=
∑
k
[
h
1
-
2
k
ϕ
(
x
-
k
)
+
g
1
-
2
k
ψ
(
x
-
k
)
]
.
(4)These two equations Equation 3 and Equation 4 can be combined into a single formula:
2
ϕ
(
2
x
-
l
)
=
∑
k
[
h
l
-
2
k
ϕ
(
x
-
k
)
+
g
l
-
2
k
ψ
(
x
-
k
)
]
,
l
∈
Z
Z
,
2
ϕ
(
2
x
-
l
)
=
∑
k
[
h
l
-
2
k
ϕ
(
x
-
k
)
+
g
l
-
2
k
ψ
(
x
-
k
)
]
,
l
∈
Z
Z
,
(5)which is called the “decomposition relation” of ϕϕ and ψ.ψ.
Note that, in the bi-orthogonal case there are four sequences in l2l2 instead of two (denoted here by {hk}{hk} and {gk}{gk}): we have two sequences for the 2-scales relations Equation 1, Equation 2, and two others for the decomposition relations Equation 3, Equation 4. In the following algorithm, we drop the normalisation constant. Suppose that we want to decompose ff as a sum of wavelets and that we have computed, or are given, the inner products of ff with ϕJ,k,ϕJ,k, where JJ is the finest scale we can work on. We denote these inner products by cJ.cJ.
Now, our task is to compute ckjckj and dkj,j<J,dkj,j<J, where
P
j
f
=
∑
k
c
k
j
ϕ
(
2
j
x
-
k
)
;
c
k
j
=
<
f
j
,
ϕ
j
,
k
>
P
j
f
=
∑
k
c
k
j
ϕ
(
2
j
x
-
k
)
;
c
k
j
=
<
f
j
,
ϕ
j
,
k
>
(6)
Q
j
f
=
∑
k
d
k
j
ψ
(
2
j
x
-
k
)
;
d
k
j
=
<
f
j
,
ψ
j
,
k
>
Q
j
f
=
∑
k
d
k
j
ψ
(
2
j
x
-
k
)
;
d
k
j
=
<
f
j
,
ψ
j
,
k
>
(7)By combining Equation 5, Equation 6 and Equation 7,
we get (see [1]):
c
k
j
-
1
=
∑
l
h
l
-
2
k
c
l
j
d
k
j
-
1
=
∑
l
g
l
-
2
k
c
l
j
.
c
k
j
-
1
=
∑
l
h
l
-
2
k
c
l
j
d
k
j
-
1
=
∑
l
g
l
-
2
k
c
l
j
.
(8)Observe that both cj-1cj-1 and dj-1dj-1 are obtained from cjcj by “moving average” schemes, using the decomposition sequence as “weights”, with the exception that these moving averages are sampled only at the even integers. This is called downsampling.
In the orthogonal case, the reconstruction algorithm follows easily from
the relationships:
c
n
j
+
1
=
<
f
j
+
1
,
ϕ
j
+
1
,
n
>
f
j
+
1
=
P
j
+
1
f
=
P
j
f
+
Q
j
f
=
∑
k
c
k
j
ϕ
j
,
k
+
∑
k
d
k
j
ψ
j
,
k
,
c
n
j
+
1
=
<
f
j
+
1
,
ϕ
j
+
1
,
n
>
f
j
+
1
=
P
j
+
1
f
=
P
j
f
+
Q
j
f
=
∑
k
c
k
j
ϕ
j
,
k
+
∑
k
d
k
j
ψ
j
,
k
,
(9)which gives:
c
n
j
+
1
=
∑
k
c
k
j
<
ϕ
j
,
k
,
ϕ
j
+
1
,
n
>
+
∑
k
d
k
j
<
ψ
j
,
k
,
ϕ
j
+
1
,
n
>
=
∑
k
[
c
k
j
h
n
-
2
k
+
d
k
j
g
n
-
2
k
]
.
c
n
j
+
1
=
∑
k
c
k
j
<
ϕ
j
,
k
,
ϕ
j
+
1
,
n
>
+
∑
k
d
k
j
<
ψ
j
,
k
,
ϕ
j
+
1
,
n
>
=
∑
k
[
c
k
j
h
n
-
2
k
+
d
k
j
g
n
-
2
k
]
.
(10)Hence cj+1cj+1 is obtained from cjcj and djdj by two moving average.
