Splitting a Matrix of Laurent Polynomials with Symmetry and its Application to Symmetric Framelet Filter Banks.
Let M be a $2\times 2$ matrix of Laurent polynomials with real coefficients and symmetry. In this paper, we obtain a necessary and sufficient condition for the existence of four Laurent polynomials (or finite-impulse-response filters) u1, u2, v1, v2 with real coefficients and symmetry such that   $$ \left[ \begin{matrix} u_1(z) &v_1(z)\\ u_2(z) &v_2(z) \end{matrix}\right] \left[ \begin{matrix} u_1(1/z) &u_2(1/z)\\ v_1(1/z) &v_2(1/z)\end{matrix}\right]=M(z) \qquad \forall\; z\in \CC \bs \{0 \} $$   and [Su1](z)[Sv2](z)=[Su2](z)[Sv1](z), where [Sp](z)=p(z)/p(1/z) for a nonzero Laurent polynomial p. Our criterion can be easily checked and a step-by-step algorithm will be given to construct the symmetric filters u1, u2, v1, v2. As an application of this result to symmetric framelet filter banks, we present a necessary and sufficient condition for the construction of a symmetric multiresolution analysis tight wavelet frame with two compactly supported generators derived from a given symmetric refinable function. Once such a necessary and sufficient condition is satisfied, an algorithm will be used to construct a symmetric framelet filter bank with two high-pass filters which is of interest in applications such as signal denoising and image processing. As an illustration of our results and algorithms in this paper, we give several examples of symmetric framelet filter banks with two high-pass filters which have good vanishing moments and are derived from various symmetric low-pass filters including some B-spline filters.
and high-pass filters, refinable functions.
AMS subject classifications. 15A23, 15A54, 42C40
1. Introduction and Motivation. Matrix theory plays an important role in
wavelet analysis [4] and filter banks [17, 18]. In this paper, we are interested in splitting
of Laurent polynomials with real coe#cients and symmetry into the
form U(z)U(1/z) T for some 2-2 matrix U whose entries are Laurent polynomials with
real coe#cients and symmetry. Our investigation on this matrix splitting problem is
greatly motivated by the recent development of symmetric tight wavelet frames and
framelet filter banks which have been found to be useful and interesting in many
applications [1]-[15]. In the following, let us review some necessary background and
explain our motivation to study this problem.
Since Daubechies constructed her famous family of compactly supported orthonormal
wavelet bases in 1988, wavelets have been extensively studied and successfully
applied to many areas. Though orthonormal wavelet bases have many desired
properties in applications, as Daubechies pointed out in [4], except the Haar wavelet
which is discontinuous, there is no compactly supported real-valued continuous orthonormal
wavelet basis that can have symmetry. However, in many applications, for
various purposes, symmetry is a much desired property. In order to achieve symmetry
in a wavelet system or a wavelet filter bank, many generalizations of orthonormal
wavelet bases have been proposed and investigated in the literature [4, 18]. In this
Research was supported by the Natural Science and Engineering Research Council of Canada
(NSERC Canada) under Grant G121210654.
Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta,
Canada T6G 2G1 (bhan@math.ualberta.ca, http://www.ualberta.ca/#bhan).
# Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta,
Canada T6G 2G1 (mo@math.ualberta.ca, http://www.math.ualberta.ca/#mo).
Han and Qun Mo
paper, we are particularly interested in tight wavelet frames and framelet filter banks
which currently stimulate a lot of interest in both theory and application due to their
particular interesting features [1]-[15]. As a generalization of an orthonormal wavelet
basis, a tight wavelet frame is an overcomplete wavelet system that preserves many
desirable properties of an orthonormal wavelet basis. See Selesnick [15] for discussion
on applications and interesting features of tight wavelet frames and framelet filter
banks.
Before proceeding further, let us review some definitions and notation. We say
that a set {# 1 , . , # r
} of functions in L 2 (R) generates a (normalized) tight wavelet
frame in L 2 (R) if
r
where #f, g# R f(x)g(x) dx and #f# 2 := #f, f#. The set {# 1 , . , # r
} is called a
set of generators for the corresponding tight wavelet frame. Let # denote the Dirac
sequence such that # In particular, if {# 1 , . , # r
generates a tight wavelet frame and #
} generates an orthonormal wavelet basis
in L 2 (R). It follows directly from (1.1) that any function f # L 2 (R) has the wavelet
In order to have a fast algorithm, one is interested in tight wavelet frames which
are derived from refinable functions via the multiresolution analysis (MRA). We
say that a function # is refinable if -
#) for a Laurent polynomial
a with is called the mask for the refinable function # and is also
called a low-pass filter in engineering), where the Fourier transform is defined to
be -
(R) and can be naturally extended to tempered
distributions. We usually normalize a refinable function # by -
Throughout this paper, we assume that all Laurent polynomials have real coef-
ficients. In other words, all the filters discussed in this paper are of finite-impulse-
response (FIR) and have real coe#cients.
As an important family of refinable functions, B-spline functions are useful in
applications. The B-spline function of order n (n # N), denoted by Bn throughout
this paper, can be obtained via the recursive formula: B 1 := # [0,1] , the characteristic
function of the interval [0, 1], and Bn (x) := # 1
2. The B-spline
function Bn # C n-2 (R) is a symmetric refinable function satisfying
Bn (#) for # R.
In order to obtain an orthonormal wavelet basis from a refinable function # via the
multiresolution analysis, the refinable function # must satisfy the following condition
([4,
By a simple argument, (1.2) implies that its mask a must satisfy the condition ([4,
If (1.2) holds, one can define a wavelet function by -
#). Then
{#} generates an orthonormal wavelet basis in L 2 (R) (see [4]). Note that the Haar
wavelet is derived from the B-spline function B 1 which is discontinuous.
Matrix Splitting with Symmetry and Framelet Filter Banks 3
The conditions in (1.2) and (1.3) impose a very restrict constraint on a refinable
function and its low-pass filter. Many refinable functions such as the B-spline
functions Bn (n > 1) do not satisfy (1.2). In fact, up to an integer shift, B 1 is the
only example of real-valued compactly supported refinable function that can have
symmetry and satisfy (1.2) (see [4]).
As discussed above, an orthonormal wavelet basis has only one generator. By
increasing the number of generators in a tight wavelet frame, recently it was found
that one has a lot of freedom in the construction of tight wavelet frames derived from
refinable functions which may not satisfy the condition in (1.2). For example, it was
demonstrated in Ron and Shen [14] that from any B-spline function of order n, one
can construct a symmetric tight wavelet frame with n generators. More recently, Chui
and He [1] (also see Petukhov [12]) showed that if the mask a for a symmetric refinable
function satisfies
then one can derive a symmetric tight wavelet frame with three generators. Recently,
Daubechies et al. [6] and Chui et al. [2] obtained the following interesting procedure
that yields all possible MRA tight wavelet frames derived from a refinable function.
Theorem 1.1. Let # be a refinable function in L 2 (R) such that -
#)
for a Laurent polynomial a with Suppose that there exist Laurent polynomials
#, a 1 , . , a r such that
# a 1 (z) - a r (z)
a 1 (-z) - a r (-z) #
a 1 (1/z) a 1 (-1/z)
a r (1/z) a r (-1/z)
where
z # C\{0}.
Define the wavelet functions # 1 , . , # r by
} generates a tight wavelet frame in L 2 (R).
According to Theorem 1.1, a framelet filter bank consists of a low-pass filter a
and r high-pass filters a 1 , . , a r . In order to design a framelet filter bank, one has to
split the matrix M# in (1.6) into the form of (1.5).
Using Theorem 1.1, it was demonstrated in [2] (also c.f. [6]) that for any refinable
function # L 2 (R) whose integer shifts are stable, one can obtain an MRA tight
wavelet frame with two generators. Unfortunately, when # is symmetric, the construction
in [2, 6] cannot guarantee the symmetry of the two constructed generators
which do not have symmetry in most cases.
Though by increasing the number of generators in a tight wavelet frame one
has a great deal of freedom to construct them from refinable functions, in many
applications, for various purposes such as computational cost and storage concern,
one prefers a symmetric tight wavelet frame with as small as possible number of
generators (or equivalently, high-pass filters). Ideally, a tight wavelet frame with a
single symmetric generator is desirable. However, as shown in [2, 6], it is impossible to
have an MRA symmetric tight wavelet frame with one continuous generator. All the
4 Bin Han and Qun Mo
above discussions naturally motivate us to consider construction of symmetric MRA
tight wavelet frames with two generators (that is, symmetric framelet filter banks
with two high-pass filters) for the following possible advantages.
1. Such framelet filter banks have symmetry which is a much desired property in
applications.
2. By using two high-pass filters, one still has much freedom to construct symmetric
framelet filter banks from many low-pass filters without imposing strict
conditions on them.
3. By limiting to two high-pass filters, the associated framelet transform for decomposition
and reconstruction is e#cient in terms of computational and storage
costs.
4. Such symmetric framelet filter banks can have good vanishing moments, short
support and many other desired properties.
In order to construct a symmetric framelet filter bank with two high-pass filters,
according to Theorem 1.1, the core problem is to find two symmetric high-pass filters
a 1 and a 2 such that (1.5) holds with 2. In other words, we have to split the 2 - 2
matrix M# of Laurent polynomials into the desirable form in (1.5). This motivates us
to investigate the problem of splitting a matrix of Laurent polynomials with symmetry
which may be of interest in other applications such as construction of symmetric
orthonormal multiwavelets and dual framelet filter banks [2, 5, 6].
The following is an outline of this paper. In Section 2, we shall present a general
result on splitting a matrix of Laurent polynomials with symmetry. As an application
of this result to symmetric framelet filter banks, we shall present a necessary and
su#cient condition for the construction of a symmetric tight wavelet frame with two
generators derived from a given symmetric refinable function through Theorem 1.1.
Once the necessary and su#cient condition is satisfied, we shall present a step-by-step
algorithm (see Algorithm 2.5 in Section 2) to derive the two symmetric high-pass filters
from a given low-pass filter. In Section 3, we shall present some examples of symmetric
framelet filter banks with two high-pass filters which are derived from various low-pass
filters including some B-spline filters. Our work in this paper was also motivated by
[11, 13, 15] where symmetric tight wavelet frames with two generators were considered
but using the unitary extension principle in [14], which is a special case of Theorem 1.1
by taking 1. In this paper, we shall generalize [13] by considering the general
fundamental function # instead of the special case As discussed in [2, 6], a
nonconstant # is very important in order to have a tight wavelet frame with good
vanishing moments. Also, in order to use the unitary extension principle, the mask
must satisfy (1.4) which excludes some interesting low-pass filters ([1, 2, 6, 11, 12]).
We shall see that by using the general construction in Theorem 1.1 the investigation
of symmetric tight wavelet frames and symmetric framelet filter banks becomes much
more complicated. This paper is also motivated by [9], which proves that one can
derive from any B-spline function of order m (m # N) an MRA tight wavelet frame in
which is generated by the dyadic dilates and integer shifts of three compactly
supported real-valued symmetric wavelet functions with vanishing moments of the
highest possible order m. For multivariate tight wavelet frames, see Han [7] and
references therein.
In Section 3, by using Algorithm 2.5 and Theorem 1.1 we shall give examples
to show that symmetric framelet filter banks with two high-pass filters having good
vanishing moments can be constructed. For applications of framelet filter banks, see
[15]. In order to prove the main results in this paper, in Section 4, we shall provide
Matrix Splitting with Symmetry and Framelet Filter Banks 5
some auxiliary results. In Section 5, we shall prove our main result on splitting
a matrix of Laurent polynomials with symmetry. Though the whole proof of the
main result is somewhat technical, we shall present a step-by-step algorithm (see
Algorithm 5.1 in Section 5) to implement the main result on splitting a matrix of
Laurent polynomials with symmetry which may be of interest in other applications.
2. Main Results. In this section, we shall present the main results of this
paper. We shall obtain a general result on splitting a matrix of Laurent polynomials
with symmetry. As an application of such a result, we shall give a necessary and
su#cient condition for the construction of symmetric MRA tight wavelet frames with
two compactly supported generators. A step-by-step algorithm (Algorithm 2.5) will
be given for construction of symmetric framelet filter banks.
In order to state the results in this section, let us introduce some notation first.
We remind the reader that all of the Laurent polynomials discussed in this paper
have real coe#cients and we say that a Laurent polynomial p with real coe#cients
is symmetric (or antisymmetric) about k/2 for some k # Z if
p(1/z)). Throughout this paper, we say that a Laurent polynomial p is
(anti)symmetric if p is either symmetric or antisymmetric. For a nonzero Laurent
polynomial p, we define an operator S to be
When p # 0, by convention Sp is undefined and can be anything.
The following result can be easily verified.
Proposition 2.1. Let p and q be two Laurent polynomials with real coe#cients.
Then
(1) p is (anti)symmetric about k/2 for some k # Z if and only if
and q are (anti)symmetric such that
and S(p -
For a nonzero Laurent polynomial
we denote the degree of p by In other words, deg(p) measures the length
of the filter p. By convention, -#. For any two Laurent polynomials p and
q, we say that p | q if there is another Laurent polynomial h such that
for all z # C\{0}. We define gcd(p, q) to be a nonzero Laurent polynomial h with
maximum degree such that h | p and h | q. By convention, gcd(0, We say that
a Laurent polynomial p is trivial if Z. Up to
a factor of a trivial Laurent polynomial, gcd(p, q) is unique.
In the terminology of digital signal processing, the symmetries of filters are classified
into Type I to Type IV filters according to whether the filter is symmetric or
antisymmetric with an even or odd degree. The operator S defined in (2.1) is very
useful in this paper to distinguish these four types of symmetries of filters. See Table 1
for more more detail.
Proposition 2.2. Let
be a Laurent
polynomial with real coe#cients. Then
Laurent polynomial d with real coe#cients if and only if
the Laurent polynomial dA which is uniquely determined by one of the following four
cases:
6 Bin Han and Qun Mo

Table
Type I to Type IV symmetries of a filter p described in terms of the operator S defined in (2.1).
In this table, k is an integer and even (or odd) means the filter p has an even (or odd) degree.
Type I Type II Type III Type IV
symmetric/odd symmetric/even antisymmetric/odd antisymmetric/even
Case 1: When
Case 2: When
Case 3: When
Case 4: When
are uniquely determined by the following recursive formula: c n :=
|AN | and
c n-j :=2c n
Moreover, if for an (anti)symmetric Laurent polynomial d with
real coe#cients, then we must have Z. Therefore, the
symmetry type of the filter d is completely determined by the degree of A and the sign
of the leading term of A.
Proof. If a Laurent polynomial d is (anti)symmetric and satisfies
then it is easy to see that Z. By comparing the coe#-
cients of A(z) and dA (z)d A (1/z), all the claims can be easily verified.
A similar algorithm for Proposition 2.2 also appeared in [16].
For a matrix M , we denote by M j,k the (j, k)-entry of the matrix M . For a
Laurent polynomial p, we denote by Z(p, z 0 ) the multiplicity of zeros of p at
that is,
| p(z)}. (2.3)
Now we are ready to state the main results in this paper.
Theorem 2.3. Let A, B and C be (anti)symmetric Laurent polynomials with
real coe#cients. Denote a 2 - 2 matrix M by
Then there exist (anti)symmetric Laurent polynomials
cients such that
and
if and only if all the following conditions are satisfied:
Matrix Splitting with Symmetry and Framelet Filter Banks 7
(a) The matrix M(z) is positive semi-definite (that is, M(z) # 0) for all z # T.
Laurent polynomial d with real
coe#cients.
(c) C). If both B and d are not identically zero, then the
matrix M satisfies the following "gcd" condition, that is, one of the following
conditions must be true:
(1) If is an even number
for every x # (-1,
(2) If is an even
number for every x # (0, 1).
(3) If there is no condition on
g.
is an even
number for every x # (-1, 0).
We shall prove Theorem 2.3 in Section 5 in a constructive way and a step-by-step
algorithm (see Algorithm 5.1) will be given to construct the desired filters
from the matrix M . We shall also show that the "gcd" condition in Theorem 2.3
cannot be removed. Note that by Proposition 2.1 and (2.5), it is easy to see that
is equivalent to
As an application of Theorem 2.3 to symmetric framelet filter banks, we have
the following result for constructing symmetric MRA tight wavelet frames with two
generators.
Theorem 2.4. Let # L 2 (R) be a refinable function satisfying -
#)
for a symmetric Laurent polynomial a with real coe#cients such that
be a Laurent polynomial with real coe#cients such that
Let M# be defined in (1.6). Then there exist two (anti)symmetric Laurent polynomials
a 1 and a 2 with real coe#cients such that (1.5) in Theorem 1.1 holds with
and only if the following conditions are satisfied:
(a) M# (z) # 0 for all z # T. (This condition can be replaced by #(z) # 0 for all
z # T.)
(b) detM# for an (anti)symmetric Laurent polynomial d with real
coe#cients.
(c) The matrix M# satisfies the following
"gcd" condition, that is, one of the following conditions must be true:
(1) If is an even
number for every x # (-1,
(2) If is an even number
for every x # (0, 1).
(3) If there is no condition
on g.
is an even
number for every x # (-1, 0).
Proof. Let us make some connections to Theorem 2.3 first. With
becomes
a 1 (-z) a 2 (-z) # . (2.8)
8 Bin Han and Qun Mo
Since the mask a is symmetric, we have Z. Inspired by the
idea of polyphase decomposition, we define
z -z
Now (2.8) can be rewritten as
with
When k is even, by computation we have
and
It is easy to see that -
W (z) and
M(z).
So, U and M are well-defined. Moreover, It is easy to see that M 1,2 # 0 and
When k is odd, by computation we have
and
It is clear that -
W (z) and -
M(z). So, U and M are well-defined.
Moreover, It is easy to see that M 1,2 # 0 and [SM 1,2
By the definition of P and the definition (2.11), we have
and
Matrix Splitting with Symmetry and Framelet Filter Banks 9
where
By the discussion above, we can clearly see the relation between conditions (a), (b)
and (c) in Theorem 2.3 and conditions (a), (b) and (c) in this theorem, respectively.
Based on the relation, we will prove the necessity and su#ciency respectively.
Necessity. Suppose that there exist two (anti)symmetric Laurent polynomials a 1
and a 2 with real coe#cients such that (1.5) holds, by (2.8) we have M# (z) # 0 for all
z # T and therefore condition (a) holds. Note that detW (z). Thus we
can define a Laurent polynomial d by d(z 2
We now show that d is (anti)symmetric. Since a 1 and a 2 are (anti)symmetric, we
have [Sa 1
By (2.8) and (1.6), we have
a
Note that
and similarly, S[a 2 (z)a 2
by a simple argument, it follows from (2.14) that
(Note that there are at least two even (or odd) numbers among k 1 , k 2 and k. Say,
are even. Then by item (4) in Proposition 2.1, we conclude that (-1) k1 =
.) Note that detW
by Proposition 2.1, we conclude that
So, detW is (anti)symmetric and therefore, by d(z 2
Hence condition (b) holds.
Recall that When k is even, By Proposition 2.1 and the fact that
it follows from (2.12) that
Thus, when k is even, (2.5) and (2.6) are satisfied. Since P (z)P (1/z) must
have
Han and Qun Mo
and k is an even integer. Therefore, by Theorem 2.3, condition (c) must be true.
When k is odd, by Proposition 2.1 and the fact that (-1) k1 = (-1)
-1, it follows from (2.13) that
Thus, when k is odd, (2.5) and (2.6) are satisfied. Note that
and k is an odd integer. Therefore, by Theorem 2.3, condition (c) must be true.
Su#ciency. Suppose that conditions (a), (b) and (c) in this theorem are satisfied.
From the discussion before the necessity part, applying Theorem 2.3 on M(z), we
know that there exist (anti)symmetric Laurent polynomials
coe#cients such that (2.5) and (2.7) hold. Define
# a 1 (z) a 2 (z)
We show that a 1 and a 2 must be (anti)symmetric. Since
we have
a
By [SM 1,2 it follows from (2.7) that
and 2.1, we have [Sa 1
and [Sa 2 are (anti)symmetric, so are the Laurent
polynomials a 1 and a 2 .
When k is odd, we have
a
and
a
By [SM 1,2 it follows from (2.7) that
Proposition 2.1, we deduce that
are
(anti)symmetric, so are the Laurent polynomials a 1 and a 2 . Now it is straightforward
to verify that (2.8) holds.
In order to construct symmetric framelet filter banks with two high-pass filters,
by the proof of Theorem 2.4, we present the following algorithm.
Algorithm 2.5. Let a be a symmetric Laurent polynomial with real coe#cients
such that (that is, a is a low-pass filter). Suppose that we have a Laurent
polynomial # such that all the conditions in Theorem 2.4 are satisfied.
Matrix Splitting with Symmetry and Framelet Filter Banks 11
Compute the symmetry center of the low-pass filter a: [Sa](z) :=
for some integer k. Define the 2-2 matrix P in (2.9) according to the parity
of the integer k.
Calculate the defined in
(1.6).
Using Algorithm 5.1 in Section 5 to split the matrix M into the desired form:
and
In most cases g(z 2 consequently,
by solving a system of linear equations, we have all the symmetric filters
Obtain the symmetric high-pass filters a 1 and a 2 by
Then (2.8) holds and we have a symmetric framelet filter bank consisting of a low-pass
filter a and two high-pass filters a 1 and a 2 .
In order to design a desired filter # such that all the conditions in Theorem 2.4
are satisfied, quite often one constructs a # such that
and
where d is determined in Proposition 2.2. In most cases the "gcd" condition in Theorem
2.4 is automatically satisfied. More explicitly, we usually set
unknown parameters c 1 , . , c n . So, we automatically
have 1. Then we obtain some equations for the unknowns c 1 , . , c n from
the condition detM(z 2 2.2. Solving such equations for
the unknowns c 1 , . , c n , we see that the desired condition detM(z 2
holds. Finally, we check the two conditions #(z) # 0 and the "gcd" condition which
quite often turn out to be satisfied automatically.
Suppose that the low-pass filter a is given. Theorem 2.4 gives us a necessary
and su#cient condition on # to construct a symmetric framelet with two high-pass
FIR filters. If we have found a desired # such that conditions (a), (b) and (c) in
Theorem 2.4 hold, then we can use Algorithm 2.5 to construct two symmetric high-pass
filters a 1 and a 2 . Since we have some freedom in constructing a 1 and a 2 from
a and #, it is of interest to know what are all the possible symmetry types for these
two high-pass filters a 1 and a 2 . We shall see in the following result that the symmetry
types of the high-pass filters a 1 and a 2 are completely determined by a and #.
Theorem 2.6. Let # L 2 (R) be a refinable function satisfying -
#)
for a symmetric Laurent polynomial a with real coe#cients such that
be a Laurent polynomial with real coe#cients such that
Suppose that conditions (a), (b) and (c) in Theorem 2.4 are satisfied. Let a 1 and a 2
Han and Qun Mo
be two (anti)symmetric Laurent polynomials with real coe#cients such that (1.5) in
Theorem 1.1 are satisfied with 2. Denote
for some # 1 , # 2 # {-1, 1} and for some integers k, k 1 and k 2 . Then k, k 1 and k 2
have the same parity (that is, are even integers) and one of the
following two cases must be true:
(a) If
antisymmetric and # 2 is symmetric) or #
and # 2 is symmetric);
(b) If
In conclusion, up to a trivial switch of the two high-pass filters a 1 and a 2 , the symmetry
types of the filters a 1 and a 2 are completely determined by the low-pass filter a and
the filter #.
Proof. We use the the proof of the necessity part of Theorem 2.4 . As in the proof
of Theorem 2.4, we must have
Therefore, both a 1 and a 2 have even degrees if a has an even degree, or, both a 1 and
a 2 have odd degrees if a has an odd degree. Thus, we only need to prove that up
to a trivial switch of the two high-pass filters a 1 and a 2 , the numbers # 1 and # 2 are
completely determined by the low-pass filter a and the filter #. In the proof of the
necessity part of Theorem 2.4, we proved that (2.16) must be true. By Proposition 2.2
and detM# we know that [Sd](1) depends only on a and #. Con-
sequently, we can assume that d(z 2 it follows from (2.16) that
we must have
If it follows from (2.17) that # 1 therefore, we
have either #
from (2.17) that # 1 To complete the proof, it su#ces to consider the case
1. In this case, we must have
{-1, 1}. It is easy to see that
Then we have #
lim
a
By (2.8) and (1.6), we have
a
Thus, we have depends only on a and
#. Therefore, # 1 and # 2 depend only on a and #.
Matrix Splitting with Symmetry and Framelet Filter Banks 13
3. Some Examples of Symmetric Framelet Filter Banks. First, we illustrate
that the "gcd" condition in Theorem 2.4 cannot be removed. Then by Algorithm
2.5 we provide several examples of symmetric framelet filter banks with two
high-pass filters. In Theorem 2.4, the "gcd" condition seems unnatural. One may
conjecture that the "gcd" condition will be automatically satisfied if M# (z) # 0 for
all z # T and detM# Laurent polynomial
d. The following example shows that this conjecture is not true.
Example 3.1. Let the low-pass filter a be given by
where c 1 # 0.07391 is a root of x 8 +8x 7 +35x 6 +58x 5
By a simple calculation, it is easy to verify that the refinable function # with the
mask a lies in L 2 (R) and in fact is a continuous function. Define b := c 2+ 2c 1 - 1,
f(z) := 1+b(2-z-z -1 )/4 and #(z) := f(z 2 )f(z). It is easy to verify that M# (z) # 0
for all z # T and detM# Laurent polynomial
d such that
By a simple computation, we have Z(g, x
the "gcd" condition fails while conditions (a) and (b) in Theorem 2.4 are satisfied.
Therefore, the "gcd" condition in Theorem 2.4 cannot be removed.
In the following, let us apply Algorithm 2.5 to obtain several examples of symmetric
framelet filter banks with two high-pass filters.
Example 3.2. Let be the B-Spline function of order 3. It is known that
the low-pass filter for B 3 is
In order to satisfy the condition detM#
Laurent polynomial d, we find that c 2 must be one of the 6 real roots of a polynomial
of degree 16 and c 1 can be expressed as a rational polynomial with variable c 2 . For
simplicity, we present them in decimal notation: c 1 # -0.9515104959378669 and
3.803127158568155. It is easy to check that all the conditions in
Theorem 2.4 are satisfied. By Algorithms 2.5 and 5.1, solving a system of linear
equations, we have the high-pass filters a 1 and a 2 as follows:
Therefore,
}, which is defined in Theorem 1.1, generates a symmetric tight
wavelet frame and has 3 vanishing moments. See Figure 1 for their graphs.
Example 3.3. Let be the B-Spline function of order 4. The low-pass
filter for B 4 is
14 Bin Han and Qun Mo
-0.4
-0.3
-0.2
(a)
-0.4
-0.3
-0.2
Fig. 1. (a) is the graph of # 1 . (b) is the graph of # 2 . {# 1 , # 2
} in Example 3.2 generates a
symmetric tight wavelet frame with 3 vanishing moments.
In order to satisfy the condition detM#
Laurent polynomial d, we find a solution {c 1 , c 2 , c 3 } in decimal notation as follows
all the conditions in Theorem 2.4 hold. By Algorithms 2.5 and 5.1,
solving a system of linear equations, we have the high-pass filters a 1 and a 2 as follows:
a 1 (z) :=z(z
Therefore,
}, which is defined in Theorem 1.1, generates a symmetric tight
wavelet frame and has 3 vanishing moments. See Figure 2 for their graphs.
Example 3.4. The low-pass filter a is given by
Matrix Splitting with Symmetry and Framelet Filter Banks 15
-0.2
(a)
-0.2
Fig. 2. (a) is the graph of # 1 . (b) is the graph of # 2 . {# 1 , # 2
} in Example 3.3 generates a
symmetric tight wavelet frame with 3 vanishing moments.
with w := (2 - z - z -1 )/4. In order to satisfy detM#
(anti)symmetric Laurent polynomial d, we find a solution {c 1 , c 2 , c 3 , c 4 , c 5 , c 6 } in decimal
notation as follows
It is easy to check that all the conditions in Theorem 2.4 hold. By
Algorithms 2.5 and 5.1, solving a system of linear equations, we have the high-pass
filters a 1 and a 2 as follows:
Han and Qun Mo
-0.3
-0.2
(b) -6 -4 -2 0 6 8
-0.2
-0.10.10.3(c)
Fig. 3. (a) is the graph of the interpolating refinable function #. (b) is the graph of # 1 . (c)
is the graph of # 2 . {# 1 , # 2
} in Example 3.4 generates a symmetric tight wavelet frame with 4
vanishing moments.
Therefore,
}, which is defined in Theorem 1.1, generates a symmetric tight
wavelet frame and has 4 vanishing moments. See Figure 3 for their graphs.
4. Some Auxiliary Results. In order to prove Theorem 2.3, in this section we
establish some auxiliary results. The following result generalizes [2, Theorem 4] by
taking into account symmetry.
Theorem 4.1. Let A, B and C be (anti)symmetric Laurent polynomials with
real coe#cients. Let M be defined in (2.4). Suppose that
z -k ) with AN #= 0, M(z) # 0 for all z # T and
(anti)symmetric Laurent polynomial d with real coe#cients. If A and B have no
common zeros in C\{0}, then there exist four (anti)symmetric Laurent polynomials
real coe#cients such that (2.5) and (2.7) are satisfied with the degrees
of u 1 and v 1 being at most N . In fact, if are (anti)symmetric
Laurent polynomials with real coe#cients such that the degrees of u 1 and v 1 are at
most N , (2.7) holds, and {u 1 , is a solution to the following system of linear
equations
with the following normalization condition
then (2.5) holds.
Proof. If B(z) # 0, by gcd(A, must be a positive constant and
all the claims can be easily verified by taking A.
So, we can assume that B is not identically zero.
If d(z) # 0, then
(anti)symmetric, it follows from
Matrix Splitting with Symmetry and Framelet Filter Banks 17
A must be a positive constant. All the claims hold by taking
So, we can assume that d is not identically zero.
In the first part of our proof, let us recall the proof of [2, Theorem 4]. Under
the assumption that (2.7) and the degrees of u 1 and v 1 are at most N , we first show
that (2.5) is equivalent to the system of linear equations in (4.1) with the condition
in (4.2).
Hence,
gcd(A, B) which is a contradiction to the assumption gcd(A,
for all z # T. Since A(z) # 0 for all z # T, we must have A(z) > 0 for all z # T.
By Proposition 2.2, without loss of generality, we can assume that
By holds.
it follows from U(z)U(1/z)
# .
Comparing the (1, 1) and (2, 1)-entries of the above matrices, we see that (4.1) holds.
Conversely, let Laurent polynomials with real
coe#cients such that (2.7) holds and the degrees of u 1 and v 1 are at most N . If
is a solution to the system of linear equations in (4.1) and satisfies the
normalization condition in (4.2), then we show that (2.5) must be true.
Multiplying with the first equation and multiplying v 1 (1/z) with the
second equation in (4.1), by adding them together we have
Since A and B have no common zeros in C\{0}, we must have A(z) | [u 1 (z)u
That is, there is a Laurent polynomial p such that
the degrees of u 1 and v 1 are at most N and
we conclude that p must be a constant. By
(4.2) and A(1) > 0, we must further have p # 1. Therefore,
It follows from (4.3) that consequently,
In other words, [U(z)U(1/z) T
for all 1 # j, k # 2 except for the case 2.
Multiplying with the first equation and multiplying u 2 (z) with the second
equation in (4.1), by subtracting the second one from the first one, we have
Consequently,
Han and Qun Mo
Now it is easy to deduce that [U(z)U(1/z) T 2,2 from the fact that
except for 2. So (2.5) holds.
In the second part of the proof, let us show the existence of a desirable solution
to the system of linear equations in (4.1) with the normalization
condition in (4.2).
First, we demonstrate that there are desirable Laurent polynomials u 1 and v 1
satisfying
and
Let u 0 and v 0 be two symmetric Laurent polynomials in the following parametric
forms:
are nonnegative integers and b j , c k , are real
numbers which are to be determined later. Let us consider the following four cases.
Case 1: choose
When N is even, set h
Case 2: choose
N is odd, set h
Case 3: Z. When N is even, we choose
when N is odd, we choose u 1
set
Case 4: choose
N is odd, set h
It is easy to see that both u 1 and v 1 are (anti)symmetric and (4.5) holds. More-
over, the degrees of u 1 and v 1 are at most N and it is easy to verify that h b +h c +2 > N .
Since A(z) > 0 for all z # T, by Fej-er-Riesz Lemma, we have
A(1/z) for
some Laurent polynomial -
A with real coe#cients such that all of the roots of -
A
are contained in {z # C : |z| < 1}. Therefore, -
A(z) and -
A(1/z) have no common
zeros in C\{0}. Since
A(z) can have at
most N zeros in C\{0}, say, {z 1 , . , z N # } are all of the distinct roots of the Laurent
polynomial -
A(z) in C\{0} such that Z( -
A, z N #
Now we have the following system of homogeneous
linear equations:
Since the number of free parameters in {c j , d
and we have N homogeneous linear equations, there must be a
Matrix Splitting with Symmetry and Framelet Filter Banks 19
nonzero solution {c } to the system of homogeneous
linear equations in (4.6). So there exist u 1 and v 1 satisfying (4.6) with at least one of
them nonzero. In other words, we deduce from (4.6) that
are complex numbers, a solution {c
may be complex numbers too. However, since -
and C are Laurent polynomials
with real coe#cients, we can simply replace the numbers c j , d k by either their real
parts or their imaginary part so that (4.7) is still true and at least one of u 1 and v 1
is nonzero.
On the other hand, by (4.5) and Proposition 2.1, we deduce that B(1/z)u 1 (z) -
for some nonzero trivial Laurent polynomial p. Consequently, it follows from (4.7)
and (4.8) that
A(z) and -
A(1/z) have no common zeros in C\{0} and
A(1/z), we
conclude that (4.4) holds. Later on we shall show that u 1 (1) 2 +v 1 (1) 2
then we can properly scale u 1 and v 1 such that u 1
holds. Note that without factorizing A we can solve the system of linear equations
given by [B(1/z)u 1 (z) - d(z)v 1 (1/z)] # 0 mod A(z) to obtain the desired u 1 and
Since A(z) # 0, we can define
By (4.4) we see that u 2 is an (anti)symmetric Laurent polynomial with real coe#cients.
Now we show that v 2 is also an (anti)symmetric Laurent polynomial. By definition
of u 2 and the fact that
From the above identity, we have
therefore, by
is a Laurent polynomial with real coe#cients. By (4.5) and Proposition 2.1, we
see that v 2 is (anti)symmetric.
By (4.9) and Proposition 2.1, we see that (2.7) and the system of linear equations
in (4.1) must hold. In the following, let us show that u 1
both (2.7) and (4.1) are satisfied, as we demonstrated in the first part of the proof,
we must have
then we must have
Han and Qun Mo
must be identically
zero which is a contradiction to our choice of u 1 and v 1 since one of them must be
nonzero. So u 1
replacing u 1 and v 1 by cu 1 and cv 1 with
in the above proof, we see that (4.1) and (2.7) still
hold. Moreover, we have which completes the proof.
Let R[z, z -1 ] denote all of the Laurent polynomials with real coe#cients. For a
Laurent polynomial p # R[z, z -1 ], we say that p is irreducible in R[z, z
some q # R[z, z -1 ] implies that Laurent polynomial
Now we have a stronger version of Theorem 4.1.
Corollary 4.2. Let A, B and C be (anti)symmetric Laurent polynomials with
real coe#cients. Let M be defined in (2.4). Suppose that M(z) # 0 for all z #
T and Laurent polynomial d with
real coe#cients. If gcd(A, B, exist four (anti)symmetric Laurent
polynomials real coe#cients such that (2.5) and (2.7) are satisfied.
Proof. If C(z) # 0, then gcd(A, all the claims follow
from Theorem 4.1. So, we can assume that C is not identically zero.
By the symmetry of A and B, we see that h
must be (anti)symmetric. Now, we show that gcd(h, C) = 1. Suppose not. Then there
is a nontrivial irreducible p # R[z, z -1 ] such that p | gcd(h, C). So, p | h and p | C.
Consequently, p | A and p | B(z)B(1/z). Note that
is trivial. So p | B 2 . Since p is irreducible, we must have p | B. So, p | gcd(A, B, C)
which is a contradiction since p is nontrivial but by assumption gcd(A, B,
Next, we show that for a nontrivial irreducible p # R[z, z
| h for some
then we must have p 2n
| h. Since p 2n-1
| h, we have p 2n-1
| B(z)B(1/z) and
therefore, p 2n-1
is irreducible, we must have
| B and consequently
| B(z)B(1/z).
On the other hand, by p | h and
| [A(z)C(z) -B(z)B(1/z)].
| d(z)d(1/z).
and Sd is trivial, it follows from p 2n-1
| d 2 that p 2n
|
have
By gcd(h, h, we must have gcd(p, since p is nontrivial irre-
ducible. Hence, we must have p 2n
| A. So, p 2n
| h. As a consequence of the fact that
| h implies p 2n
| h, factorize h as
(z),
where p 0 is a trivial Laurent polynomial and p 1 , . , pm are essentially di#erent non-trivial
irreducible Laurent polynomials in R[z, z -1 ]. Now define
d h (z) :=
(z).
Matrix Splitting with Symmetry and Framelet Filter Banks 21
(z). Note that by Proposition 2.2 we can directly obtain
d h from h without factorizing h. Since ([Sd h
Laurent polynomial, Sd h must be trivial and therefore d h is (anti)symmetric. So,
are (anti)symmetric, it
follows from d h (z)d h (1/z) | B(z)B(1/z) that d 2
consequently d h | B. Define
d h (z)
and -
# .
Clearly, -
and C are (anti)symmetric Laurent polynomials and gcd( -
Theorem 4.1, there exist four (anti)symmetric Laurent polynomials -
real coe#cients such that
and
Note that
Then it follows directly from (4.10) and (4.11) that (2.5) and (2.7) are satisfied.
Lemma 4.3. Let p be a nonzero (anti)symmetric Laurent polynomial with real
coe#cients. Then there exist c # {-1, 1} and k # Z such that cz k p(z) # 0 for all
z # T if and only if Z(p, z 0 ) is an even integer for every z 0 # T.
Proof. If cz k p(z) # 0 for all z # T, then by Fej-er-Riesz Lemma, cz k
q(z)q(1/z) for some Laurent polynomial q with real coe#cients. Hence for all z 0 # T,
we have
where we used the fact that Z(q(1/z), z
q is a Laurent polynomial with real coe#cients. So Z(p, z 0 ) must be an even integer
for every z 0 # T.
Conversely, q(z)h(z) such that q(z) #= 0 for all z # T and all of the
zeros of h lie on T. Since p is (anti)symmetric and Z(p, z is an even
integer for all z 0 # T, there exist c 1 # {-1, 1} and k 1 # Z such that c 1 z k1 h(z) # 0 for
all z # T. Since must be symmetric. Since q(z) #= 0 for all
z # T, we must have and is real-valued
for all z # T. Consequently, there exists c 2 # {-1, 1} such that c 2 z -k2 q(z) > 0
for all z # T. So, c 1 c 2 z k1-k2
When p is antisymmetric, it is evident that the condition in Lemma 4.3 cannot
be satisfied.
22 Bin Han and Qun Mo
Lemma 4.4. Let g be a nonzero Laurent polynomial with real coe#cients. Then
there exist two (anti)symmetric Laurent polynomials q 1 and q 2 with real coe#cients
such that
and
z 2k+1 for some integer k
if and only if g(z) # 0 for all z # T and Z(g, x) is an even integer for every x #
Proof. Necessity. If (4.12) holds, then it is evident that g(z) # 0 for all z # T.
](z), we can rewrite (4.12) as
follows:
consequently, it is easy to see that for every x # (-1,
have
must be an even integer for all x # (-1, 0)#
(0, 1).
all x # R\{0}. Similarly, it is easy to prove that Z(g,
must be an even integer for every x # (0, 1).
then we have q 2(x)+(-x) 2k+1 q
for all x # R\{0}. Similarly, it is easy to prove that Z(g,
must be an even integer for every x # (-1, 0).
Su#ciency. Since g(z) # 0 for all z # T, by Fej-er-Riesz lemma, we can write
Laurent polynomial h with real coe#cients such that all
of the roots of h are contained in {z : |z| # 1}. Set q 1
and q 2 it is easy to verify that (4.12) holds and
. In the following, let us consider the other three cases.
Factorize h as
(z),
where p 0 is a trivial Laurent polynomial and all p j , are essentially different
nontrivial irreducible Laurent polynomials in R[z, z -1 ]. Since there are only
two types of nontrivial irreducible Laurent polynomials in R[z, z -1 ], without lost
of generality we can assume that either p
us consider the
following two cases.
, since c j # 0 and
Matrix Splitting with Symmetry and Framelet Filter Banks 23
then we have
for some a j # (-1, 1)\{0}, then by assumption, we have the
following cases:
Case 1: If Z(g, x) is an even integer for all x # (-1, must be an
even integer and therefore, p n j
Case 2: If Z(g, x) is an even integer for all x # (0, 1), then n j must be an even
integer when a j # (0, 1). Therefore, when a
Case 3: If Z(g, x) is an even integer for all x # (-1, 0), then n j must be an even
integer if a j # (-1, 0). When a j # (-1, 0), we have
z 2k+1
z 2k+1 [z -k
# .
By a direct computation, it is easy to verify the following identify
By the above argument, using the identity in (4.13) we have
where - q 0 is a trivial Laurent polynomial, or -z 2k+1 according to the
assumption, and -
are Laurent polynomials with real coe#cients. Observing
that
# .
Note that - q 0 (z)-q 0 (1/z) is a positive constant since - q 0 is trivial. By a simple compu-
tation, we deduce that
where
by a simple computation, we have
Therefore, both q 1 and q 2 are (anti)symmetric and [Sq 1 ](z)/[Sq 2
Han and Qun Mo
5. Proof of Theorem 2.3 and its Associated Algorithm. In this section,
we shall prove Theorem 2.3 and give a step-by-step algorithm to implement it.
Proof of Theorem 2.3: If all the
claims are obviously true by taking
C), by the symmetry of A, B and C, g is (anti)symmetric.
T, we see that
yields that 2Z(B, z) # Z(A, z)
z # T. So, by the definition of g, we have Z(g,
min(Z(A, z), Z(C, z)) for every z # T. Since A(z) # 0 and C(z) # 0 for all z #
T, by Lemma 4.3, Z(A, z) and Z(C, z) are even integers. Consequently, Z(g,
is an even integer for all z # T. Since g is (anti)symmetric, by
Lemma 4.3, there exist c # {-1, 1} and k # Z such that cz k g(z) # 0 for all z # T.
loss of generality, we can assume that g(z) # 0 for
all z # T by replacing g by cz k g(z). Now define -
# with
T, it is easy to see that all -
B, -
C are (anti)symmetric
Laurent polynomials and -
Su#ciency. Since
M(z), we have g 2
| d(z)d(1/z).
| d 2 and therefore, g | d. So define d 1
Then d 1 is an (anti)symmetric Laurent polynomial and det -
Note that gcd( -
B, -
1. By Corollary 4.2, there exist four (anti)symmetric Laurent
polynomials -
real coe#cients such that (4.10) and (4.11) are
By (4.11), -
d is (anti)symmetric and by Proposition 2.1 [S -
By Proposition 2.2, it follows from -
that we
must have -
Rewrite (4.11) as
So, we have
and
Matrix Splitting with Symmetry and Framelet Filter Banks 25
By assumption in (c) and Lemma 4.4, there exist two (anti)symmetric Laurent polynomials
q 1 and q 2 such that
and
Now by (5.2) and Proposition 2.1, it is easy to check that all u 1 , are (anti)symmetric
Laurent polynomials. By a direct computation, it is easy to see that (2.5) and (2.7)
are satisfied.
Necessity. Obviously, (a) and (b) must be true. We shall prove that (c) must be
true. We can assume that d # 0. As we proved before the part of su#ciency, we can assume
that g(z) # 0 for all z # T. Let -
M be defined in (5.1). We have g(z) 2 det -
| d(z)d(1/z). Since
that
| d 2 and therefore, g | d. Define -
d is (anti)symmetric
and det -
d(1/z). Since M(z) # 0 and g(z) # 0 for all z # T, it is easy to
see that -
B, -
are satisfied. So,
In particular, we have
d(1/z).
By (2.7) and (4.11), we have
By Proposition 2.1, q 1 and q 2 are (anti)symmetric. By Proposition 2.2,
Observing that
we have
z 2k [Su 2 ](z)[Sv 1 ](z)
26 Bin Han and Qun Mo
By Lemma 4.4, Z(g(z) -
must be an even integer for the corresponding
cases. Note that -
d](z). So, Z( -
d(1/z), x) is always an even integer
for all x # R. So, Z(g,
must be an even
integer for the corresponding cases. Therefore, (c) must be true.
Finally, by the proof of Theorem 2.3 and all the auxiliary results in Section 4, let
us present the following algorithm on splitting a matrix of Laurent polynomials with
symmetry.
Algorithm 5.1. Let A, B and C be (anti)symmetric Laurent polynomials with
real coe#cients. Let M be the 2-2 matrix defined in (2.4) such that all the conditions
in Theorem 2.3 are satisfied.
C). By the proof of Theorem 2.3, without loss of general-
ity, we can assume that g # 0 and g(z) # 0 for all z # T.
By the proof of Corollary 4.2,
we can assume that h(z) # 0 for all z # T and we can calculate d h such that
by Proposition 2.2.
M of Laurent polynomials with real coe#cients by
with
g(z)d h (z) , -
By Proposition 2.2, we can calculate -
d such that det -
d(1/z).
(If we have an (anti)symmetric Laurent polynomial d such that
d(z)d(1/z), then we can take -
Assume -
Parameterizing the
(anti)symmetric Laurent polynomials -
d](z) and the degrees of - u 1 and - v 1 are at most N (see the paragraph
after the formula (4.5) about how to parameterize -
according
to Theorem 4.1 there must be a nonzero solution {-u to the system of
linear homogeneous equations derived from
A(z).
By the proof of Theorem 4.1, we must have - u 1
Multiplying
1 by a constant, we can require that the solution {-u
A(1).
5) Define the symmetric filters - u 2 and - v 2 by
and
Laurent polynomials q 1 and q 2 such that [Sq 1 ](z)/[Sq 2
(In most cases, and we can simply choose q
Matrix Splitting with Symmetry and Framelet Filter Banks 27
Obtain the (anti)symmetric Laurent polynomials (or symmetric FIR filters) u 1 ,
It is not necessary to check all the conditions in Theorem 2.3 in advance. If at
some step one cannot carry out Algorithm 5.1, then the conditions in Theorem 2.3
cannot be satisfied.

Acknowledgments

. The authors would like to thank the referees for helpful
comments to improve the presentation of this paper and for suggesting the reference
[16].



--R

Compactly supported tight frame associated with refinable func- tions
Compactly supported tight and sibling frames with maximum vanishing moments
The wavelet transform
Ten lectures on wavelets
Pairs of dual wavelet frames from any two refinable functions
Framelets: MRA-based constructions of wavelet frames
Compactly supported tight wavelet frames and orthonormal wavelets of exponential decay with a general dilation matrix
On dual wavelet tight frames
Tight wavelet frames generated by three symmetric B-spline functions with high vanishing moments
The matrix-valued Riesz lemma and local orthonormal bases in shift-invariant spaces
Parameterizations of masks for tight a
Explicit construction of framelets


Smooth wavelet tight frames with zero moments
Nonnegativity constrained spectral factorization for image reconstruction from autocorrelation data
Multirate Systems and Filter Banks
Wavelets and Subband Coding
--TR

--CTR
Amir Z. Averbuch , Valery A. Zheludev , Tamir Cohen, Tight and sibling frames originated from discrete splines, Signal Processing, v.86 n.7, p.1632-1647, July 2006
refinable functions;low-pass and high-pass filters;framelet filter banks;tight wavelet frames;matrix splitting;symmetry