7.
4 Discrete Wavelet Transforms
Discrete wavelet transforms (DWT) are applied to discrete data sets and produce
discrete outputs. Transforming signals and data vectors by DWT is a process that
resembles the fast Fourier transform (FFT), the Fourier method applied to a set of
discrete measurements.
Table 7.2: The analogy between Fourier and wavelet methods
Fourier Methods Fourier Integrals
Fourier Series
Discrete Fourier
Transforms
Wavelet
Methods
Wavelet
Series
Discrete Wavelet
Transforms
Continuous Wavelet
Transforms
The analogy between Fourier and wavelet methods is even more complete
(Table 7.2) when we take into account the continuous wavelet transform and
wavelet series expansions.
Discrete wavelet transforms map data from the time domain (the original or input
data vector) to the wavelet domain. The result is a vector of the same size. Wavelet
transforms are linear and they can be defined by matrices of dimension
if
they are applied to inputs of size . Depending on boundary conditions, such
matrices can be either orthogonal or ''close'' to orthogonal. When the matrix is
orthogonal, the corresponding transform is a rotation in
in which the data (a typle) is a point in
. The coordinates of the point in the rotated space comprise
the discrete wavelet transform of the original coordinates. Here we provide two toy
examples.
Example 5 Let the vector be
and let
be the point in
with
coordinates given by the data vector. The rotation of the coordinate axes by an
angle of
matrix is
can be interpreted as a DWT in the Haar wavelet basis. The rotation
and the discrete wavelet transform of
is
that the energy (squared distance of the point from the origin) is
preserved,
, since
Example 6 Let
is a rotation.
. The associated function
Fig. 7.10. The values
. Notice
is given in
are interpolated by a piecewise
constant function. We assume that belongs to Haar's multiresolution space
Figure 7.10: A function interpolating
on
The following matrix equation gives the connection between
coefficients (data in the wavelet domain).
The solution is
and the wavelet
Thus,
(7.45)
The solution is easy to verify. For example, when
Applying wavelet transforms by multiplying the input vector with an appropriate
orthogonal matrix is conceptually straightforward task, but of limited practical
value. Storing and manipulating the transformation matrices for long
inputs
may not even be feasible.
This obstacle is solved by the link of discrete wavelet transforms with fast filtering
algorithms from the field of signal and image processing.
7.4.1 The Cascade Algorithm
Mallat (1989a,b)[16,17] was the first to link wavelets, multiresolution analyses and
cascade algorithms in a formal way. Mallat's cascade algorithm gives
a constructive and efficient recipe for performing the discrete wavelet transform. It
relates the wavelet coefficients from different levels in the transform by filtering
with wavelet filter
and and its mirror counterpart
It is convenient to link the original data with the space
or
, where
, where
is often 0
is a dyadic size of data. Then, coarser smooth and
complementing detail spaces are
,
, etc. Decreasing the
index in -spaces is equivalent to coarsening the approximation to the data.
By a straightforward substitution of indices in the scaling equations (7.21) and
(7.35), one obtains
(7.46)
The relations in (7.46) are fundamental in developing the cascade algorithm.
In a multiresolution analysis,
Since
, any function
as
, where
to denote the coefficients associated with
respectively.
.
can be represented uniquely
and
and
. It is customary
by
and
Thus,
By using the general scaling equations (7.46), orthogonality of
and
for any
and , and additivity of inner products, we obtain
(7.47)
Similarly
The cascade algorithm works in the reverse direction as well. Coefficients in the
next finer scale corresponding to
corresponding to
and
can be obtained from the coefficients
. The relation
(7.48)
describes a single step in the reconstruction algorithm.
The discrete wavelet transform can be described in terms of operators. Let the
operators
and acting on a sequence
coordinate-wise relations:
and their adjoint operators
where
and
is wavelet filter and
, satisfy the following
satisfy:
its quadrature-mirror counterpart.
Denote the original signal by
. If the signal is of length
, then
can be interpolated by the function
from . In each step of
the wavelet transform, we move to the next coarser approximation (level)
by
applying the operator ,
. The ''detail information,'' lost by
approximating
by the ''averaged''
, is contained in vector
The discrete wavelet transform of a sequence
represented as
of length
.
can then be
(7.49)
Notice that the lengths of
decimation, the length of
and
and its transform in (7.49) coincide. Because of
is twice the length of
,
,
For an illustration of (7.49), see Fig. 7.11. By utilizing the operator notation, it is
possible to summarize the discrete wavelet transform (curtailed at level ) in
a single line:
The number
can be any arbitrary integer between
and
and it is associated
with the coarsest ''smooth'' space,
, up to which the transform was curtailed.
In terms of multiresolution spaces, (7.49) corresponds to the multiresolution
decomposition
contains a single element,
. When
the vector
Figure 7.11: Forward wavelet transform of depth
(DWT is a vector of coefficients
connected by double lines)
If the wavelet filter length exceeds , one needs to define actions of the filter
beyond the boundaries of the sequence to which the filter is applied. Different
policies are possible. The most common is a periodic extension of the original
signal.
The reconstruction formula is also simple in terms of operators
and . They
are applied on
and
, respectively, and the results are added. The
vector
is reconstructed as
(7.50)
Recursive application of (7.50) leads to
Figure 7.12: Inverse Transform
Example 7 Let
be an exemplary set we want to
transform by Haar's DWT. Let
, i.e., the coarsest approximation and
detail levels will contain a single point each. The decomposition algorithm applied
on
is given schematically in Fig. 7.13.
Figure 7.13: An illustration of a decomposition procedure
For the Haar wavelet, the operators
and
are given
by
Similarly,
.
.
Figure 7.14: An illustration of a reconstruction procedure
The reconstruction algorithm is given in Fig. 7.14. In the process of
reconstruction,
, and
first line in Fig. 7.14 recovers the object
Indeed,
and
. For instance, the
from
by applying
We already mentioned that when the length of the filter exceeds 2, boundary
problems occur since the convolution goes outside the range of data.
There are several approaches to resolving the boundary problem. The signal may
be continued in a periodic way (
), symmetric way
(
), padded by a constant, or extrapolated as
a polynomial. Wavelet transforms can be confined to an interval (in the sense of
Cohen, Daubechies and Vial (1993)[7] and periodic and symmetric extensions can
be viewed as special cases. Periodized wavelet transforms are also defined in
a simple way.
If the length of the data set is not a power of , but of the form
, for
odd
and
a positive integer, then only
steps in the decomposition algorithm can be
performed. For precise descriptions of conceptual and calculational hurdles caused
by boundaries and data sets whose lengths are not a power of 2, we direct the
reader to the monograph by Wickerhauser (1994)[26].
In this section we discussed the most basic wavelet transform. Various
generalizations include biorthogonal wavelets, multiwavelets, nonseparable
multidimensional wavelet transforms, complex wavelets, lazy wavelets, and many
more.
For various statistical applications of wavelets (nonparametric regression, density
estimation, time series, deconvolutions, etc.) we direct the reader to Antoniadis
(1997)[2], Hrdle et al. (1998)[15], Vidakovic (1999)[23]. An excellent monograph
by Walter and Shen (2000)[25] discusses statistical applications of wavelets and
various other orthogonal systems.
