\setcounter{equation}{0}\section{$W$-Matrices and Some New Transforms}

In the preceding section, we noted that the 
crucial element in the multiresolution algorithm is a suitable
transform ``matrix'' such as {\bf H} or~{\bf D}.  
This ``matrix'' is really a family of matrices of 
sizes $ 2n\times 2n $ (for all positive integers $ n) $, all having the
same structure.  Three properties are essential for
constructing the multiresolution analysis algorithm.
\begin{enumerate}
\item With the exception of two rows (more 
rows may be needed for higher order transforms)
at the top or bottom of the matrix,
the other rows come in pairs (let us call them the $ g $- 
and $ h $-vectors).  Each pair is obtained from the
previous pair by a shift of two positions to the right. 
\item Each row has only a small number of nonzero elements.  
\item Each matrix is near-orthogonal, in the sense that the product
of each matrix with its transpose is almost identical to the 
identity matrix.
\end{enumerate}

\LEFTLINE Two additional properties are desirable for compression and
other purposes.  
\begin{itemize}
\item The $ g $-vector is associated
with a sufficiently smooth scaling function.
\item The $ h $-vector
has vanishing moments up to some high order.
\end{itemize}

How important is the near-orthogonality of the matrix?
Our work is based on a relaxation of this requirement.
Orthogonality makes it easy to find the
inverse of the transform --- simply multiply {\bf y} by the
transpose of the matrix.  We can, however, achieve the same goal
by requiring that the
inverse of the matrix is easy to find and that it
has a small number of nonzero
elements (so that the 
inverse transform can be efficiently implemented).

We define a $W$-matrix as one for which both it and its inverse
satisfy conditions 1 and 2.  The first question that comes to 
mind is: Are there any simple $W$-matrices besides the orthogonal
ones?  Examples are given below.

A more subtle point concerning orthogonality is the
``stability'' of the inverse transform.  With nonorthogonal
matrices,  small data in the transformed output may not correspond
to small input data if the transform matrix has a large
condition number.  The $W$-matrices of our example do have a reasonable condition number.

\subsection{The Quadratic Spline $W$-matrices}

We call our first example of $W$-matrix the quadratic spline $W$-matrix
because, as we will see in Section~7, its associated 
scaling function is the well-known quadratic B-spline.

The $W$-matrices of even order in the family have the form
\begin{equation}    \mbox{\bf K} =  \left( \begin{array}{rrrrrrrrrr}    2 &  3  & -1  \\   2  & -3  & 1  \\   & -1  & 3  & 3  & -1 \\   & -1  & 3  & -3  & 1 \\   &   &   &   & \ddots  \\   &   &   &   &   & -1  & 3  & 3  & -1  \\   &   &   &   &   & -1  & 3  & -3  & 1 \\   &   &   &   &   &   &   & -1  & 3  & 2  \\   &   &   &   &   &   &   & -1  & 3  & -2  \end{array} \right ) . \Label{k}   \end{equation}

\LEFTLINE The building blocks are the $ g $- and $ h $-vectors
$  [ -1, 3, 3, -1 ] $ and $ [ -1, 3, -3, 1 ] $.

The top two rows and bottom two rows
are obtained from the basic vectors by adding the
number(s) that has (have) been cut off to the nearest neighborhood
that is retained. 
The inverse of {\bf K} is 

\begin{equation}    \mbox{\bf K}^{-1} = \frac{1}{16}  \left( \begin{array}{rrrrrrrrrr}    4 &  4  \\   3  & -3  & 1 & 1 \\ 1  & -1  & 3  & 3  \\ & & 3  & -3  & 1  & 1 \\ & &  1  & -1  & 3 &3 \\  & &   &   &   & \ddots  \\   &   &   &   &   & 3  & -3  & 1  & 1  \\   &   &   &   &   & 1  & -1  & 3  & 3 \\   &   &   &   &   & & & 4 & -4 \end{array} \right )  . \Label{ik} \end{equation}


Table 1 gives a simple example of a two-level 
decomposition.
The first column is the input signal.  The second and
third columns are the first-level transformed signals
using the matrix {\bf K} in (\ref{k}).  The last two columns are the
second-level transformed signals using the odd-sized
matrix {\bf K} given by (\ref{ko}) in the next subsection.

\begin{center}
\begin{minipage}{5in}
Table 1.  Two-level multiresolution analysis of \bdx\ using the quadratic spline transform
\end{minipage}
\end{center}
\begin{center}
\tabcolsep=20pt
\begin{tabular}{|r|r|r||r|r|}
\hline
$ \bdx  $ &  $ \mbox{\bf y} $  & $ \mbox{\bf y}_1,\mbox{\bf y}_2 $ &  $ \mbox{\bf y} $  & $ \mbox{\bf y}_1,\mbox{\bf y}_2 $  \\
\hline  1 & -1    & -1    & -198  & -198 \\
        8 &   5   &  140  & 194   & 2893 \\
       27 & 140   &  616  & 2893  & 16755 \\
\cline{5-5} 64 &   6   &  1620 &  523  & 194   \\
      125 & 616   &  3675 & 16755 & 523   \\
\cline{3-5} 216   &   6   &   -1  & & \\
      343 & 1620  &     6  & & \\
      512 &   6   &     6  & & \\
      729 & 3675  &     6  & & \\
     1000 & -325  &  -325  & & \\ \hline
\end{tabular}
\end{center}

This algorithm is very easy to implement.  We will see in the
next section that this example is only a special case of a general
class of $W$-matrices --- {\it given any set of four numbers 
$ [h_1,h_2,h_3,h_4] $ with $ h_1h_4\neq h_2h_3 $, one can supplement
it with an $ g $-vector to form a $W$-matrix}.  Our Matlab implementation 
encompasses the general $W$-matrix transform.  

