\documentstyle {amsppt}
%\documentstyle {lhamsppt}
\pagewidth {6.5in}
\pageheight {9in}
\magnification1200
\TagsOnRight
\define\Lt {\Bbb L^2 (\Bbb R)}
\define\z {\Bbb Z}
\define\R {\Bbb R}
\define\vf {\varphi}
\define\sign {\text {sign\,}}
\define\dfn {\,\overset\text {def} \to=\,}
\topmatter
\title
Biorthogonal wavelet bases   with rational masks
and their application\footnotemark
\endtitle
\rightheadtext {Biorthogonal wavelet bases  with rational masks}
\author
A.P.Petukhov \endauthor
\email petukhov\@pdmi.ras.ru \endemail \abstract
General principles of a construction of biorthogonal wavelet bases,
associated with recursive filters, are considered.
Fast algorithms of expansion
of functions in these bases, including, algorithms, which are based on
factorizations of polyphase matrices, are presented. Results of numerical
simulation of image compression algorithms, based on
expansion of images in the offered basis, are given. They 
allow to make a conclusion about high effectiveness of the
offered algorithms 
from a point of view of computational complexity as well as
from a point of view of value of the compression factors.
\endabstract
\endtopmatter
\document
\footnotetext{Supported by  Russian Foundation for Basic Researches
under grant \# 97-01-00443}
\head
\S 1. Introduction.
\endhead
For last 10 years wavelet  bases  became a powerful tool  for many
theoretical problems of analysis and for applied problems, relating to
signal processing. The theory of wavelet bases, connected to the bases
whose functions have compact support, had
the greatest development.
The algorithms of expansion of functions in
such bases are realized as a collection of discrete convolutions
with numerical sequences, which has only
finite number of non-zero coefficients. In a radio 
engineering
linear
operators,
acting on infinite sequences and commutative with a shift
(i.e., the operators of a convolution), is called {\it (digital) filters}.
A sequence of numbers, which forms the convolution kernel is called
{\it impulse response} of a filter.
Thus, the expansion in wavelet bases   with compact support
is realized with
the aid of filters those have finite impulse response (FIR-filters).
Fourier transform of impulse response
of a filter is called 
{a frequency characteristic}.
Hence, the frequency characteristic of a filter with finite impulse response
is a trigonometric polynomial. In many divisions of  mathematics, for
example in the theory approximation,  rational functions are
more flexible and effective tool than polynomials.
Here we consider wavelet bases, such that expansion in them
is realized with
filters with a rational frequency characteristic. Certainly,
appearing new types of wavelet bases   gives new possibilities
for
applied problems of  signal and image processing.
\par
Despite the fact, that this types of filters
has infinite impulse response
(IIR-filters), there is  effective numerical realization
in the form of  a composition of
well known in a radio engineering, so-called, recursive filters.
Moreover, the computional complexity
for  realization of filters with a rational
frequency characteristic are proportional to a sum of degrees
of the numerator and the denominator, that is comparable
to complexity of a realization of
expansions in bases with compact supports,
which are proportional to degrees of
the appropriate polynomials.
\par
For the first time the similar bases were investigated systematic  in
the paper of C.Herley and
M.Vetterly [1], where the case
when the corresponding bases are
orthogonal and  form the multiresolution analysis (MRA) of the space $\Lt$
was considered.
As it is well-known (see [4]),
except for the Haar bases, there do not exist 
orthogonal bases of compactly supported wavelets, the functions of which
are even or odd with an accuracy to a shift of argument.
However, for bases, generated by recursive IIR-filters, it does not  so.
In [1] even and odd bases, associated with recursive filters, were
constructed.
Orthogonality of bases allows to receive results,
which guarantees convergence and
a stability of expansion algorithms with considerably smaller efforts,
than in the cases , when the orthogonality is lacking.
However, to use an orthogonality it is
necessary, at least, to have a scalar product in an investigated  space.
But even if
the scalar product is introduced, for an effective uze of orthogonal bases
in applied problems it is required,
that the Euclidean distance should be
natural for the given problem.
Unfortunately, not always it is  so. In
particular, in  image processing
biorthogonal pairs of bases are
more effective than 
orthogonal wavelet bases. For example,
for image compression, so-called, 9/7-wavelets with compact
supports, constructed in  [2], are most frequently used.
As for the bases from [1], which combines an orthogonality and symmetry, in
view of severe constraints their adaptation to a concrete problem
is rather problematic.
Outcomes of numerical simulation of
image compression algorithms  with use of such bases have shown, that
their effectiveness is rather law
at least for small  degree of recursive filters.
On the contrary, the tool of biorthogonal pairs of bases,
generated by recursive filters, signicantly exceeds in flexibility
the tool of biorthogonal pairs of
bases with compact support.
\par
About a possibility of a construction
of biorthogonal pairs of filter banks with a
rational frequency characteristic it is written, for example,
in the book by G.Strang and T.Nguyen [7].
There a few examples of such bases were obtained as a collateral yield
in a construction of "good" bases with compact support.
Here we build just the biorthogonal theory of bases, associated with
recursive filters. As we shall see, the use of such approach leads
to essential economy of computing expenditures in
some problems.
\par
Primarily the theory of  wavelet bases 
was developed independently of the theory  of subband coding
which arose a little bit earlier in a radio engineering . However,
soon  their almost complete identity has become clear.
In any case, it may be stated for most practically important cases.
In \S 2 we  stop on their connection.
Unfortunately, in a general case a question when a pair of filters,
defining algorithm of subband coding, generates a pair of biorthogonal bases,
remains open until now.
At the moment this problem for the  biorthogonal case,  
when the
bases associated with subband coding belong to $\Lt$
and have the compact support,
was investigated the most completely in the works [2], [5],
Therefore in \S 3 we  temporarily disregard a problem on the
correspondence with bases of wavelets and, remaining on a platform of subband
coding, we shall construct  biorthogonal pairs of filters with
a rational frequency characteristic.
\par
In \S 4 algorithm of subband coding and reconstruction of
signals, based on, so-called, lifting scheme, is constructed for IIR
filters.
This scheme  for FIR filters (see [3], [6]),
gives asymptotically double gain in
computational complexity as  compared with a direct realization
of convolution algorithms of subband coding.
\par
In \S 5 the computational complexity of the proposed
algorithms is calculated
and comparison with the computational cost
of a direct realization of algorithms of wavelet expansion  
is given.
\par
In \S 6 we give results of numerical
simulation of image compression algorithms, which allows  to
compare
effectiveness of the new algorithms  with the known ones in respect to
compression factor as well as with respect to
computational cost. Besides, we give arguments, which show 
that the filters, used in the simulation, associate with some pairs of biorthogonal
wavelet bases  of the space $\Lt$.
% *******************
\head
\S 2. The multiresolution analysis of quasi-Banach spaces of distributions.
\endhead
% *******************
First we  extend the definition of the Multiresolution analysis to
quasi-Banach space differing from $\Lt$. We  recall, that
quasi-Banach spaces are generated by a quasi-norm, i.e.,
functional, whose
difference from a norm consists in the fact that
an triangle inequality for it
is valid only in the form
$\ | f + g\ | \le C (\ | f\ | + \ | g\ |) $, where $C > 1$. Such
relaxation of norm properties allows to include in general consideration
many useful spaces such as the Hardy spaces. The complete construction
of the theory of 
Multiresolution for spaces of periodic distributions can be found in
our paper [8] (see also [9], [11]), the case of periodic wavelets
on a discrete grid is considered in [10]. The given below
definitions of wavelets in
quasi-Banach spaces of non-periodic distributions in no way are  the
complete theory. It is only a sketch of the possible scheme of 
construction of the wavelet theory, which  is necessary  here to us only to
show a place of those special bases, construction of which we deal with.
\par
We  denote by $S^\prime$ and $S$ respectively the space of tempered
distributions
and the space of trial functions
\par
\definition {Definition 1}
Collection of closed linear subspaces $\{V^j\}_{j\in\z} $
of quasi-Banach spaces
$X$, $S\subset X\subset S^\prime$ is called    {\it  the
Multiresolution analysis} (MRA) of the space $X$, if it satisfies
the following conditions:
\par
a) $\dots\subset V^ {-2} \subset V^ {-1} \subset V^0\subset V^1\subset \dots$;
\par
b) $\overline {\cup V^j} =X$; %, $\cap \overline {V^j} $ %содержит of a constant or $\delta$-функцию; \par
c) $f (x) \in V^j\Leftrightarrow f (2x) \in V^ {j + 1} $;
\par
d) there is distribution $\varphi\in V^0$, called {\it a scaling
function}, such that the linear span of a system  $\varphi
(\bullet - k) $, $k\in\z$, is dense in $V^0$.
\enddefinition
% *****************
%\definition {the Definition 2}
%Набор of closed linear subspaces $\ {V^j\} _{j\in\z} $
%квазибанахова of space
%$X$, $S\subset X\subset S^\prime$ %называется a MRA of space
%$X$, if closures of these linear spaces in topology
%пространства $S^\prime$ will form a MRA of space $S^\prime$.
%\enddefinition
\par
According to  item b) of  Definition 1 function $\varphi (x) $ can be
approximated by linear combinations of functions $\{\varphi (2x-k) \} $.
We are
interested in only a case, when
MRA is formed by real spaces and {\it scaling equation} 
$$
\varphi (x) =\sqrt2\sum_ {n\in\z} h_n \varphi (2x-n),\tag 2.1
$$
where $h_n$ are  Fourier coefficients of a rational function
$$
\sqrt2m_0 (\omega) =\frac {{\Cal P} (e^ {i\omega})} {{\Cal Q} (e^ {i\omega})} =
\sum_ {n\in\z} h_ne^ {-in\omega},\tag {2.2}
$$
takes place.
It is clear, that  $h_n$ is a real sequence.
The functions ${\Cal P} (z) $ and $ {\Cal Q} (z) $ in (2.2)
are Laurent polynomials.
We note
that we use a traditional factor
$\sqrt2$, since if the functions $\{\varphi (x-n) \} $  form an orthonormal
basis of the space $V^0\in \Lt$,
the functions $\{\sqrt2\varphi (2x-n) \} $ constitute
orthonormal basis of $V^1$.  After application Fourier transform
to (2.1)
this relation can be rewritten in the form
$$ \hat\varphi (\omega) =m_0\left (\frac\omega2\right) \hat\varphi \left
(\frac\omega2\right).
\tag {2.3}
$$
If we assume, that $\hat\varphi$ is a continuous function
and $\hat\varphi(0) \ne0$, it is clear that $m_0 (0) =1$.
Thus, applying (2.3) and assuming that $\hat\varphi (0) = (2\pi) ^ {-1/2}$,
it can be proved, that
$$
\hat\varphi (\omega) = (2\pi) ^ {-1/2} \prod_ {k=1} ^\infty m_0 \left
(\frac\omega {2^k} \right),
$$
where the product in the right side converges  uniformly on compact sets.
\par
Let $\{V^j\} $ be  MRA of a quasi-Banach space $X$. We  denote by
$Z^\circ$ the completion of the space $S$ with respect to a quasi-norm
of the space $Z$.
In what follows we assume $X=X^\circ$. To introduce the concept of
wavelet  decomposition of a space $X$ we need MRA 
$\{\tilde V^j\} $ of the dual space $Y=X^ {* \circ} $.
Under this assumption the spaces
$$
W^j=\{f\in V^ {j + 1} | \langle f, g\rangle=0, \text{ for any } g\in \tilde
V^j\}
$$
are called wavelet spaces. In analogous way the dual 
wavelet spaces
$$
\tilde W^j=\{g\in \tilde V^ {j + 1} | \langle f, g\rangle=0, \text{ for any }
f\in V^j\}
$$
are defined.
Here we do not  discuss any additional conditions
for the correct definition of  wavelet spaces.
However, we  mark that the MRA $\{\tilde V^j\} $ of the dual
space should be chosen so that $V^j\cap W^j= {0} $. Then we have
$$
V^ {j + 1} =
W^j\oplus V^j=\left (\bigoplus_ {i=0} ^k W^ {j-i} \right) \bigoplus V^ {j-k} =
\left (\bigoplus_ {i=0} ^ {+ \infty} W^ {j-i} \right) \bigoplus\left (\bigcap_
{i\in\z} V^ {i} \right),
$$
where the symbol $\oplus$ means a direct sum of spaces.
The component of
intersection of spaces $V^i$ in the last formula could not appear
in the  case of 
MRA of  $\Lt$, because  such intersection is always empty for $\Lt$.
As for a general case it is not. Easily to construct examples of MRA which
have in intersection either polynomials  of a fixed degree or Dirac's
$\delta$-function
or its generalized derivatives.
\par
Let us comment this construction.
On the one hand, it is clear, that the classical definition  MRA of
the  space
$\Lt$ requires generalization on other function space, in which scalar product
is not defined. However, on the first sight it seems  that  Definition 1
envelop too wide class of spaces and for applications it is
possible to be limited by classical function spaces, not passing to
distributions.
It would be possible to agree with it, if
the spaces $V^j$ were used only as approximations of the space $X$. However,
in the
definition of wavelet spaces  two MRAs of mutually dual spaces participate.
One of them serves for an approximation, and the second one does
for the definition of a projection.
And since, the narrower the initial space, the wider  the dual space, then
one may occur that it is not enough functionals, determined by usual
functions, for the determination of a projection to a space
of smooth functions.
For
example, at the definition of interpolational wavelets, the examples of which
will be given below, the projectors are set by shifts
of the Dirac $\delta$-function which is the most simple example
of a distribution.
This example is a quite natural corollary that a dual space for the space of
continuous functions is the space of finite Borel measures.
We note, that
the space of finite Borel measures is not separable.
Therefore, if $X=\Bbb C
(\Bbb R) $ is the space of continuous functions, vanishing at  infinity, the
space of finite Borel measures $\Bbb C^ * (\Bbb R) $ does not coincide with
$\Bbb C^ {* \circ} (\Bbb R) $. However,
if we take little narrower space (for example, determined by
any module of a continuity) as above $X$,
we obtain that the space of Borel measures is a separable
subspace of the space $X^ * $.
\par
We  recall, that two  function collections $\{f_n\} \subset X$ and
$\{g_n\} \subset X^* $ is defined to be biorthogonal, if relations
$$
\langle f_k, g_m\rangle=\cases 1,\quad &k=m,\\ 0, &k\ne m. \endcases $$
hold.
Let us assume, there  is  a basis $\{\tilde\varphi (x-n) \}$ of the space $\tilde V^0$
biorthogonal to the basis
$\{\varphi (x-n) \}$, which is
generated by a rational function
$$
\tilde m_0 (\omega) = \frac {1} {\sqrt2} \frac {\tilde {\Cal P} (e^ {i\omega})}
{\tilde {\Cal Q} (e^ {i\omega})} = \frac1 {\sqrt2} \sum_ {n\in\z} \tilde h_ne^
{-in\omega}. %\label {2.4},
$$
In view of a condition of a biorthogonality easily to obtain, that $m_0$ and
$\tilde m_0$  satisfies the condition
$$
m_0 (\omega) \overline {\tilde m_0 (\omega)} + m_0 (\omega + \pi) \overline
{\tilde m_0 (\omega + \pi)} =1. %\label {5}
$$
We note since the convergence of infinite products, determining
functions $\hat\varphi$ and $\hat {\tilde\varphi} $, implies
equalities $m (0)=\tilde m (0) =1$,
we obtain, that from  a biorthogonolity  condition 
we have $m (\pi) \overline {\tilde m (\pi)} =0$. It means, that at least
one of the factors $m (\pi) $ and $\tilde m (\pi) $ is equal to zero.
\par
From the definition $W^j$ we  obtain, that Fourier transform  of
function $\psi$, generating basis $\{\psi (x-n) \} $ of the space $W^0$,
can be calculated by the formula
$$ \hat\psi (\omega) =m_1 (\frac\omega2) \hat\varphi (\frac\omega2),%\label{6}
$$
where $m_1$ satisfies the equation
$$
m_1 (\omega) \overline {\tilde m_0 (\omega)} + m_1 (\omega + \pi) \overline
{\tilde m_0 (\omega + \pi)} =0. %\label {7}
$$
It follows from here
$$ m_1 (\omega) =\alpha (\omega) e^ {-i\omega} \overline {\tilde m_0 (\omega +
\pi)},
$$
where $\alpha$ is some $\pi$-periodic distribution.
In what follows, 
following traditions in notation rather  than  a matter of fact,  for
a definitness we suppose $\alpha (\omega) \equiv 1$.
In analogous way we introduce a function
$$
\tilde m_1 (\omega) =e^ {-i\omega} \overline {m_0 (\omega + \pi)},
$$
which generates a basis in the dual wavelet space  $\tilde W^0$.
Thus, the matrix relation
$$
\left (\matrix
m_0 (\omega) &m_0 (\omega + \pi) \\
m_1 (\omega) &m_1 (\omega + \pi) \endmatrix
\right)
\cdot
\left (
\matrix
\tilde m_0 (\omega) &\tilde m_0 (\omega + \pi) \\ \tilde m_1 (\omega)
&\tilde m_1 (\omega + \pi) \endmatrix
\right) ^ *
=
I,\tag {2.4}
$$
where
$I=
\left (
\matrix
1 &0\\
0  &1 \endmatrix
\right)
$, holds.
\par
Thus, the equation (2.4) gives a necessary condition for the functions $m_0$
and $\tilde m_0$ to generate continuous scaling functions
$\varphi$, $\tilde\varphi$, which determine a pair of  dual MRA.
As for
sufficient conditions, at the moment this problem is far from a complete
solution, though in most practically important cases  it is
possible to show, that the concrete solution of the equation (2.4)
really 
generates a biorthogonal pair of bases of certain dual MRA.
\par
In case of  multiplying of the function $m_1 (\omega) $ by
$\pi$-periodic
function $\alpha (\omega) $ the equality (2.4)  is broken.
For its restoration the function $\tilde m_1 (\omega) $ should be multiplied
by
$1/\overline {\alpha (\omega)} $, by receiving, thus,
$$
\left (\matrix
m_0 (\omega) &m_0 (\omega + \pi) \\ m_1 (\omega) \alpha (\omega) &m_1 (\omega +
\pi) \alpha (\omega) \endmatrix
\right)
\cdot
\left (
\matrix
\tilde m_0 (\omega) &\tilde m_0 (\omega + \pi) \\ \tilde m_1 (\omega)
/\overline {\alpha (\omega)}  &\tilde m_1 (\omega + \pi) /\overline {\alpha
(\omega)} \endmatrix
\right) ^ *
=
I.\tag {$2.4^\prime$}
$$
Certainly, the choice of $\alpha (\omega) $ does not influence either a pair
of dual MRA,
which are determined by functions $m_0$, $\tilde m_0$,
or on a choice of
bases in the appropriate spaces $V^j$ and $\tilde V^j$
or on a choice of wavelet spaces
$W^j$ and $\tilde W^j$. However,  variating the function $\alpha$
gives an additional degree of freedom at a choice of  wavelet bases to correspond
in the
greatest degree  to a concrete applied problem.
In what follows we shall see,
that the basis, the most appropriate for image compression,
uses this degree of freedom.
The reason why this method was unclaimed
in the current literature has an objective character. The fact is, that
considering biorthogonal wavelet bases, associated with FIR-filters, we are
forced to search polynomial for solutions of the equation (2.4). If $m_0$ and
$\tilde m_0$ are polynomials, the traditional choice of functions $m_1$ and
$\tilde m_1$ is also polynomial.
If we shall multiply function $m_1$ by a $\pi$-periodic polynomial
$\alpha$, we are obliged to divide $\tilde m_1$ by $\overline {\alpha}$.
Let us  assume there is  a $\pi$-periodic polynomial $\alpha$ such
that the second matrix in $ (2.4^\prime)$ is polynomial.
In a degenerate case,
when
$\alpha$ is a monomial, i.e., accurate to multiplication by a constant we
have $\alpha (\omega) =e^ {i2k\omega} $, $k\in\z$,
such choice leads to  a
shift of the elements of bases in $W^ {-1} $ and $\tilde W^ {-1}$ by 2, i.e.,
in fact only to a renumbering of the basis elements. If $\alpha$ is a
nondegenerate polynomial,  in order to the function
$\tilde m_1/\overline {\alpha} $
is a polynomial it is required the coincidence  of zeros of
$\tilde m_1$ and a
polynomial $\overline {\alpha} $.
But then in view of $\pi$-periodicity of the polynomial $\alpha$
the polynomial
$\tilde m_1 (\omega + \pi) $ also has zero at those points, where $\alpha
(\omega) =0$. Thus, there is the point $\omega_0$ at which the vector $
(\tilde m_1 (\omega_0),\tilde m_1 (\omega_0 + \pi)) $ vanishes and the
corresponding matrix in $ (2.4) $ becomes degenerate. It leads to  violation
of equality  (2.4)  not only at this point, but because of 
continuity of components in some its neighborhood.
In the case, when rational solutions of the equation $ (2.4) $
are allowed, the
zero of a determinant of one of the matrices in $ (2.4^\prime) $ can put in the
correspondence to poles of other determinant.
Thus, though the traditional choice of functions $m_1$ and $\tilde m_1$ 
is quite  justified, but it is unique possible only for polynomial 
solutions.
\par
The dual MRA $\{V^j\} $ and $\{\tilde V^j\} $ in a certain sense are
equivalent and can be considered as  an imbedded sequence of spaces in the
signal space as well as for the definition of projection operators,
which in turn
allow to determine spaces of wavelets.
In what follows we stipulate to suppose, that the signals are projected to
the spaces $\tilde V^j$ with the help of the spaces $V^j$.
Such agreement is 
accepted in overwhelming majority publications.
\par
We introduce the functions
$$
h (z) =\sum_ {n\in \z} h_ne^ {-in\omega} =\sqrt {2} m_0 (\omega),\quad \tilde h
(z) =\sum_ {n\in \z} \tilde h_ne^ {-in\omega} =
\sqrt {2} \tilde m_0 (\omega),\tag {2.5}
$$
where $z=e^ {i\omega} $, and
$$
g (z) =z^ {-1} \tilde h (-z^ {-1}),\quad \tilde g (z) =z^ {-1} h (-z^ {-1})
.\tag {2.6}
$$
Functions $h$ and $\tilde h$ we call  {\it  a biorthogonal pair of
filters}.
Now  equality (2.4) in case of real $\{h_n\} $ and $\{\tilde h_n\} $
can be rewritten in the form
$$
M (z) \tilde M^t (z^ {-1}) =2I,\tag {2.7}
$$
where the symbol $t$ means a transposition of a matrix, and
$$
M (z) =\left (\matrix
h (z) &h (-z) \\
g (z) &g (-z) \endmatrix
\right),\quad
\tilde M (z) =\left (\matrix \tilde h (z) &\tilde h (-z) \\
\tilde g (z) &\tilde
g(-z) \endmatrix
\right) 
%\label {9}
$$
are, so-called, {\it modulation matrices}, whose components in our case are rational
functions. From (2.6) and (2.7) it is easily to obtain
that $\det | M (z) | =\det |\tilde M (z) | =-2z^ {-1} $.
\par
Now we  explain a sense and assignment of modulation matrixes $M$ and $\tilde
M$. Let $\tilde v^0 (x) =\sum_n c^0_n\tilde \vf (x-n) \in \tilde V^0$
and it is required to find projections
$\tilde v^ {-1} (x) =\sum_n c^ {-1} _n\tilde \vf (x/2-n) $
and $\tilde w^ {-1}
(x) =\sum_n d^ {-1} _n\tilde \psi (x/2-n) $ of distribution $\tilde v^0$ to
the spaces $\tilde V^ {-1} $ and $\tilde W^ {-1} $.
Using the refinement equation (2.1), we obtain
$$
c^ {-1} _m= \langle \tilde v^0 (x),\vf (x/2-m) \rangle= \sqrt2\langle \sum_
{n\in\z} c^0_n \tilde\vf (x-n),\sum_ {k\in\z} h_k\vf (x-k-2m) \rangle=
\sqrt2\sum_ {n\in\z} c^0_nh_ {n-2m}.
$$
In terms of $z$-transform of sequences the last equality  can be written
in the form
$c^{-1} (z^ {-2}) =\frac {1} {\sqrt2} (h (z) c^0 (z^ {-1}) +
h (-z) c^0 (-z^{-1}))$,
where $c^0 (z) =\sum_ {n} c^0_n z^ {-n} $,
$c^ {-1} (z) =\sum_ {n} c^{-1} _n z^ {-n} $.
We note, that
here and
in what follows
the convergence of series
is guaranteed by exponential decrease of sequences $\{h_n\}$
and $\{\tilde h_n\}$.
The equality $d^ {-1} _m=\sqrt2\sum_ {n\in\z} c^0_ng_ {n-2m} $
is obtained in analogous way.
Hence, $d^ {-1} (z^
{-2}) =\frac {1} {\sqrt2} (g (z) c^0 (z^{-1}) + g(-z)c^0(-z^{-1})) $

