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.
Fourier Methods | Fourier Integrals | Fourier Series | Discrete Fourier Transforms |
Wavelet Methods | Continuous Wavelet Transforms | Wavelet Series | Discrete 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.
![]() |
The following matrix equation gives the connection between
and the wavelet coefficients (data in the wavelet
domain).
![]() |
The solution is
![]() |
Thus,
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.
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 , where
is often 0 or
, where
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
In a multiresolution analysis,
. Since
, any function
can be represented uniquely as
, where
and
. It is customary to denote the coefficients
associated with
and
by
and
, respectively.
Thus,
![]() |
![]() |
|
![]() |
||
![]() |
Similarly
.
The cascade algorithm works in the reverse direction as well.
Coefficients in the next finer scale corresponding to can be
obtained from the coefficients corresponding to
and
. The relation
The discrete wavelet transform can be described in terms of operators.
Let the operators
and
acting on a sequence
, satisfy the following coordinate-wise relations:
![]() |
![]() |
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
of length
can then be represented as
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:
![]() |
![]() |
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
Recursive application of (7.50) leads to
![]() |
||
![]() |
||
![]() |
For the Haar wavelet, the operators
and
are given by
. Similarly,
.
The reconstruction algorithm is given in Fig. 7.14. In the
process of reconstruction,
,
and
. For instance, the
first line in Fig. 7.14 recovers the object
from
by applying
. Indeed,
and
.
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], Härdle 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.
The following two matlab m-files implement discrete wavelet
transform and its inverse, with periodic handling of boundaries. The
data needs to be of dyadic size (power of ). The programs are
didactic, rather than efficient. For an excellent and comprehensive
wavelet package, we direct the reader to wavelab802 module
(http://www-stat.stanford.edu/~ wavelab/) maintained by Donoho and
his coauthors.
function dwtr = dwtr(data, L, filterh) % function dwtr = dwt(data, filterh, L); % Calculates the DWT of periodic data set % with scaling filter filterh and L scales. % % Example of Use: % data = [1 0 -3 2 1 0 1 2]; filter = [sqrt(2)/2 sqrt(2)/2]; % wt = DWTR(data, 3, filter) %------------------------------------------------------------------ n = length(filterh); %Length of wavelet filter C = data; %Data \qut{live} in V_J dwtr = []; %At the beginning dwtr empty H = fliplr(filterh); %Flip because of convolution G = filterh; %Make quadrature mirror G(1:2:n) = -G(1:2:n); % counterpart for j = 1:L %Start cascade nn = length(C); %Length needed to C = [C(mod((-(n-1):-1),nn)+1) C]; % make periodic D = conv(C,G); %Convolve, D = D([n:2:(n+nn-2)]+1); % keep periodic, decimate C = conv(C,H); %Convolve, C = C([n:2:(n+nn-2)]+1); % keep periodic, decimate dwtr = [D,dwtr]; %Add detail level to dwtr end; %Back to cascade or end dwtr = [C, dwtr]; %Add the last \qut{smooth} part
function data = idwtr(wtr, L, filterh) % function data = idwt(wtr, L, filterh); % Calculates the IDWT of wavelet % transform wtr using wavelet filter % \qut{filterh} and L scales. % Example: %>> max(abs(data - IDWTR(DWTR(data,3,filter), 3,filter))) %ans = 4.4409e-016 %---------------------------------------------------------------- nn = length(wtr); n = length(filterh); %Lengths if nargin==2, L = round(log2(nn)); end; %Depth of transform H = filterh; %Wavelet H filter G = fliplr(H); G(2:2:n) = -G(2:2:n); %Wavelet G filter LL = nn/(2^L); %Number of scaling coeffs C = wtr(1:LL); %Scaling coeffs for j = 1:L %Cascade algorithm w = mod(0:n/2-1,LL)+1; %Make periodic D = wtr(LL+1:2*LL); %Wavelet coeffs Cu(1:2:2*LL+n) = [C C(1,w)]; %Upsample & keep periodic Du(1:2:2*LL+n) = [D D(1,w)]; %Upsample & keep periodic C = conv(Cu,H) + conv(Du,G); %Convolve & add C = C([n:n+2*LL-1]-1); %Periodic part LL = 2*LL; %Double the size of level end; data = C; %The inverse DWT