Databases Reference
In-Depth Information
x
s
x
k
e,k
e,k
x
k
x
k
Split
Merge
P
U
U
P
x
o,k
d
x
o,k
k
F I GU R E 15 . 18
Decomposing a sequence using prediction and updating
operations.
Corresponding to the simple prediction operation we can create a simple update equation using
the weighted sum of the neighboring residual values:
s
k
=
x
e
,
k
+
α
d
k
We would like the sequence
{
s
k
}
to have the same average value as the sequence
{
x
k
}
. As there
are only half as many elements in the sequence
{
s
k
}
as in the sequence
{
x
k
}
, this means that
2
k
1
s
k
=
x
k
(94)
k
where the summation range for the right-hand sum is twice that of the left-hand sum. Substi-
tuting for
s
k
we obtain
k
s
k
=
x
e
,
k
+
α
d
k
k
=
x
2
k
+
α
(
x
2
k
+
1
−
(
x
2
k
))
k
=
(
−
α)
x
2
k
+
α
1
x
2
k
+
1
k
k
where we have ignored boundary effects. One way we can get this sum to satisfy Equation (
94
)
is to assume that the sum of the even-indexed components and the odd-indexed components
is the same. Therefore,
1
2
1
−
α
=
α
=
Thus,
d
k
2
s
k
=
x
e
,
k
+
(95)
x
2
k
+
1
−
x
2
k
=
x
e
,
k
+
(96)
2
x
2
k
+
1
+
x
2
k
=
(97)
2
But this (within a scale factor) is simply the Haar wavelet expansion! The Haar wavelet ex-
pansion is such a simple expansion that this might seem like a rather small return for all this