\par
Thus, after passage to $z$-transform the matrix $M$ becomes a matrix of
passage from the space $\tilde V^0$ to a direct sum of the spaces
$\tilde V^ {-1} $ and
$\tilde W^ {-1} $, which is determined by the formula
$$
\left (\matrix
c^ {-1} (z^ {-2}) \\
d^ {-1} (z^ {-2})
\endmatrix
\right)
=\dsize\frac {1} {\sqrt2} \left (\matrix
h (z) &h (-z) \\
g (z) &g (-z) \endmatrix
\right)
\left (\matrix
c^ {0} (z^ {-1}) \\
c^ {0} (-z^ {-1})
\endmatrix
\right). \tag {2.8}
$$
For reconstruction of coefficients of expansion of function in basis
of the space $\tilde V^0$ in terms of its projections
on the spaces $\tilde V^ {-1} $ and $\tilde W^{-1}$
the formula $$ 
\left (\matrix
c^ {0} (z^ {-1}) \\
c^ {0} (-z^ {-1})
\endmatrix
\right)
=\dsize\frac {1} {\sqrt2} \left (\matrix \tilde h (z^ {-1}) &\tilde g (z^ {-1})
\\ \tilde h (-z^ {-1}) &\tilde g(-z^ {-1}) \endmatrix
\right)
\left (\matrix
c^ {-1} (z^ {-2}) \\
d^ {-1} (z^ {-2})
\endmatrix
\right)
$$
holds.
Certainly, the last formulae are convenient for analytical representation of
operation of expansion in wavelets and reconstruction
by projections. However, they contain
many repeated operations and consequently they cannot be recommended for an
immediate evalu\-ation of coefficients.
\par
In some sense an alternative method of representation of operation
of expansion
of the space $\tilde V^0$ in a direct sum of spaces $\tilde V^ {-1} $
and $\tilde W^ {-1} $ is its realization with the help of, so-called,
polyphase matrix. For an arbitrary formal Laurent series
$f (z) =\sum_n f_nz^ {-n} $ we introduce the notation
$f_e (z) =\sum_n f_ {2n} z^{-n} $ and $f_o (z) =\sum_n f_ {2n + 1} z^ {-n} $.
Then the representation $f (z)=f_e (z^2) + z^ {-1} f_o (z^2) $ is valid.
Using this representation, by
replacing them all components of the formula (2.8), after simple
transformations of a right side we obtain
$$
\left (\matrix
c^ {-1} (z^ {-1}) \\
d^ {-1} (z^ {-1})
\endmatrix
\right)
=\left (\matrix
h_e (z) &h_o (z) \\
g_e (z) &g_o (z) \endmatrix
\right) 
\left (\matrix
c_e^ {0} (z^ {-1}) \\
c_o^ {0} (z^ {-1})
\endmatrix
\right). \tag {2.9}
$$
Just this formula is an initial point
for a construction of fast algorithms of
decomposition and reconstruction of signals,
joined by a common title {\it the lifting 
scheme}. A matrix in expression (2.9) is called {\it polyphase}.
We denote it by $P (z) $. Polyphase matrix of a dual MRA is denoted by
$\tilde P(z)$. It is easily to verify that
$$
P (z) \tilde P^t (z^ {-1}) =I.\tag2.10
$$
\par
Besides,  since for polyphase matrices $P$ and $\tilde P$ representations 
$$
P (z^2) =\frac12 M (z) \left (\matrix 1 &z\\1 &-z\endmatrix\right),\quad
\tilde
P (z^2) =\frac12 \tilde M (z) \left (\matrix 1 &z\\1 &-z\endmatrix\right)
$$
are valid,
from the equalities $\det M=\det \tilde M=-2z^ {-1} $ we have $\det P=\det \tilde
P=1$.
% ****************************
\head
\S 3. Examples.
\endhead
% ****************************
Equation (2.7) has many rational solutions.
Though from further reasoning
easily to see, in what way
all possible solutions
of such type
 can be obtained, here we are  interested in only
