\setcounter{equation}{0}\section{Orthogonal Compensation}

\newcommand{\bg}{\overline {\mbox{\bf g}}}
\newcommand{\bh}{\overline {\mbox{\bf h}}}
The QS transform can be summarized in the equations
\begin{equation}    \mbox{\bf y} = \mbox{\bf K} \bdx , \quad  \bdx = \mbox{\bf K}^{-1} \mbox{\bf y} .  \Label{qs}  \end{equation}
The odd and even components of $ \mbox{\bf y} $ form the pair
of vectors
\begin{equation}    \yo = [ y_{11},\, y_{12},\, \cdots  ]' , \quad  \yt = [ y_{21},\, y_{22},\, \cdots  ]' . \end{equation}
Let us denote the columns of the matrix $ \mbox{\bf K}^{-1} $ as
\begin{equation}     \left[ \begin{array}{cccccccccc}    \bg_1 &  \bh_1 &  \bg_2 &  \bh_2 &  \cdots   \end{array} \right ] . \end{equation}
Then the second equation in (\ref{qs}) has the equivalent form
\begin{equation}    \bdx = ( y_{11}\bg_1 + y_{12}\bg_2 +\cdots   ) +  ( y_{21}\bh_1 + y_{22}\bh_2 +\cdots   ) .  \Label{qs2}  \end{equation}
This equation suggests that the QS transform can be interpreted as
the decomposition of \bdx\ along the subspaces, $ G $ and
$ H $, spanned by 
translates of the dual basic $ \overline g $- and $ \overline h $-vectors
(with appropriate modifications at the boundary), respectively.  

In the analogous interpretation of the
Haar and $ D_4 $  transforms, the linear subspaces $ G $ and $ H $ are orthogonal
to each other.  In addition, the one-dimensional subspaces
generated by all the $ \bg_i $ and $ \bh_i $ are mutually
orthogonal.  When some of the components in $ \yt $ are 
discarded, the compressed vector is then the unique
signal, in the space spanned by the remaining base vectors,
that best approximates the original signal.

For the QS transform, $ G $ and $ H $ are not orthogonal.  Neither are
the one-dimensional subspaces generated by $ \bg_i $ and $ \bh_i $.
Hence, the compression step will not give the optimal
approximate signal, representable by the remaining 
base vectors.  This fact seems to argue against the use
of the QS transform.  In practice, a reasonable signal (one that
is not wildly oscillating or badly degraded by noise)
has such small coefficients in the $ H $ subspace decomposition that 
even if we do not take additional steps to optimize the
approximation, the error incurred in simply discarding
them is still smaller than
that incurred when using the $ D_4 $  transform.
In other words, a reasonable signal is very likely to be
closer to the $ G $ subspace associated with the QS than to the
$ G $ subspace associated with the $ D_4 $  transform.
This is supported by the numerical evidence given in the last
section.

We give below the method of orthogonal compensation to enhance
the approximation when discarding some of the components of
$ \yt $.  Let {\bf d} be the vector to be discarded.  It is
likely to be a partial sum of the expression in the
second pair of parentheses in (\ref{qs2}).  We decompose {\bf d}
into a linear combination of the vectors $ \bg_i $ and
an error vector that is orthogonal to $ G $.

\begin{equation}    \mbox{\bf d} = ( a_1\bg_1 + a_2\bg_2 +\cdots  ) + \mbox{\bf e}.  \Label{oc}  \end{equation}

After determining $ a_i $, they are added
to the corresponding $ y_{1i} $, so that the actual part that
is discarded is {\bf e}, which is orthogonal to~$ G $.
To this end, we take inner products of {\bf d} with each
of $ \bg_i $.  One can easily verify that $ a_i $ is the
solution to the tridiagonal system of linear equations
\begin{equation}     \left( \begin{array}{cccccccccc}    26 & 6 \\ 6 & 20 & 6 \\   & 6 & 20 & 6 \\   &   &   & \ddots  \\   &   &   &   &   & 6 & 26  \end{array} \right )  \left( \begin{array}{cccccccccc}    a_1 \\ a_2 \\ a_3 \\ \vdots \\ \vdots  \end{array} \right ) =  \left( \begin{array}{cccccccccc}    <\mbox{\bf d},\bg_1>  \\  <\mbox{\bf d},\bg_2>  \\ <\mbox{\bf d},\bg_3>  \\  \vdots \\  \vdots  \end{array} \right )  \end{equation}
for signals of even length.  For signals of odd length, the
corresponding tridiagonal matrix is just a bit more 
complicated --- the last two rows are now
\begin{equation}    \frac{1}{49}  \left[ \begin{array}{cccccccccc}    294  &  906  &  256  \\   &  256  &  640  \end{array} \right ] . \end{equation}

Tridiagonal systems can be solved by standard numerical linear
algebra method with no more than $ O(n) $ computational complexity.