The quadratic spline $W$-matrix given in this subsection is particularly good for 
compression because its $ h $-vector
has vanishing moments up to order two.  
Furthermore, the exact inverse of {\bf K} is used in the 
restoration step; hence, the endpoints of the signal \bdx\ will be 
recovered exactly, without any need to extend \bdx\ 
either periodically or with zero padding.  This 
strategy avoids the
possible introduction of an artificial discontinuity.

Although the inverse matrix $ \mbox{\bf K}^{-1} $ has a structure
similar to that of {\bf K,} it is more appropriate to think of 
$ \mbox{\bf K}^{-1} $ as being built by columns instead of rows.
The building blocks of $ \mbox{\bf K}^{-1} $ are thus the
$ \overline g $-vector and $ \overline h $-vector
\begin{equation}    [ 1, 3, 3, 1 ] \quad   \mbox{ and }  \quad  [ 1, 3, -3, -1 ] . \end{equation}
They are dual to the $ g $- and $ h $-vectors of {\bf K}, respectively.
The columns of the matrix come in pairs, made up of
the transpose of
the above two basic vectors; successive 
pairs of columns are shifted
two positions downwards.

\subsection{Odd-sized $W$-Matrices }

Classical discrete wavelet transforms require the length of the
input signal to be
an even number.  As a consequence, the length of signals that can have 
$ J $ levels of multiresolution analysis must have a factor of $ 2^J $. 
Our approach to treat signals of odd length is to transform
them with a $W$-matrix of odd size.  For the family of quadratic 
spline $W$-matrices, we let (there is more than one possible choice)
the odd-sized matrices be

\begin{equation}    \mbox{\bf K} =  \left( \begin{array}{rrrrrrrrrr}    2 &  3  & -1  \\   2  & -3  & 1  \\   & -1  & 3  & 3  & -1 \\   & -1  & 3  & -3  & 1 \\   &   &   &   & \ddots  \\   &   &   &   &   & -1  & 3  & 3  & -1  \\   &   &   &   &   & -1  & 3  & -3  & 1 \\   &   &   &   &   &   &   & -1  & 5  \end{array} \right ) . \Label{ko}   \end{equation}
Its inverse can be obtained from (\ref{ik}) by first deleting
the last row and last column and then replacing the lower
right $ 2\times 3 $ submatrix by
\begin{equation}    \frac{1}{28}    \left[ \begin{array}{cccccccccc}    5 & -5 & 2 \\ 1 & -1 & 6  \end{array} \right ] \end{equation}


The transformed signal $ \mbox{\bf y}=\mbox{\bf Kx} $ has the
same length as \bdx. After separating the odd and even
components, the vector $ \mbox{\bf y}_1 $ has one component
more than the vector $ \mbox{\bf y}_2 $.  Since the total number
of components of the output signal is always the same
as the length of \bdx, the latter can be restored without
additional information (other than the number of multiresolution analysis levels
applied).

See Taswell \cite{ta} for a different technique in dealing with
signals of odd length.  Our method is more efficient because
the transformed signal does not increase in length and
there is no need to use an additional bookkeeping vector.

\subsection{Other Examples of $W$-Matrices }

Note that each row of {\bf K} has at most four nonzero elements.
We say that
{\bf K} is of order 4.  The Daubechies and Haar transforms have order~4
and~2, respectively.  $W$-matrices of a higher order lead to 
computationally more extensive multiresolution analyses.
One can obtain smoother transforms,
however, using suitable choices of
$ g $- and $ h $-vectors.

The order 6 generalization of the quadratic spline $W$-matrix is built from the
vectors
\begin{equation}     \left[ \begin{array}{cccccccccc}    1, &  -5, &  \frac{20}{3} , &  \frac{20}{3} , &  -5, &  1  \end{array} \right ] , \end{equation}
and
\begin{equation}     \left[ \begin{array}{cccccccccc}    -1, &  5, &  -10 , &  10 , &  -5, &  1  \end{array} \right ] . \end{equation}
For even-sized matrices, the first and last two rows of the matrix 
have only four nonzero elements.  For odd-sized matrices, the last
three rows have to be modified.  For each of these rows,
the numbers that are cut off are added to the next surviving number.

The inverse matrix is built (by columns) by using the dual vectors
\begin{equation}     \left[ \begin{array}{cccccccccc}    1, &  5, &  10 , &  10 , &  5, &  1  \end{array} \right ] \mbox{ and }  \left[ \begin{array}{cccccccccc}    1, &  -5, &  \frac{20}{3} , &  -\frac{20}{3} , &  5, &  -1  \end{array} \right ] . \end{equation}
The exact form of $ \mbox{\bf K}^{-1} $ can be found by using
either Matlab or Maple.

$W$-matrices of odd orders also exist.  For example, the 
analogous spline matrix of order 3 is
generated by the basic vectors
\begin{equation}     \left[ \begin{array}{cccccccccc}    -1, &  2, &  1  \end{array} \right ]  \mbox{ and }  \left[ \begin{array}{cccccccccc}    -1, &  2, &  -1  \end{array} \right ]  \end{equation}
(note that one of them is not symmetric)
and the inverse by the dual vectors
\begin{equation}     \left[ \begin{array}{cccccccccc}    1, &  2, &  1  \end{array} \right ] \mbox{ and }  \left[ \begin{array}{cccccccccc}    -1, &  -2, &  -1  \end{array} \right ] . \end{equation}

Generalized $W$-matrices can be easily constructed with
a set of more than two basic vectors, or
with more than one set of basic vectors.
Examples are given in the full paper.