some of them, which have a minimal order of a numerator and denominator and
correspond to wavelet bases, whose  scaling functions are
symmetric with respect to whole or half-integer points.
Thus, we  show, that after an appropriate shift of argument the corresponding
wavelet bases are odd functions in the first case, and even ones in the second case.
Therefore for a short we  speak, that an odd or even case takes
place respectively.
\par
First we  consider the  even case.
We  note, that the multiplying the function $h (z) $ by $z^k$ means
passage from a scaling function $\vf (z) $ to the scaling function
$\vf (z + k) $,
i.e. passage to one of functions of a basis system of shifts.
Easily to see, that,  multiplying $h$, if it is necessary, by an appropriate
integer degree of a variable $z$, we  obtain, that in (2.5)
$h_n=h_ {-n} $ for all $n=1,2,\dots$.
The function $h (z) $ together with each pole at $z=z_0$ has a pole at
$z=z_0^ {-1}$.
Thus, rational function $h$ is representable as a ratio of two polynomials
$S (z)=\sum_ {n=-l} ^l s_nz^ {-n} $ and $Q (z) =\sum_ {n=-m} ^m q_nz^ {-n} $
with symmetric sequences of coefficients $s_ {-n} =s_n$ and $q_ {-n} =q_n$,
hence, invariant with respect to a change of variable $z\to z^ {-1} $.
\par
In the odd case, by multiplying $h$, if it is necessary, by an appropriate
integer 
degree of a variable $z$, we  obtain $h_n=h_ {1-n} $ for all
$n=1,2,\dots$. It is clear, that the function $f (z) = (1 + z) h (z) $ has a
symmetric sequence of Laurent coefficients.
The sequence of Laurent coefficients of function $f (z) / ((1 + z) (1 + z^ {-1})) $
is symmetric, and this function is rational and representable in the form
$S (z) /Q (z) $,
where $S$ and $Q$ are Laurent polynomials with symmetric sequences of factors,
invariant with respect to a change $z\mapsto z^ {-1} $.
Thus,
$$
h (z) =\frac {(1 + z^ {-1}) S (z)} {Q (z)}.
$$
\par
We show, that the filters $h$ and $\tilde h$ can have distinguish
evenness, i.e., when one function corresponds to the even case, and other
does
to the odd one, only for a pair of filters
$h (z) = (1 + z^ {-1}) /\sqrt {2} $ and $\tilde h (z) =\sqrt {2} $.
In spite of the fact that the given pair of filters leads to two MRA,
generated accordingly the Haar basis  and basis, consisting of shifts
$\delta$-function, in view of a discontinuity the Haar functions these
bases is not form a biorthogonal pair.
\par
From (2.7) for an arbitrary pair $h$ and $\tilde h$ we obtain
$$
h (z) \tilde h (z^ {-1}) + h (-z) \tilde h (-z^ {-1}) =2
$$
or, substituting a representation $h (z) $ and $\tilde h (z) $ in the form
of rational functions and reducing if necessary the common factors
of a numerator and
denominator, we obtain expression of the form
$$
\frac {A (z)} {B (z)} + \frac {A (-z)} {B (-z)} =2,\tag3.1
$$
where $A$, $B$ are Laurent polynomials of $z$. The addends in (3.1) should
have common poles with consideration for a multiplicity.
In
particular, it follows from this that the polynomials $B (z) $ and $B (-z) $
have the same zeros. Thus, we obtain
that in a polynomial
$B$, at least after a multiplying, if it is   necessary, by an appropriate 
factor $z^k$, only even degrees are present, i.e.,
$B (z) =\Cal B (z^2) $, where
$\Cal B (z) $ is some Laurent polynomial.
Thus,  equation (3.1) can be rewritten in the form
$$
{ A (z)} + {A (-z)} =2 {\Cal B (z^2)} .\tag3.2
$$
The last equation is a simple sourse of all possible MRA. Indeed,
it is easily to see from relation (3.2), that the Laurent polynomial $A$
can be chosen arbitrary within certain limits.
As above $A_e (z) =\Cal B (z) $
an arbitrary Laurent
polynomial, that 
has not  the roots on a unit circle $ | z | =1$,
can be taken. Then, since
$A (-1) =m_0 (\pi) \overline {\tilde m_0 (\pi)} =0$, the polynomial $A_o$
has to satisfy  the equality $A_o (1) =A_e (1) $, i.e.,
sums of coefficients of
polynomials $A_o$ and $A_e$ has to coincide. All possible
biorthogonal filters
$h$ and $\tilde h$ come out a factorization
$h (z) \tilde h (z^ {-1}) =A (z)/B (z) $,
where $h (1) =\tilde h (1) =\sqrt {2} $.
Certainly, not all factorizations lead to biorthogonal pairs of wavelet
bases, however, all such pairs of bases are generated by these
factorizations.
\par
Now we assume, that one of the functions $h$ and $\tilde h$ generates
an even
MRA, and other does an odd one.
Then the representation $A (z) = (1 + z^ {-1}) \Cal A (z)$,
where $\Cal A (z) $ is Laurent polynomial with a symmetric sequence of
coefficients, is valid.
Substituting this representation in (3.2), we have
$$
{ (1 + z^ {-1}) \Cal A (z)} + {(1-z^ {-1}) \Cal A (-z)} =2 {\Cal B
(z^2)},\tag3.3
$$
where without loss of generality it is possible to suppose that the
polynomials $\Cal A$ and $\Cal B$ have not common zeros.
The right member of equality (3.3) is invariant with respect
to a change of variable $z\to z^ {-1} $, since it is
a product of polynomials, possessing this
property. Hence,  his  left part is invariant with respect to such
replacement.
Consequently,
$$
{ (1 + z^ {-1}) \Cal A (z)} + {(1-z^ {-1}) \Cal A (-z)} = {(1 + z) \Cal A (z^
{-1})} + {(1-z) \Cal A (-z^ {-1})}.
$$
And because of
$\Cal A (z) =\Cal A (z^ {-1}) $, the last equality is transformed to 
the form
$$
( z^ {-1} -z) (\Cal A (z) - \Cal A (-z)) =0.
$$
It means a lack of odd degrees of the polynomial $\Cal A$ .
But then, returning
to (3.3), we  see that $\Cal A (z) =\Cal B (z^2) $. So, in view of a lack
of common divisors of these polynomials we have $\Cal A\equiv 1$.
A biorthogonal pair of filters $h (z) = (1 + z^
{-1}) /\sqrt {2} $ and $\tilde h (z) =\sqrt {2} $
corresponds to the given case.
Thus, $h$ and $\tilde h$ can have distinguish evenness
only for 
trivial case mentioned above,
which does not generate biorthogonal wavelet bases.
\par
So, we consider even and odd biorthogonal pairs with small orders of a
numerator and denominator of functions $h$ and $\tilde h$.
We start from the odd case.
The  simplest right term in (3.2) can be taken as
$\Cal B\equiv 1$. At the first sight, this case can seem degenerate
and corresponding to biorthogonal compactly supported bases.
Nevertheless, one could appear, that the zero of one of
the functions $h (z) $ and $\tilde h (z^ {-1})$ has appeared a pole of other
function. Then the corresponding factors in a product
$h (z) \tilde h (z^ {-1}) $
are reduced and consequently are not taken in consideration in (3.1).
The specific features of MRA forces us to consider not all solutions
of equation
(3.2). Principal of restrictions consists of the fact that since
for the odd case
$h (-1) =\tilde h (-1) =0$, then
$A (z) = (1 + z) (1 + z^ {-1}) \Cal A_1 (z) $.
Thus, the polynomial $\Cal A_1 (z) $
of a minimal possible degree is
equal to a constant, $\Cal A_1 (z) \equiv 1/2$. And taking into account, that
the rational functions $h (z) / (1 + z^ {-1}) $
and $\tilde h (z) / (1 + z^{-1}) $ have symmetric sequences
of Laurent factors, we obtain that a
biorthogonal rational pair of filters of the minimal possible degree
looks like
$$
h (z) =\alpha\frac {1 + z^ {-1}} {\sqrt {2} (z^ {-1} + a + z)},\qquad
\tilde h (z) =\frac {1} {\sqrt {2} \alpha} (1 + z^ {-1}) (z^ {-1} + a + z),
$$
where $\alpha=2 + a$ is a factor which ensures a normalization
$h (1) =\tilde h(1) =\sqrt2$.
\par
For the wavelet theory only the case $ | a | > 2$ is a subject of interest.
Indeed, the polynomial $1 + az + z^2$ has the roots $z_ {1,2} =-\frac
{a} {2} \pm\sqrt {\frac {a^2} {4} -1} $. For $ | a | \le 2$
the both roots are
equal to 1 in modulus, i.e.,
$z_ {1,2} =e^ {\pm i\omega_0} $. Hence, in this case
the function $m_0 (\omega) $ has singularities at points
$\omega=\pm\omega_0$
and not only is nonsummable, but also is not even a distribution.
\par
The considered example shows,
in what way  MRA (in our case  MRA, generated by the Haar bases)
may be varied by means of
addition a
factor $z^ {-1} + a + z$ in a denominator of one of the filters $h$, $\tilde h$
and the same factor in a numerator of the other.
From the qualitative point of view this
method leads to "swapping of a smoothness" between one basis of a
biorthogonal pair  and its dual  basis with preservation of a summarized
smoothness of bases. Such method can be used for a variation of any
biorthogonal pair and it should be taken into account,
though in what follows we shall not 
mention about it.
\par
Now we consider a less trivial case, when a polynomial $\Cal B$
is nondegenerate. In the simplest case
$\Cal B (z) =z^ {-1} + a + z$. Here for the above mentioned reasons
we also have $ | a | > 2$.
Hence, we obtain, that the polynomial $\Cal A_1$
of a minimal possible degree, satisfying (3.2),
looks like $\Cal A_1 (z) =z^ {-1} +
(\frac {a} {2} -1) + z$. Thus, there are two biorthogonal pairs:
$$ h (z) =\sqrt {2} \frac{(1 + z^ {-1}) (z^ {-1} + (\frac {a} {2} -1) + z)}%
{z^ {-2} + a + z^2},\qquad
\tilde h (z) =\frac {1 + z^ {-1}}{\sqrt {2}}
$$
and
$$
h (z) =\alpha\frac {(1 + z^ {-1})}{z^ {-2} + a + z^2},\qquad
\tilde h (z) =\frac {(1 + z^ {-1})(z^ {-1} + (\frac {a} {2} -1) + z)}{\alpha},
\text {where } \alpha=\frac {a + 2} {\sqrt {2}},
$$
corresponding to
the given choice of the polynomial $\Cal B$.
\par
We  consider the simplest solutions in the even case.
Since in (3.1) $A (-1)=0$,
one of polynomials $h$ or $\tilde h$ has zero at the point $z=-1$.
And because of symmetry of
the coefficient sequence the root is of even multiplicity.
Hence, the polynomial $A (z) $ contains the factor $z^{-1} + 2 + z$.
Thus, in the simplest case $A (z) =\frac12 (z^ {-1} + 2 + z)$,
$\Cal B (z) \equiv1$, $$
h (z) =\sqrt2,\qquad
\tilde h (z) =\frac {z^ {-1} + 2 + z} {2\sqrt2}.
$$
The given pair of FIR-filters leads to a pair of 
a biorthogonal MRA, first of which is generated by shifts of
$\delta$-function, and other is generated by shifts of linear B-spline.
At the first glance, one can
seem that this example is degenerate and has not prospect
to be used
in applications. Indeed, "imperfections" of this pair consist in the fact
that one of spaces of a dual pair consists of distributions,
besides the functions of bases of piecewise linear wavelets
have not zero mean value.
The second property seems
especially unpleasant from the generally accepted point of view,
because it is considered, that good for approximation bases (in
particular for compression of an information)   should have
many zero moments or, what is the same, the polynomial $h (z) $
should have a high multiplicity of zero at the point $z=-1$.
Nevertheless, it turns out, that in  most cases use of this pair of bases for
image compression leads to bigger to compression factors, than use
quite satisfactory Haar bases.
Taking into account high computing effectiveness of these bases,
it is possible to assume, that they quite can be used in applications.
\par
Now we  consider the case, when $\Cal B (z) =z^ {-1} + a + z$.
For the polynomial $\Cal A_1$, chosen
before, four variants of an even factrization $h (z)\tilde h (z^ {-1}) = (z^ {-1} + 2 + z) \Cal A_1 (z) $
are possible:
$$
h (z) =\frac {(z^ {-1} + 2 + z) (z^ {-1} + (\frac {a} 2-1) + z)} {\sqrt {2} (z^
{-2} + a + z^2)},\qquad \tilde h (z) =\sqrt {2}; % \text
$$
$$
h (z) =\frac {(a + 2) (z^ {-1} + 2 + z)} {2\sqrt {2} (z^ {-2} + a +
z^2)},\qquad \tilde h (z) =2\sqrt {2} \frac {z^ {-1} + (\frac {a} 2-1) + z}
{a+ 2}; % \text
$$
$$
h (z) =\frac {z^ {-1} + 2 + z} {2\sqrt {2}},\qquad \tilde h (z) =2\sqrt {2}
\frac {z^ {-1} + (\frac {a} 2-1) + z} {z^ {-2} + a + z^2}; % \text
$$
$$
h (z) =\frac {(z^ {-1} + (\frac {a} 2-1) + z) (z^ {-1} + 2 + z)} {\sqrt {2} (a
+ 2)},\qquad \tilde h (z) =\frac {\sqrt {2} (a + 2)} {z^ {-2} + a + z^2}.
$$
We  note, that for all four cases $\tilde h (-1) \ne0$.
\par
It is clear, that for realization of the relation
$h (-1) =\tilde h (-1) =0$ in
the even case it is necessary to require that a polynomial
$A (z) $ in (3.2) has zero of at least  of the fourth order at the point $-1$.
Thus, representation 
$A (z) = (1 + z) ^2 (1 + z^ {-1}) ^2\Cal A_2 (z) $ is valid.
Let again $\Cal B (z) =z^ {-1} + a + z$.
Then, solving  equation
(3.2) for $\Cal A_2 (z) $ of the form $bz^ {-1} + c + bz$, we obtain
$$
\Cal A_2 (z) =\frac {6-a} {16} z^ {-1} + \frac {a-2} {4} + \frac {6-a} {16} z,
$$
where, as well as earlier, $ | a | > 2$.
Thus, assuming $b=\frac {6-a}{16}$,
$c=\frac{a-2}{4}$, we have
two different biorthogonal pairs
$$
h (z) =\frac {2 (z^ {-1} + 2 + z) (bz^ {-1} + c + bz)}{\sqrt {2} (z^ {-2}+ a + z^2)},
\qquad
\tilde h (z) =\frac {z^ {-1} + 2 + z} {2\sqrt {2}} \tag3.4
$$
and
$$ h (z) =\frac {4 (z^ {-1} + 2 + z) (bz^ {-1} + c + bz)} {\sqrt {2} (a +
2)},\quad \tilde h (z) =\frac {\sqrt {2} (a + 2) (z^ {-1} + 2 + z)} {4 (z^ {-2}
+ a + z^2)} .\tag3.5 $$
\par
Formulae (3.4) and (3.5) have
two important special cases, when the
algorithms of  wavelet decomposition are much simplified.
The first of these
cases $a=6$ leads to the simplified biorthogonal pair
$$
h (z) =\frac {z^ {-1} + 2 + z} {2\sqrt {2}}.
\qquad
\tilde
h (z) =\frac {2\sqrt {2} (z^ {-1} + 2 + z)}{z^ {-2} + 6 + z^2},
$$
\par
The second case under   the limit passage $a\to\infty$ leads to the known 
(see [2] and [4, p. 277]) biorthogonal pair of compactly supported bases
 that is determined by
