Applied and Computational Harmonic Analysis 11,313 327 (2001)
doi:10.1006/acha.2000.0337,available online at http://www.idealibrary.com on
LETTER TO THE EDITOR
Explicit Construction of Framelets 1
Alexander Petukhov 2
Communicated by Charles Chui
Received July 11,2000; revised October 27,2000; published online July 10,2001
Abstract We study tight wavelet frames associated with given re nable func-
tions which are obtained with the unitary extension principles,All possible solu-
tions of the corresponding matrix equations are found,It is proved that the problem
of the extension may be always solved with two framelets,In particular,if symbols
of the re nable functions are polynomials (rational functions),then the correspond-
ing framelets with polynomial (rational) symbols can be found,2001 Academic Press
Key Words,tight frames; multiresolution analysis; wavelets.
1,INTRODUCTION
The main goal of our paper 3 is to present an explicit construction of an arbitrary
wavelet frames generated by a re nable function,After submission this paper to Applied
and Computational Harmonic Analysis we received information that the editorial portfolio
already contains the paper by C,Chui and W,He [3] that contains similar results.
In this paper,we shall consider only functions of one variable in the space 2 with
the inner product
As usual,denotes the Fourier transform of 2,de nedby
Suppose a real-valued function 2 satis es the following conditions:
(a) 2 0,where 0isessentially bounded 2 -periodic function;
(b) lim 0 2 1 2;
then the function is called re nable or scaling,0 is called a symbol of,and the relation
in item (a) is called a re nement equation.
1 This work was partially supported under Grants NSF KDI 578AO45,DoD-N00014-97-1-0806,ONR/ARO-
DEPSCoR-DAAG55-98-1-0002,and by Russian Foundation for Basic Research under Grant #00-01-00467.
2 Department of Mathematics,University of South Carolina,Columbia,South Carolina 29208,E-mail:
petukhov@math.sc.edu,petukhov@pdmi.ras.ru.
3 This paper is a reduced version of preprint [7].
313
1063-5203/01 $35.00
Copyright 2001 by Academic Press
All rights of reproduction in any form reserved.
314 LETTER TO THE EDITOR
In spite of the fact that in most practically important cases the re nement function can be
easily reconstructed by its symbol,the problem of existence of a scaling function satisfying
a re nement equation with the given symbol is not completely solved,Here we shall not
discuss the problem of recovering the function by its symbol,So in what follows the
notion of a re nable function is basic for us and a symbol is only an attribute of a re nable
function.
Every re nable function generates a multiresolution analysis (MRA) of the space 2,
i.e.,a nested sequence
1 0 1
of closed linear subspaces of 2 such that
(a) 0 ;
(b) 2 ;
(c) 2 1.
To obtain the MRA we just have to take as above the closure of the linear span of the
functions 2,Ful llment of items (a) and (b) for the spaces was proved
in [1],Property (c) is evident.
The most popular approach to the design of orthogonal and biorthogonal wavelets is
based on construction of MRA of the space 2,generated with a given re nable
function,Mallat [6] showed that if the system constitutes a Riesz basis
of the space 0,then there exists a re nable function 0 with a symbol such that
the functions form an orthonormal basis of 0.Ifwedenoteby the
orthogonal complement of the space in the space 1,then the function (which is
called a wavelet),de ned by the relation
2
where,generates orthonormal basis of the
space 0,Thus,the system
2 2 2
(1)
constitutes an orthonormal basis of the space 2,
We see that if we have a re nable function,generating a Riesz basis,then we have
explicit formulae for the wavelets,associated with this function,It gives a simple
method for constructing wavelets,Generally speaking,any orthonormal basis of 2
of the form (1) is called a wavelet system,However,wavelet construction based on
multiresolution has an advantage from the point of view effectiveness of computational
algorithms,because it leads to a pyramidal scheme of wavelet decomposition and
reconstruction (see,for example,[4]).
It is well known that the problem of nding orthonormal wavelet bases,generated by a
scaling function,can be reduced to solving the matrix equation
(2)
LETTER TO THE EDITOR 315
where
0 1
0 1
and 0,1 are essentially bounded functions 0 0 ; i.e.,Fourier
series of these functions have real coef cients,It is known (see [4]) that for any scaling
function and the associated wavelet,generating an orthogonal wavelet basis,
the corresponding symbols 0,1 satisfy (2),Any re nable function,whose
symbol 0 is solution to (2),generates a tight frame (see [5] for the case when 0 is
polynomial,the general case was proved in [2]).
We cannot independently look for the functions 0 and 1,In fact,usually we nd a
solution of the equation
0 2 0 2 1 (3)
and then all possible functions 1 can be represented in the form
1 0 (4)
where is an arbitrary -periodic function,satisfying 1,.
Now suppose we have an arbitrary re nable function with the symbol 0 which
does not satisfy (3),Then the set does not constitute an orthonormal basis
of 0,If this set forms a Riesz basis,then we can use orthogonalization,proposed in [6].
However,in this case,when the function has a compact support,this property fails for
the orthogonalized basis,This argues for construction other systems keeping compactness
of support,It will be shown in Section 4 that tight frame of wavelets leads to one of the
possible compactly supported systems.
We note that sometimes the orthogonalization can be conducted even if our set is not a
Riesz basis,The simplest example gives a re nable function
1 2 1;
0 1;
with the symbol 0 cos 2,In this case the MRA coincides with the Haar MRA.
Thus,the function
1 0 1;
0 1or 0;
is the natural orthogonalization.
Nevertheless,it is easy to design a re nable function such that its MRA does not
allow orthogonalization,Indeed,let us introduce a re nable function sin,
where 0 1.It generates the space 0 which consists of functions of 2 with
Fourier transform supported on,Thus,for any function 0 the function
2 2 vanishes on the set,Hence,its integer translates
do not form an orthonormal bases (see [4]),In this case the traditional procedure of
constructing an orthonormal wavelet basis cannot be applied,We note that by the same
reason even a biorthogonal pair with this MRA cannot be constructed.
In the case when the symbol 0 of a re nable function does not satisfy (3) we cannot
construct an orthonormal bases of 1 of the form,However,we can
316 LETTER TO THE EDITOR
hope that there exists a collection of several framelets 1 2 1,satisfying the
following conditions:
(1) functions 1,where 2 2 2,form a tight frame of
the space 2 ;
(2) for any 2,algorithms of decomposition and reconstruction the recurrent
formulae
1 2
1 (5)
1 2
and
1
1
(6)
where,are coef cients of the expansions 0 2 1 2 and
2 1 2,1 take place.
The goal of Section 2 is to show that this problem can be solved with at most two
framelets and to present explicit formulae for symbols of the framelets,In Sections 3 and
4 we prove that in the case when 0 is either a rational function or a polynomial we
can choose 1,2 as rational functions or polynomials respectively.
2,GENERAL FRAMELETS
Let be a re nable function with a symbol 0,2 2 1,where
each symbol is a 2 -periodic and essentially bounded function for 1 2,Itis
well known that for constructing practically important tight frames the matrix
0 1
0 1
plays an important role.
It is easy to see that the equality
(7)
is equivalent to (5) and (6).
It turns out that (7) also implies the tightness of the corresponding frame.
THEOREM 2.1,If (7) holds,then the functions 1 generate a tight frame
of 2,
Remark.For 1this theorem was proved in [5] for polynomial symbols and in [2]
for the general case,For an arbitrary it was proved in [8] under some additional decay
assumption for and in [3] for an arbitrary polynomial symbol,In [8] Theorem 2.1 was
called the unitary extension principle.
LETTER TO THE EDITOR 317
We split the proof of Theorem 2.1 into several lemmas.
LEMMA 2.1,Let the symbols 0 satisfy (7),Then for any
2 2 1 0 1 (8)
Proof,Obviously,without lose of generality it suf ces to prove inequality (8) only for
0,Let us rewrite relation (7) in the form
1
0 2 0 0
0 0 1 0 2
(9)
where
1 2
1 2
The Hermitian matrix has eigenvalues
!1 1 !2 1 0 2 0 2
By de nition (9),is a positive de nite matrix,Hence,!2 0,which is (8) for
0.
LEMMA 2.2,If " 2 is a re nable function with a symbol that satis es the
condition
2 2 1a e (10)
then # " 2 for any function 2 and
lim
# 2 lim
# 0
where " 2 2" 2,
Proof,First,we prove that
" 2 2 12 (11)
We note that due to (10) and the continuity " at 0wehave " 2 1 2 a.e.
Thus,for any positive we obtain
2 1
2
" 2 2
2 1
2
1
1
2 2 2 " 2 1 2 2
12
2 1
2
1
1
2 2 2
318 LETTER TO THE EDITOR
12
2 1
0
1
1
2 2 2
1
1
2 2 2 2
12
2 1
0
1
2 2 2
12
2 1 1
0
1
2 2 2
1
2 2 2 1 2
12
2 1 1
0
1
1
2 2 2 12
Applying the Plancherel and Parseval formulae,we have
" 2 2 2
" 2 2
2
2 2
2
2
2 2 " 2 2 2
2
2
2 2
2
2
2 2 " 2 2 2
2
2 $ 2 (12)
where $ 2 2 " 2 2 2,Let us introduce the follow-
ing sequences of functions
2 ;
,0 1 2
0 2 ;
%
2 2 " 2 2 2
&
2 2 " 2 2 2
It is clear that,on the one hand,% 2 1 2 as,Onthe other hand,
in view of (11),
LETTER TO THE EDITOR 319
& 2
2
2
2 2 " 2 2 2
2
2
2
2 2
2
" 2 2 2
12
2
2
2 2
2 1
2
2 0 as (13)
Thus,since
% & $ % & % &
it follows from (12) and (13) that
" 2 2 $ 2 2 2 2 as
Thus,relation (i) is proved.
Now we shall prove (ii),Let us denote ’( the characteristic function of a segment
( ( and by ( the function ’(,We xanarbitrary) 0and choose ( 0such
that 1 ’( ).
Since
" 2 2
( " 2 2
( " 2
2
( " 2 ( 2
( " 2 )
we need only to prove that
lim
( " 2 0
If we assume that 2 ( 1 2,then the last relation follows from the chain of inequalities
( " 2
(
"
2
2
(
"2 2
2 (
"2
2
2 ( 2 (
"2 0as
LEMMA 2.3,If (7) holds,then for any 2 and *
1
2
* 2
1
*
2
320 LETTER TO THE EDITOR
Proof,It follows from (7) that
0 2 1 2 2 1
0 0 1 1 0
So,introducing the notation
+1
2 2,1 2,1 2
+2
2 2,1 2 2,2,1 2
we have,by analogy with (12),for any,
,2
1
,2
2 2
2,
2,
2 2,2,2 2,
2
2 2
1
2,
2,
2 2,2,2 2,
2
2 2
0
2,
2,
2 2,
2,1 2 2,2,1 2 2,
2
2 2
0
2,
2,
+1 2,1
2
2 2
0
2,
2,
+2 2,1
2
2 2
0
2,
2,
+1 2,1 +2 2,1
2 2
0
2,
2,
+2 2,1 +1 2,1
2 2
2,
2,
2 2,1 2,1 2
2
2 2
2,
2,
2 2,1 2 2,2,1 2
2
2 2
2,1
2,1
2 2,1 2,1 2
2
,1 2
Using Lemma 2.2 we obtain of Lemma 2.3.
LETTER TO THE EDITOR 321
Now Theorem 2.1 is an easy consequence of Lemmas 2.1 2.3.
Thus,the problem of constructing tight frames,generated by a re nable function,can be
reduced to nding,that satisfy (7),Now we shall describe all possible solutions to (7).
Let the symbol 0 satisfy (10),Unit eigenvectors of the matrix can be represented
in the form
v1
0
-
0 -
v
2
0
-
0
-
- 0
where - is an arbitrary -periodic measurable functions,satisfying - 2
0 2 0 2 a.e,For de niteness,we can take here the positive root of
the right-hand expression,For those when 0 0 0 the matrix
becomes the identity matrix,So any non-zero vector is its eigenvector,In this case we put
v1 1 0,,v2 0 1,,
Thus,we have
/ 0 / (14)
where
/
0
-
0
-
0 - 0 -
0
10
01 0 2 0 2
We note that eigenvectors are determined up to multiplication by a scalar function
of absolute value 1 a.e,We have chosen the normalization convenient for further
consideration.
THEOREM 2.2,Let a 2 -periodic function 0 satisfy (10),Then there exists a pair
of 2 -periodic measurable functions 1,2 which satisfy (7) for 2,Any solution of
(7) can be represented in the form of the rst row of the matrix
/ 0 1
where 1 is an arbitrary unitary (a.e.) matrix with -periodic measurable components.
Proof,The matrix can be represented in the form of its singular decomposition
where,are unitary matrices,is a nonnegative diagonal matrix,These
representations may differ by multiplication of columns of the matrix by functions
1,2,1 2 1 andsimultaneous multiplication of rows of the
matrix by 11 and 12,Thus,in view of (9) and (14) without loss of generality
we can suppose /,0.