\setcounter{equation}{0}\section{Motivation -- the Haar and Daubechies $ D_4 $  Transforms}

Our goal is signal compression, and we look at two
well-known wavelet transforms in the light of this objective.
We permit lossy compression.  The conventional
strategy is to discard data that are small, because their
contribution to the perception of the signal is
not sufficiently significant, and to filter 
out high-frequency components of the signal, because the
human ear and eye are not very sensitive to highly
oscillatory signals.

In the method of transform coding, an invertible transform is first
applied to the signal to produce an alternative but
equivalent representation, before discarding small
data and{/}or data that correspond to high-frequency 
components.  A transform is well suited for compressing a given
class of signals if it produces
considerable near-zero data for 
most signals in the class in the equivalent representation.

\subsection{The Haar Transform}

We are given a finite discrete signal $ \bdx  $ 
of length $ 2n $.  More precisely, $ \bdx=[x_1,x_2,\cdots ,x_{2n}]' $
is a column vector
($'$  denotes matrix transpose).
We divide the vector into $ n $ ordered pairs of numbers, $ (x_1,x_2) $,
$ (x_3,x_4),\cdots ,(x_{2n-1},x_{2n}) $.  For each pair, we
generate a new pair consisting of their sum and difference,
for example, $ (y_1,y_2)=(x_1+x_2,x_1-x_2) $.  This is the $ 2\times 2 $ Haar
transform.

By keeping the new numbers
$ y_i $ instead of $ x_i $, no information
is lost, since each pair of $ x_i $ can be recovered from the 
corresponding pair of $ y_i $
by taking their sum and difference and then 
dividing by 2.  Suppose that the original signal 
is slowly varying, with an occasional jump 
here and there.  Then a majority of the $ y_i $, for $ i $ even, will 
be small.
The new representation {\bf y} is thus more apt for our
compression goal.

Since the odd and even components of {\bf y} are computed 
in different ways, it makes sense to rearrange them into
two smaller vectors $ \mbox{\bf y}_1=[\mbox{odd }y_i]' $
and $ \mbox{\bf y}_2=[\mbox{even }y_i]' $.  The components
of $ \mbox{\bf y}_2 $ are, one hopes,  mostly small; so after 
discarding those below some threshold value,
only a small portion remains.  
There is no need to further compress the survivors.

The components
of $ \mbox{\bf y}_1 $, on the other hand, are not necessarily
small.  In fact, it is a low-pass-filtered output that
retains the general shape of the original signal.  
This output carries
the correlation between points that are twice as far apart
in the original signal (two adjacent values in $ \mbox{\bf y}_1 $
represents four components in {\bf x}).
It is natural to iterate the Haar transform on $ \mbox{\bf y}_1 $
to gain further compression, ad infinitum.
The algorithm, consisting of a chain of transforms applied 
to the progressively shorter
low-pass-filtered signals, was formerly called a pyramidal 
scheme and recently was recast into the concept of the 
renowned {\sl multiresolution analysis}.
One of the attractive features of multiresolution analysis is the self-similarity
of the iterates.  Exactly the same procedure is used to
transform the principal component
signal at each level, albeit the 
signal vector becomes shorter every time.

The Haar transform has an obvious matrix formulation.  Let {\bf H} be
the $ 2n\times 2n $ block diagonal matrix

\begin{equation}    \mbox{\bf H} =  \left( \begin{array}{cccccccccc}    1 & 1 \\ 1 & -1 \\   &   & 1 & 1 \\   &   & 1 & -1 \\   &   &   &   & \ddots  \\   &   &   &   &   & 1 & 1 \\   &   &   &   &   & 1 & -1  \end{array} \right )  . \end{equation}

Then 
\begin{equation}    \mbox{\bf y} = \mbox{\bf Hx}   \Label{ht}  \end{equation}
and (for the inverse transform)
\begin{equation}    \mbox{\bf x} = \mbox{\bf H}\mbox{\bf y}/2  \end{equation}
The Haar matrix {\bf H} is not orthogonal,
but it can be easily converted
into one by dividing by $ \sqrt{2} $.  For computational purposes,
the current form of {\bf H} is preferable.

The Haar transform is easy to understand, but it lacks 
sophistication.  Nonconstant signals do not lead to 
zero $ \mbox{\bf y}_2 $.
The transform also does not have sufficient smoothness (this can
be adequately explained only by referring to the scaling 
function associated with the transform; see Section~7).  

\subsection{The Daubechies $ D_4 $ Transform}

Daubechies made a significant contribution when she
constructed higher-order orthogonal wavelets of 
compact support that
led to discrete wavelet transforms generalizing the 
classical Haar transform \cite{da}.
To fully understand the beauty of her wavelets and the
motivation for imposing certain properties requires
a fair amount of reading.  However, her wavelet transforms 
can still be appreciated and applied without delving too
much into the technical details of wavelet theory.  What follows is
our attempt
to explain her $ D_4 $  discrete transform succinctly.

\newpage
Daubechies has found two magic sets of
four numbers each:
\begin{equation}     \left[ \begin{array}{cccccccccc}    g_1,  & g_2,  & g_3,  & g_4  \end{array} \right ] = \frac{\sqrt{3}+1}{4\sqrt{2}}  \left[ \begin{array}{cccccccccc}    1, & \sqrt{3} , &  2\sqrt{3} - 3,  &  \sqrt{3} - 2  \end{array} \right ]  \end{equation}
and
\begin{equation}     \left[ \begin{array}{cccccccccc}    h_1,  & h_2,  & h_3,  & h_4  \end{array} \right ] = \frac{\sqrt{3}-1}{4\sqrt{2}}  \left[ \begin{array}{cccccccccc}    1, & \sqrt{3} , &  -3-2\sqrt{3} ,  &  2+\sqrt{3}   \end{array} \right ]  . \end{equation}
These numbers satisfy some remarkable yet easily verifiable
orthogonal properties, which can be stated in the following form.

Stack $ n $ copies of the sets of numbers to form the $ 2n\times 2n $ matrix

\begin{equation}    \mbox{\bf D} =  \left( \begin{array}{cccccccccc}    g_1  & g_2  & g_3  & g_4 \\   h_1  & h_2  & h_3  & h_4 \\   &   & g_1  & g_2  & g_3  & g_4 \\   &   & h_1  & h_2  & h_3  & h_4 \\   &   &   &   & \ddots  \\   &   &   &   &   & \ddots  \\   &   &   &   &   &   & g_1  & g_2  \\   &   &   &   &   &   & h_1  & h_2  \end{array} \right )  \Label{d} . \end{equation}
In the first two rows, the numbers are flushed to the left.  In subsequent
pairs of rows, the numbers are shifted successively
by two positions to the right.
Note that the last two rows can hold only the first two numbers of each
set.  Then
\begin{equation}    \mbox{\bf DD}' =  \left( \begin{array}{cccccccccc}    1 \\   & 1 \\   &   & 1 &   \\   &   &   & 1 \\   &   &   &   & \ddots  \\   &   &   &   &   & \times  & \times  \\   &   &   &   &   & \times  & \times   \end{array} \right )  , \end{equation}
which is almost the $ 2n\times 2n $ identity matrix (if not for the $ 2\times 2 $ submatrix
at the lower right-hand corner).

Analogous to the Haar transform (\ref{ht}) discussed in Subsection 2.1,
the Daubechies matrix
transforms a given signal \bdx\ into a new signal {\bf y}: 
\begin{equation}    \mbox{\bf y} = \mbox{\bf Dx} .  \Label{dt}  \end{equation}
The original signal (or at least the first $ 2n-2 $ components of)
\bdx\ can be recovered as
\begin{equation}    \mbox{\bf x} \doteq \mbox{\bf D}'\mbox{\bf y}, \end{equation}
where $ \doteq $ indicates that equality holds only for the
first $ 2n-2 $ components.

Many techniques have been devised to deal with the problem caused by 
the last two components
of the signal --- by using periodic or even extension,
zero padding, etc.  We present a new method in this paper.

Also analogous to the Haar transform, the odd components of {\bf y}
are a low-pass-filtered output which retains the general shape of 
\bdx, while the even components of {\bf y} are mostly very small.
Indeed, Daubechies has, in her search for 
the $ h_i $, imposed the 
condition that they will transform any linear function to zero (in the
language of wavelet theory, the wavelet has vanishing moments of orders
0 and 1).

The multiresolution analysis defined by $ D_4 $ is the algorithm consisting of
multiplying \bdx\ by the matrix {\bf D}, separating out the odd and
even components of the output to form two vectors 
$ \mbox{\bf y}_1 $ and $ \mbox{\bf y}_2 $, and then repeating the
process on $ \mbox{\bf y}_1 $.
Each level of transform can be easily reversed (if one ignores the problem
with the endpoints, for the time being) --- merge $ \mbox{\bf y}_1 $
and $ \mbox{\bf y}_2 $ into a longer vector by interlacing their
components and then multiply by $ D' $.

Although both the Haar transform and the Daubechies $ D_4 $  transform define
invertible multiresolution analysis, the latter is better for at
least two reasons.  It produces near-zero $ \mbox{\bf y}_2 $
for more signals, and its scaling function is continuous.
The Daubechies $ D_4 $  wavelet is still not perfect because it is
not symmetrical, not smooth (the graphs contain
an infinite number of sharp cusps), and not intuitive.  
Higher-order Daubechies wavelets have progressively better smoothness
properties.