the functions
$$
h (z) =\frac {(z^ {-1} + 2 + z) (-z^ {-1} + 4-z)}{4\sqrt {2}},\qquad
\tilde h (z) =\frac {z^ {-1} + 2 + z} {2\sqrt {2}}.
$$
At last,  two more important pairs of filters are obtained
at $a=10/3$.
For this value of the  parameter $a$ at the point $-1$ filters  which
have a maximal (equal to 6) summarized multiplicity of
zero are obtained.
Filters (3.4) is transformed thus to filters
$$
h (z) =\frac {\sqrt {2} (z^ {-1} + 2 + z) ^2}{3z^ {-2} + 10 +3z^2},\qquad
\tilde h (z) =\frac {z^ {-1} + 2 + z} {2\sqrt {2}}
$$
and filters (3.5) is transformed to  filters
$$
h (z) =\frac {(z^ {-1} + 2 + z) ^2}{8\sqrt {2}},\qquad \tilde h (z) =\frac
{4\sqrt {2} (z^ {-1} + 2 + z)} {3z^ {-2} + 10a + 3z^2}. $$
\par
We  note, that except for two pairs (3.4) and (3.5)
in this case there are 
four more different factorizations, for which one of the filters $h$ or $\tilde h$
has not zero at the point $-1$.
% ******************************************
\head
\S4.
Method of a lifting.
\endhead
% ******************************************
The greatest progress in a problem of acceleration of algorithms of
function expansion in wavelet bases and their reconstruction by expansion
coefficients is connected to, so-called, lifting  scheme, accepting a
completed form in  [3].  Close ideas were realized in [6] and [15].
Just upon the approach, considered in [6],  we lean  here.
\par
We introduce necessary notation. Let $\Pi (z) $ be Laurent polynomial
$\Pi (z)
=\sum_ {n=k_1} ^ {k_2} p_nz^n$, where $k_1, k_2\in\z$,
then $l (\Pi) \dfn k_1$,
$u (\Pi) \dfn k_2$, $L (\Pi) \dfn p_ {l (\Pi)} $, $U (\Pi) \dfn p_ {u (\Pi)}$.
The value  $d (\Pi) \dfn u (\Pi) -l (\Pi) $ we call an order of a
polynomial $\Pi$.
\par
At first we consider a case,
when each of rational functions $h$ and
$\tilde h$ has not roots, being poles of another function.
In this case, as it was
shown in the previous section the denominators of these functions are Laurent
polynomials of $z^2$, that allows to write components
of a polyphase matrix $P$ in the form
$$
h_e (z) =\frac {E_1 (z)} {Q_1 (z)},\quad h_o (z) =\frac {O_1 (z)} {Q_1
(z)},\quad g_e (z) =\frac {E_2 (z)} {Q_2 (z)},\quad g_o (z) =\frac {O_2 (z)}
{Q_2 (z)} .\tag4.1
$$
The fact that a determinant of a polyphase matrix is equal to the identity
imples the  relation
$$
\det\left (\matrix E_1 (z) &E_2 (z) \\O_1 (z) &O_2 (z) \endmatrix\right) =Q_1
(z) Q_2 (z). \tag4.2
$$
holds.
 It is clear from here that two inequalities 
$$
\Cal L (P) \dfn l (Q_1Q_2) -\min \{l (E_1O_2), l (O_1E_2) \} \ge0; $$
$$
\Cal U (P) \dfn \max \{u (E_1O_2), u (O_1E_2) \} - u (Q_1Q_2) \ge0 $$
are valid.
The value $\Cal D (P) \dfn
\Cal L (P) + \Cal U (P) $ is said to be 
{\it the defect} of matrix $P$.
\par
Matrices of the form
$$
T^ + (k, a) =\left (\matrix 1 &az^{k} \\0 &1\endmatrix\right),
\qquad T^- (m,
b) =\left (\matrix 1 &0\\ bz^ {m} &1\endmatrix\right),
$$
where $a, b\in\R$; $k, m\in\z$, are said to be  {\it  elementary liftings}.
\proclaim {Theorem 1}
Any polyphase matrix $P$ with rational components of the form (4.1) can be
represented in the form
$$ P (z) =P_0 (z)T^ {\sigma (1)} (k_1, a_1) T^ {\sigma (2)} (k_2, a_2) \dots T^
{\sigma (\Cal D (P))} (k_ {\Cal D (P)}, a_ {\Cal D (P)}) ,\tag4.3
$$
where $P_0 (z) $ is a matrix with a zero defect, $k_i\in\z$, $a_i\in\R$,
$\sigma (i) $ is an appropriate sign;
$i=1,2,..., \Cal D (P) $.
\endproclaim
\remark {Remark 1} In a statement of  Theorem 1 it does not affirm that all
elementary liftings in (4.3) are nondegenerated. Some of them can be equal
to the identity matrix.
\endremark
\remark {Remark 2} Factrization (4.3) is determined by  not
a unique way.
\endremark
\demo {Proof of  Theorem 1} To  prove  the theorem it suffices to 
show that any polyphase matrix $P$  of a non-zero defect can be
represented in the form $P (z) =P^\prime (z)T^ {\sigma} (k, a)$,
where $\Cal D (P^1) < \Cal D(P) $.
\par
First we prove the following auxiliary statement.
\proclaim {Lemma 1}
If for a polyphase matrix $P (z) $ with rational components of the form (4.1)
the  inequality $\Cal L (P) > 0$ (or $\Cal U (P) > 0$) is valid, then
$l (E_1) + l (O_2)
=l (E_2) + l (O_1) $ (or $u (E_1) + u (O_2) =u (E_2) + u (O_1) $) and
the determinant of the matrix
$$
A=\left (\matrix L (E_1) z^ {l (E_1)} &L(E_2) z^ {l (E_2)} \\ L (O_1) z^ {l
(O_1)} &L(O_2) z^ {l (O_2)} \endmatrix\right) \quad
\left (\text { or } B=\left (\matrix U (E_1) z^ {u (E_1)} &U(E_2) z^ {u (E_2)}
\\ U (O_1) z^{u (O_1)} &U (O_2) z^ {u (O_2)}
\endmatrix\right) \right)
$$
is equal to zero.
\endproclaim
\demo { Proof of  Lemma 1}
In the case when the  equality $l (E_1) + l (O_2) =l (E_2) + l (O_1) $ is violated
we come to contradiction  to equality (4.2), since the minimal degree in
the left side  equals  $\min \{l (E_1O_2), l (E_2, O_1) \} $. By assumption
of  Lemma 1 it is less than minimal power of the right term of
equality (4.2).
\par
For the same reason the determinant of the matrix $A$ is equal to zero, since
in the opposite case the minimal power of a polynomial in the left part (4.2) would be
less than minimal power of the right member.
\par
The statement, concerning the matrix $B$, is proved in similar way.
\enddemo
Let us return to  proving  Theorem 1.
\par
Let for a definiteness
$\Cal L (P) > 0$. Then it follows from  Lemma 1 that
$$
l (E_1) + l (O_2) =l (E_2) + l (O_1) .\tag4.4
$$
For  a definiteness we also assume, that
$$ d (E_1) \le d (O_1) .\tag4.5
$$
\par
We consider two cases: 1) $\Cal U (P) > 0$; 2) $\Cal U (P) =0$.
\par
In the first case, according to  Lemma 1,
we have $u (E_1) + u (O_2) =u (E_2) +
u (O_1) $. Subtracting (4.4) from here, we  obtain
$d (E_1) + d (O_2) =d
(E_2) + d (O_1) $, that join with (4.5) gives
$d (E_2) \le d (O_2) $.
Thus, by carrying out transformation
$E_1^\prime (z) =E_1 (z) $, $E_2^\prime (z) =E_2 (z) $,
$O_1^\prime (z) =O_1 (z) -a z^k E_1 (z) $, $O_2^\prime (z) =O_2
(z) -a z^k E_2 (z) $, where $a=L (O_1) /L (E_1) $, $k=l (O_1) -l (E_1) $,
taking into account that the determinant of the matrix $A$
is equal to zero, we obtain
$l (O_1^\prime) =l (O_1) + 1$, $l (O_2^\prime) =l (O_2) + 1$. At
the same time, the inequalities $u (O_1^\prime) \le u (O_1) $, $u (O_2^\prime) \le
u (O_2) $ are valid. Hence, the defect of the matrix
$$
P^\prime (z) \dfn P (z)\left (\matrix 1 &-az^k \\0&1\endmatrix\right)  \tag4.6
$$
is strictly  less than the defect of the matrix $P$.
As was to be proved.
\par
Let now $\Cal U (P) =0$. We  show that  transformation (4.6) reduces
the defect of the matrix $P$ at least by 1.
If $d (E_2) \le d (O_2) $, the mentioned above reasoning remain in a force.
We consider the case $d (E_2) > d (O_2) $.
Because after transformation
(4.6) we have $\Cal L (P ") \le\Cal L (P) -1$, it remains to prove
an invariance of the value $\Cal U (P) $.
Easily to see, that
$u (O_2^\prime) =u (E_2) + k$ and $u (O_1^\prime) \le u (O_1) $. Thus,
$u(E_2O_1^\prime) \le u (E_2O_1) $ and $u (E_1O_2^\prime) =u (E_1) + u (E_2) +
k\le u (O_1) + u (E_2) =u (E_2O_1) $. Hence,
$$
\multline
\Cal U (P ") =\max\{u (E_1O'_2), u (O'_1E_2) \} - u (Q_1Q_2) \le\\ \max\{u
(E_1O_2), u (O_1E_2) \} - u (Q_1Q_2) =\Cal U (P) =0.
\endmultline
$$
Thus,
$\Cal D (P^\prime) \le\Cal D (P) -1$.
\par
In conclusion of the proof of  Theorem 1 we note that in the case,
when $d (E_1)> d (O_1) $, it should be applied an elementary lifting,
being the upper triangular matrix.
\enddemo
\par
As it will be shown in \S 5,
realization of algorithms leaning upon the factorization,
guaranteed by Theorem 1, has a double asymptotic gain in
computational complexity for fixed degrees of denominators
of $h (z) $ and $\tilde h(z) $ and degree of at least one of numerators,
goes to infinity, provided
that both functions
$h (z) $ and $\tilde h (z) $ have a general form, i.e.,
there are
no zeros or respectively little amount of them
among coefficients
of their numerators between a maximum and minimum degree.
\par
However, in practice most often it is necessary to deal  with wavelets which
with accurate to a shift of argument are even or odd functions.
Just such examples were considered in \S 2.
\par
Unfortunately, for sequences $h_n$ and $\tilde h_n$ with
half-integer  symmetry  we were not succeeded to find a lifting  realization,
taking into account a symmetry.
The importance of this problem is obvious, since
such sequences determine bases of odd wavelets (elementary example of
such functions are
Haar's wavelets).
\par
We  consider the case of even wavelets.
About a possibility of taking account of the symmetry at a realization of the
lifting  scheme, when $h (z) $ and $\tilde h (z) $ are  Laurent
polynomials, it was  mentioned (without a proof) in [3].
In those paper for all examples,
corresponding to the even case, the lifting  realization
is given with the taking account of evenness.
\par
The problem here is as follows. When $h (z) =S (z) /Q (z) $, where $S$, $Q$ are
Laurent polynomials, for which $S (1/z) =S (z) $, $Q (1/z) =Q (z) $,
it is possible to economize at a
realization of  formulae (2.8) or (2.9), accounting
 a symmetry of a numerator, using the formula
$$
c^ {-1} _k=h_0c^0_ {2k} + \sum_ {m=1} ^M h_m (c^0_ {2k + m} + c^0_ {2k-m}),
$$
where $2M=d (S) $. Asymptotically at large $m$ at the account
of a symmetry the amount of operations is equal $3/4$
of the amount of operations which is  necessary in a
general case. Naturally, it would be necessary at a lifting  realization
additionally to the double gain to obtain the same additional gain in
computational complexity.
\par
So, we suppose that the both rational functions $h (z) $ and $\tilde
h (z) $ have a sequences of Laurent coefficients which are
symmetric  with respect to the coefficient with the zeroth subscript.
Then without loss of generality it is possible to state this about
polynomials $E_1$, $E_2$, $O_1$, $O_2$ in notation of (4.1).
Then the following statement takes place.
\proclaim {Theorem 2}
Let a polyphase matrix $P (z) $ has rational components of the form (4.1),
generated by sequences $h_n=h_ {-n} $, $\tilde h_n=\tilde h_ {-n} $. Then the
matrix $P (z) $ has an even defect and can be representted in the form 
$$
P (z) =P_0 (z)\left (\prod_ {i=1} ^ {\Cal D (P) /2} T^ {\sigma (i)} (\sigma (i) k_i,
a_i) T^ {\sigma (i)} ((-1) \cdot\sigma (i) (k_i + 1), a_i) \right) ,
%\tag4.3
$$
where $P_0 (z) $ is a matrix with a zero defect, $k_i\in\Bbb N\cup {0} $,
$a_i\in\R$,
$\sigma (i) $ is a sign chosen in appropriate way.
\endproclaim
\demo {Proof of Theorem 2}
First we  show  that the defect of the matrix $P (z) $ is an even
number. Indeed, from a symmetry of factors it is easily to receive
that $l(E_1) =-u (E_1) $, $l (O_1) =1-u (O_1) $, $l (O_2) =-u (O_2) $, $l (E_2) =-1-u
(E_2) $. Hence,
$l (E_1O_2) =-u (E_1O_2) $ and $l (E_2O_1) =-u (E_2O_1) $, moreover,
$l (Q_1Q_2)
=-u (Q_1Q_2) $. Therefore $\Cal L (P) =\Cal U (P) $, that implies $\Cal D (P)
=2\Cal L (P) =2\Cal U (P) $.
\par
Thus, it remains to show that any matrix $P (z) $ with a non-zero
defect, satisfying  conditions of Theorem 2,  can be 
represented in the form
$$
P (z) =
P_1(z)T^{\sigma}(\sigma k,a)T^{\sigma}((-1)\cdot\sigma(k+1),a),
%\tag4.3
$$
where $P_1$ is a matrix, also satisfying  conditions of  Theorem 2.
\par
Since $\Cal L (P) = \Cal U (P) > 0$, by Lemma 1 we have $l (E_1) + l
(O_2) =l (E_2) + l (O_1) $
and $u (E_1) + u (O_2) =u (E_2) + u (O_1) $. Moreover, the determinants
of matrices
$$
A=\left (\matrix L (E_1) &L (E_2) \\
L (O_1) &L (O_2)
\endmatrix\right),\quad
B=\left (\matrix U (E_1) &U (E_2) \\
U (O_1) &U (O_2)
\endmatrix\right)
$$
are equal to zero. In view of a symmetry of the sequences $h_n$ and $\tilde h_n$
we have $A=B$.
In view of the fact that $d (E_1) $ and $d (O_2) $ are even numbers
and $d (O_1)$
and $d (E_2) $ are odd ones, 
either fulfilment inequalities a) $d (E_1)> d (O_1) $, $d (E_2) > d (O_2) $ or b) $d (E_1) <
d (O_1) $, $d (E_2) < d (O_2) $ takes place.
\par
We assume that inequalities a) are valid.
Then,  choosing $a=L(E_1) /L (O_1) $ and $m=u (E_1) -u (O_1) $, we obtain
that for
polynomials
$$
E'_1 (z) =E_1 (z) -a (z^m + z^ {-m-1}) O_1 (z),
$$
$$
E'_2 (z) =E_2 (z) -a (z^m + z^ {-m-1}) O_2 (z)
$$
relations 
$E'_1 (z) =E'_1 (z^ {-1}) $, $E'_2 (z) =z^ {-1} E'_2 (z^ {-1}) $, $d (E'_1) =d
(E_1) -2$, $d (E'_2) =d (E_2) -2$ hold.
Thus, taking as above $P_1 (z) $ a
matrix, obtained of $P (z) $ by the change $E_1\to E'_1$, $E_2\to E'_2$,
we have
$$
P_1(z)=P(z)\left(\matrix 1 &0\\-a(z^m+z^{-m-1})&1\endmatrix\right)=
P(z)T^-(m,-a)T^-(-(m+1),-a)\tag4.7
$$
or
$P(z)=P_1(z)T^-(-(m+1),a)T^-(m,a)=P_1(z)T^-(m,a)T^-(-(m+1),a)$.
\par
The case b) is considered in similar way. Operating in the same way as  for
the case a), we obtain
$$
P(z)=P_1(z)T^+(-m,a)T^+(m+1,a),
$$
where $a=L (O_1) /L (E_1) $, $m=l (O_1) -l (E_1) $, and the matrix $P_1 (z) $
differs from $P (z) $ by the change
$$ O_1 (z) \to O'_1 (z) =O_1 (z) -a (z^ {-m} + z^ {m + 1}) E_1 (z), $$ $$ O_2
(z) \to O'_2 (z) =O_2 (z) -a (z^ {-m} + z^ {m + 1}) E_2 (z). $$
Thus, Theorem 2 is proved.
\enddemo
%
\head
\S 5.  Numerical realization of algorithms of subband coding. \endhead
%
Now we consider realization of decomposition and reconstruction
algorithms in a basis of which the lifting scheme  lays.
First we 
explain what advantage is given by a factorization of a polyphase
matrix, guaranteed by Theorem 1.
Let us calculate how many arithmetical operations
(additions  and multiplications) 
is required for a direct realization of the formula.
For this purpose in notation of \S4 the action of
a polyphase matrix $P (z) $ to a signal
it is conveniently to represent
in the form
$$
P (z)
\left (\matrix
c_e^ {0} (z^ {-1}) \\
c_o^ {0} (z^ {-1})
\endmatrix
\right)
=\left (\matrix \dsize\frac {1} {Q_1 (z)} &0\\0 &\dsize\frac{1}{Q_2 (z)}
\endmatrix\right) \left(\matrix E_1(z) &O_1 (z) \\E_2 (z) &O_2 (z)
\endmatrix\right) \left (\matrix
c_e^ {0} (z^ {-1}) \\
c_o^ {0} (z^ {-1})
\endmatrix
\right). \tag5.1
$$
Easily to see that the first matrix multiplication in (5.1)
by a signal vector
can be realized, using on average for $d (E_1) + d (O_1) + d
(E_2) + d (O_2) + 3$  arithmetical operations for a signal sample.
Indeed, for
deriving one factor in Laurent expansion of the first component
it is required
$2d (E_1) + 2d (O_1) + 3$  operations, and for deriving one Laurent
factor of
the second component it is required $2d (E_2) + 2d (O_2) + 3$  operations.
\par
We  stop in more details on a realization of the second factor with the
help of  a method, which in a radio engineering refers to as a digital
recursive filter.
Since for $ | a | < 1$ we have
$$ \sum_ {n_\in\z} \beta'_nz^n\dfn\frac {1} {1-az} \sum_ {n\in\z} \beta_nz^n
=\sum_ {n\in\z} \beta_nz^n \sum_ {n=0} ^ {+ \infty} a^nz^n=\sum_ {n\in\z} \left
(\sum_ {k=0} ^ {+ \infty} \beta_ {n-k} a^k\right) z^n,\tag5.2
$$
then
$$
\beta'_n=\dsize \sum_ {k=0} ^ {+ \infty} \beta_ {n-k} a^k= \sum_ {k=0} ^ {+
\infty} \beta_ {n-1-k} a^ {k + 1} + \beta_n= (\sum_ {k=0} ^ {+ \infty} \beta_
{n-1-k} a^ {k}) a + \beta_n= \beta'_ {n-1} a + \beta_n.
$$
The obtained recurrence formula is called {\it  an elementary recursive
filter}.
\par
If there exists $N$ such that
$\beta_n=0$ for $n < N$, therefore $\beta'_n=0$, and
the recursive filter allows an exact realization of  formula (5.2).
Certainly, in this case the interior sum in (5.2) is finite and consequently
it allows  an exact realization.
However, the computational complexity for
its realization are much higher than complexity of the recursive filter.
\par
In the case when there are non-zero $b_n$ with an arbitrary large negative
numbers,
the recursive filter can be realized, beginning with
some number $N$. Therefore there is a necessary error in
its realization, which decreases with each pitch  as
 a geometrical progression with a ratio $a$.
\par
Similarly an operator is determined by the formula
$$
\sum_ {n_\in\z}
\beta'_nz^n\dfn\frac {1} {1-az^ {-1}} \sum_ {n\in\z} \beta_nz^n,
$$
can be realized as an elementary recursive
filter $\beta'_n=\beta'_ {n + 1} a +\beta_n$.
\par
Laurent polynomials $Q_1$ and $Q_2$ in (5.1) can be represented
in the form
$$
Q_1 (z) =Az^ {l_1} \prod_ {i=1} ^ {d (Q_1)} \left (1-\left (\frac {a_i} {z}
\right) ^ {\sign (1- | a_i |)} \right),\quad Q_2 (z) =Bz^ {l_2} \prod_ {i=1} ^
{d (Q_2)} \left (1-\left (\frac {b_i} {z} \right) ^ {\sign (1- | b_i |)}
\right),
$$
where $\{a_i\} $, $\{b_i\} $ are roots of the polynomials $Q_1$ and $Q_2$, and
without loss of generality
the factors $Az^ {l_1} $ and $Bz^ {l_2} $ can
be considered equal to the identity. We note
that the roots of the polynomials $Q_1$ and $Q_2$ cannot be equal to the identity
by modulus, because in this case, on the one hand, we
have unstable filters, and on
the other hand, such functions $h$ and $\tilde h$ obviously does not
correspond to any biorthogonal pair of MRA.
Hence, multiplication by a diagonal matrix in the formula (5.1)  can
be realized with the help of $d (Q_1) + d (Q_2) $  elementary
recursive filters. Therefore the average computational complexity of all
recursive filters are equal to $d (Q_1) + d (Q_2) $.
Thus, total computational complexity
of a direct realization of formula (5.1) constitutes
$d (E_1) + d(O_1) + d (E_2) + d (O_2) + d (Q_1) + d (Q_2) + 3$
operations per a signal sample.
\par
The computational complexity for lifting realization of 
formula (5.1) are represented in the following statement.
\proclaim {Theorem 3}
The computational complexity of lifting  realization of the formula (5.1)
does not exceed $\Cal D (P) + 3d (Q_1) + 3d (Q_2) + 3$
operations per a signal sample.
\endproclaim
\remark {Remark 1} If $h (z) $ and $\tilde h (z) $ are Laurent polynomials,
then as
a special case of the Theorem 3 we obtain, that the complexity is equal to
$\Cal D (P) + 3$, that is result, obtained in  [3] and [6].
\endremark
%\remark {a Note 2} the lifting - realization not without fail conducts(leads)
%к to a prize in computing expenditures. In the elementary case, when
%$E_1=O_2$, $E_2=O_1=1$, $Q_1=E_1-1$, $Q_2=E_1 + 1$, $d (E_1) =m$, $l (E_1)=0$,
%получим, that expenditures at an immediate realization
%равны $4m + 3$ of realizations, and after application one elementary
%лифтинга
%\endremark
\demo{Proof of Theorem 3}
According to  Theorem 1, in  formula (2.9) action of a polyphase matrix to
the signal vector can be represented as a product of
$\Cal D (P) $  elementary
liftings and matrix $P_0$ of a zero defect.
The action of each lifting
$T^\sigma (k, a) $ to a signal consists in multiplication of a half of
signal
samples by number $a$,  a shift of coordinates of the same samples by
$k$  positions and adding the result to the second half of samples.
Thus, the cost of one lifting is equal to one operation per a signal sample
(as it usually is a shift of coordinates is not included in computational
expenditures).
Thus, we obtain  
it is necessary $\Cal D (P) $ arithmetical operations
for realization $\Cal D (P) $ elementary liftings.
\par
Denoting by $E'_1$, $E'_2$, $O'_1$, $O'_2$ the numerators of the appropriate
elements of the matrix $P_0$, we obtain that for a realization of
multiplication by a matrix $P_0 (z) $ it is required at most $d (E'_1) + d
(E'_2) + d (O'_1) + d (O'_2) + d (Q_1) + d (Q_2) + 3$ operations per a sample.
But since the matrix $P_0$ has a zero defect, $d (E'_1) + d (O'_2) \le d
(Q_1) + d (Q_2) $ and $d (E'_2) + d (O'_1) \le d (Q_1) + d (Q_2) $, therefore
the total expenditures are estimated from above by the value
$3d (Q_1) + 3d(Q_2) + 3$. As was to be proved.
\enddemo
It is clear, that for lifting scheme
a possibility of
additional reduction of amount of arithmetical operations by one forth
in the case of symmetric sequences $h(z)$ and $\tilde h(z)$
follows from Theorem 2.
Such possibility appears
because of the fact,
that for a realization of each elementary lifting
one operation per a sample is required and it is visible from (4.7)
composition of two elementary liftings
$T^ + (m, a) $ and $T^ + (- (m + 1), a)$
can be realized for 1.5 operations per a sample
( 3 operations with a half of samples).
% ******
\head\S 6. Applications to image compression\endhead
%
\par
We begin from motivation of application of considered types of wavelets
to signal and image processing.
We consider an elementary digital device, for a realization of which
wavelet bases can be applied. This is an equalizer. It is
intended for frequency correction of a signal.
The principle of an operation consists in
the following. An initial signal $f (t) $ with a finite spectrum
(Fourier transform) is represented as a sum of signals
$f_0$, $f_1$,$f_2$,\dots,$f_n$, which have
disjoint spectra, located respectively on intervals
$ [0,\omega_1] $, $ [\omega_1, \omega_2 [$, $ [\omega_2, \omega_3 [$,\dots $
[\omega_n, \omega_ {n + 1}] $, the union of which covers
the whole spectrum of the signal $f$.
Then the obtained signals are summed with required weights $\alpha_k$,
that gives a signal $\tilde f=\sum \alpha_kf_k$ at the output of a device .
This problem can be solved by means of Fast Fourier Transform.
Computational complexity of such procedure is equal to $O (N\log N) $,
where $N$ is number of  signal samples.
Clearly that the computational complexity of algorithm can be reduced
due to a partition of a signal to short segments. However,
in this case 
the problem, connected to a glueing together of separate pieces after
processing, can occur.
\par
It is usually presupposed that the points $\omega_k$
form a logarithmic
scale, i\. e., $\omega_ {k + 1} /\omega_k=c$,
$k=1,2,\dots, n$. In the case when
$c=2$, it is conveniently to use representation of a signal $f$ in the form of
a sum of its
projections to some collection of spaces
$\tilde V^ {m} $, $\tilde W^ {m} $,
$\tilde W^ {m + 1} $,\dots, $\tilde W^ {m + n} $.
Where the operators of projection to
$\tilde W^ {m + k} $ should  well
approximate a bandpass filter,
passing  a harmonics in an
interval $ [\omega_k,\omega_ {k + 1} [$ without distortions
and damping  all remaining
harmonics.
Thus, the problem is reduced to a choice of $2\pi$-periodic function
$m_0$, approximating the function
$$
\chi (x) =\cases 1,\quad &| x | < \pi/2,\\0, &\pi/2\le | x |
\le\pi\endcases
$$
In  [12] in some sense optimal solutions
of this problem, when $m_0=\tilde m_0$
is polynomial of fixed degree were found. The optimality of a
choice consists in the fact that  
polynomial  solution which has as the
much as possible flat graph near to zero was chosen. It was
provided by the greatest
possible multiplicity of zero of derivative of a polynomial $m_0$
at points $0$
and $\pm\pi$. Such choice ensures a large absolute value of derivative
(so-called, steepness of a filter) at points $\pm\pi/2$.
\par
It is clear that the rational functions can approximate function
$\chi$ with a
much higher degree. As much as possible flat performance near to zero among
rational functions of an equal degree of a numerator
the functions $m_0 (\omega) =\tilde m_0 (\omega) =h (e^ {i\omega}) /\sqrt {2} $, constructed (see,
for example, [1]) on the base of Butterworth filters 
$$ H (z) h (z^ {-1}) =\frac {2 (1 + z^ {-1}) ^N (1 + z) ^N} {(z^ {-1} + 2 + z)
^N + (-z^ {-1} + 2-z) ^N},
$$
give.
\par
If to take for a comparison the Daubechies and Butterworth bases  with
functions $m_0$ with the same  multiplicity of zero  (equal to $N$)
at points 
$\pm\pi$, the corresponding algorithms of decomposition and reconstruction of
signals  have almost identical computational complexity.
At the same time the
ratio of  derivative of a function $m_0$ for the Butterworth wavelets
at points $\pm\pi$ for $N=2$ to the derivative of the Daubechies  wavelets
is equal to 4/3, and at $N=3$ is equal to 8/5. At growth $N$
the distinction derivatives becomes even more significant.
If the Butterworth  filter 
at $N=2$ ensures the same derivative (even a little bit large), as a
the Daubechies filter  at $N=3$, to receive the same derivative,
which gives a
filter of a Butterworth at $N=3$, it is required to take the Daubechies filter
of order 7.
\par
Unfortunately, a similar sort of the simple argumentation
cannot be serious argument
for the benefit of application of any bases to problems of
 image compression. At the present there are no justified
reasons about quantitative characteristics of bases,
which influence a degree of compression.
One of such properties, which is presented in majority of the
publications, is a multiplicity of zero of functions
$m (\omega) $ and $\tilde
m (\omega) $ at points $\pm\pi$. It is accepted to consider, that
increasing a multiplicity of zero leads to increasing of
possible compression factor for images.
Our research, the results of which are presented below,
refutes this
statement in some respects.
\par
We have conducted numerical simulation for comparison the bases
described in \S 3 and best biorthogonal pairs of  compact supported bases
for their effectiveness for image compression.
\par
All studies were carried out for 8-bit (256 grades of grey) images.
An image as the function of two variables was periodized by means  of a
mirror prolongation beyond the edges and then was represented
as coefficients of
expansion in wavelet bases, which were a tensor product (see, for example,
[4, Chapter 10]) of one-dimensional bases.
\par
The obtained coefficients were coded by algorithm SPIHT [13]
without additional arithmetic coding.
For reconstruction of an image an initial segment of a code of
required length was taken. The reconstruction was carried out
by  code segments of a length
equal to from 1/10 up to 1/150 of a file length which is necessary
to keep 
image
in a
standard format, requiring 1 byte per a pixel.
\par
The measured in decibels  peak  signal-to-noise ratio (PSNR),
determined  by the formula
$$
PSNR=10\lg\frac {255^2}{\sum_ {i=1} ^N\sum_ {j=1} ^M | x_ {ij} -\tilde x_ {ij}|^2},
$$
where $x_ {ij} $, $\tilde x_ {ij} $ are integers in bounds from 0 up to 255,
defining value of intensity  of a pixelя with coordinates
$ (i, j) $ accordingly for original and for a reconstructed image,
was taken as a criterion for the quality of a reconstructed image.
\par
Among the investigated  bases, associated with recursive filters,
the  biorthogonal pair 
$$
h (z) =\frac {1 + z} {\sqrt2},\qquad g (z) =\frac {z^ {-3} -3z^ {-2} + 3z^ {-1}
-1} {4\sqrt {2}}, $$
$$
\tilde h (z) =\frac {(1 + \alpha) ^2} {4\sqrt {2}} \frac {z^ {-1} + 3 + 3z +
z^2} {(1 + \alpha z^2) (1 + \alpha z^ {-2})}, $$
$$
\tilde g (z) =\frac {(1 + \alpha) ^2} {\sqrt {2}} \frac {-z^ {-2} + z^ {-1}}
{(1 + \alpha z^2) (1 + \alpha z^ {-2})}, $$
where $\alpha=3-2\sqrt {2} $, has given the best
results for compression.
Such pair allows to reach approximately the same
compression factors as the best
of known bases with finite masks (for example, 9/7-wavelets from [2]).
The difference in PSNR for the given pair and
9/7-bases for overwhelming majority of images is in range $\pm0.3$ dB.
However,
our algorithm has significant advantage in computational complexity.
\par
The standard pyramidal algorithm of expansion of an one-dimensional signal
in
9/7-bases has complexity 14 operations (see [3]) of addition
and multiplication per
a signal sample. As much of operations it is required for reconstruction
of a signal by the coefficients.
We show, that our algorithm can be realized for 7 operations per a signal
sample for decomposition of an one-dimensional signal  and for 11
operations per a sample for reconstruction.
\par
The standard realization of image expansion  in
two-dimensional wavelet bases,
consists in a sequential realization of one-dimensional algorithms at
first for rows of an image and then  for columns. Thus, the relationships of
computational complexity for different bases are kept after passage to
two-dimensional algorithms.
\par
The polyphase matrices of algorithms of decomposition and reconstruction
have the form
$$
P (z) =\frac {1} {\sqrt2} \pmatrix 1 &z\\%\dsize
-\frac{3z^ {-1} -1}{4} %\dsize.
&\frac{z^ {-1} + 3}{4} \endpmatrix,
\tilde P (z) =
\frac {(1 + \alpha) ^2}{\sqrt2
( 1 + \alpha z^ {-1}) (1 + \alpha z)} \pmatrix
%\dsize
\frac {3 + z} {4}
%\dsize
&\frac {1 + 3z} {4}
\\-z^ {-1} &1
\endpmatrix.
$$
That does not allow to use outcomes \S 4 for  realization of
algorithms of expansion and restoration directly .
We note, that the reason is not that matrices $P (z) $ and
$\tilde P(z) $ in view of transfer of a polynomial from a denominator
of the second row
of the matrix $P$ to a denominator of the second row
of the matrix $\tilde P$ have a determinant different from the identity,
but in view of the fact that  before transfer of
a polynomial  the initial matrices have zero defects. That does
senseless application of  Theorem 1.
Thus, probably, for  realization
of one-dimensional algorithm of decomposition
it makes a sense to use the direct form of decomposition algorithm
(without passage to a polyphase matrix),
which in view of a symmetry of filters requires 7 operations
per a signal sample.
\par
As to algorithm of reconstruction, despite above mentioned argument,
we were succeed
in finding a lifting  factorization
$$
\tilde P (z) = \pmatrix
1 %\dsize.
&\frac {1 + 3z} {4} \\0 &1
\endpmatrix
\pmatrix
\sqrt2 &0\\0 %\dsize.
&\frac {(1 + \alpha) ^2} {\sqrt2}
\endpmatrix
\pmatrix
1 &0\\0 %\dsize.
&\frac {1} {(1 + \alpha z^ {-1}) (1 + \alpha z)} \endpmatrix
\pmatrix
1 &0\\-z^{-1} &1 \endpmatrix.
$$
It can be seen from here, the computational complexity
of such algorithm are equal
11 operation per a signal sample.
We note, that the direct form of a
realization of reconstruction algorithm  requires 15 operations per a sample.
\par
In summary we  mark, that the filters $h (z)$ and $\tilde h (z) $,
considered in this section,
really generate a biorthogonal pair of bases of the space
$\Lt$. Unfortunately, we do not know   any general result,
from which
the given fact would immediately follows.
One of the first results about a
sufficient condition for existence of orthogonal wavelet basis,
corresponding
to some filter $h (z) =\tilde h (z) $ and satisfying the equation (2.7),
belongs to S.Mallat [14].
\par
Though we deal with biorthogonal pairs $h$ and $\tilde h$ and
we can not use the mentioned sufficient condition, however,
in our case in view of a positivity 
of functions $m_0$ and $\tilde m_0$ on an interval
$ (-\pi,\pi) $ a Mallat's proof 
for our pair of recursive
filters
passes without essential modifications.

\Refs%\nofrills {the Literature}

\ref\no {1}
\by Herley C., Vetterli M. \paper {\ Wavelets and recursive filter banks} IEEE
Trans. On Signal Proc. \vol 41 \yr1993 \issue 8 \pages 2536 -- 2556 \endref

\ref\no {2}
\by Cohen A., Daubechies I., and Feauveau J.-C. \paper {Biorthogonal bases of
compactly supported wavelets}
Commun. Pure Appl. Math. \vol 45 \yr1992 \pages 485 -- 560 \endref

\ref\no {3}
\by Daubechies I., Sweldens W.
\paper {Factoring wavelet transforms into lifting steps} \jour J. Fourier Anal.
Appl.\vol 4\yr 1998\issue 3 \pages 247 -- 269 \endref
\ref\no {4} \by Daubechies I.\book {Ten Lectures on Wavelets} \publ SIAM,
Philadelphia
\yr1992
\endref
\ref\no {5}
\by Cohen A., Daubechies I. \paper {Nonseparable biorthogonal bases}
\jour Rev. Mat. Iberoam. \vol 9 \issue 1 \pages 51 -- 137 \yr 1993 \endref
\ref\no {6}
\by Borac S., Seiler R.
\paper {Loop group factorization of biorthogonal wavelet bases} \publ Report
\yr 1997 \endref
\ref\no {7}
\by Strang G., Nguyen T.Q. \book {Wavelets and Filter Banks} \publ
Wellesley-Cambridge Press \yr 1996 \endref
\ref\no {8}
\by Petukhov A.P. \paper Periodic wavelets \jour  Mat.
Sborn. \vol 188\yr 1997\issue 10 \pages 69 -- 94;
\transl Engl.transl. in {\it Sbornik: Mathematics} {\bf 188} (1997),
1481 -- 1506
\endref
\ref\no {9}
\by  Petukhov A.P. \paper  Multiresolution analysis and wavelet 
decompositions of spaces of periodic distributions \jour Docl. Rossiisk.
Akad. Nauk \vol 356\yr
1997\issue 2 \pages 303 - 306 \endref
\ref\no {10}
\by Petukhov A.P. \paper Periodic discrete wavelets \jour Algebra and
analysis \vol 8 \yr1996 \issue 3 \pages 151 - 183
\transl Engl.transl. in {\it St. Petersburg Math. J.} {\bf 8} (1997),
481 -- 503
\endref
\ref\no {11}
\by Skopina M.A.\paper Multiresolution analysis of periodic functions \jour
East Journal on Approximation \vol 3\issue 2\yr 1997 \pages 203 - 224 \endref
\ref\no {12}
\by Daubechies I.\paper {Orthogonal bases of compactly supported wavelets}
\jour Comm. Pure and Appl. Math.\vol 41\yr 1988\pages 909 - 996 \endref
\ref\no {13}
\by Pearlman W., Said A. \paper {A new fast and efficient image codec based on
set partitioning in hierarchical trees} \jour IEEE Trans on Circuits and
Systems for Video Tech. \vol 6 \yr 1996 \endref
\ref\no {14}
\by Mallat S. \paper Multiresolution approximations and wavelet orthonormal
bases of $\Lt$ \jour Trans. Of the Amer. Math. Soc.\vol 315\issue 1\yr1989
\pages 69 - 87 \endref
\ref\no {15} \by Meyer F.G., Averbuch A., Str\"omberg J.-O. \paper {Fast
adaptive wavelet packet image compression} \publ Report\yr 1998
\endref

\end