d0300thttpwww.comonIDE≥L LETTER TO THE EDITOR Explicit Construction of Framelets 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 refinable 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 refinable functions are polynomials(rational functions), then the correspond- with polynomial (rational)symbols can be for 2001 Academic Press Key Words: tight frames; multiresolution analysis; wavelets 1 INTRODUCTION The main goal of our paper' is to present an explicit construction of an arbitrary wavelet frames generated by a refinable 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 L (R)with the inner product (f,g) f(x)g(x)dx As usual, f(o)denotes the Fourier transform of f(x)ELZ(R), defined by f(o)= f(r)e-d Suppose a real-valued function E LZ(R)satisfies the following conditions (a)(2o)=mo(o)(a), where mo is essentially bounded 2T-periodic function; (b)lima→0(a)=(2x)-1 then the function is called refinable or scaling mo is called a symbol of and the relation in item(a) is called a refinement equation I This work was partially supported under Grants NSF KDI 578A045, DoD-N00014-97-1-0806, ONR/ARO- DEPSCoR-DAAG55-98-1-0002, and by Russian Foundation for Basic Research under Grant #OO-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 [71 063-520313500 Copyright G 2001 by Academic All rights of reproducti
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 refinable functions which are obtained with the unitary extension principles. All possible solutions 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 refinable functions are polynomials (rational functions), then the corresponding 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 refinable 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 L 2 (R) with the inner product f, g = ∞ −∞ f (x)g(x) dx. As usual, f (ˆ ω) denotes the Fourier transform of f (x) ∈ L 2 (R), defined by f (ˆ ω) = ∞ −∞ f (x)e −ixω dx. Suppose a real-valued function ϕ ∈ L 2 (R) satisfies the following conditions: (a) ϕ(ˆ 2ω) = m0(ω)ϕ(ˆ ω), where m0 is essentially bounded 2π-periodic function; (b) limω→0 ϕ(ˆ ω) = (2π )−1/2 ; then the function ϕ is called refinable orscaling, m0 is called a symbol of ϕ, and the relation in item (a) is called a refinement equation. 1 This work was partially supported under Grants NSF KDI 578AO45, DoD-N00014-97-1-0806, ONR/ARODEPSCoR-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 refinement function can be asily reconstructed by its symbol, the problem of existence of a scaling function satisfying a refinement 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 refinable function is basic for us and a symbol is only an attribute of a refinable Every refinable function generates a multiresolution analysis(MRA)of the spaceL-(R) 1.e,a nested sequence of closed linear subspaces of L2(R)such that (a)∩ezV={0; (b)Jez v!=L-(r) (c)f(x)∈V分f(2x)∈V+1 To obtain the mra we just have to take as above V/ the closure of the linear span of the functions((2x-n)nez Fulfillment of items(a)and()for the spaces V! 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 L2(R), generated with a given refinable function Mallat [6] showed that if the system lp(r-n)Jnez constitutes a Riesz basis of the space V, then there exists a refinable function p E VO with a symbol mo such that the functions ((x - n))nez form an orthonormal basis of vo. If we denote by W!the orthogonal complement of the space Vi in the space VJ+l, then the function y(which is called a wavelet), defined by the relation 2o):=my( where my(o)=elmo(o+I), generates orthonormal basis y(x-n)nez of the space wo. Thus, the system (2-y(2x-n)nkez (1) constitutes an orthonormal basis of the space L2(R) We see that if we have a refinable 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 L2( 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 econstruction(see, for example, [4D) It is well known that the problem of finding orthonormal wavelet bases, generated by a aling function, can be reduced to solving the matrix equation M(oM (o)=l
314 LETTER TO THE EDITOR In spite of the fact that in most practically important cases the refinement function can be easily reconstructed by its symbol, the problem of existence of a scaling function satisfying a refinement 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 refinable function is basic for us and a symbol is only an attribute of a refinable function. Every refinable function generates a multiresolution analysis (MRA) of the space L 2 (R), i.e., a nested sequence ··· ⊂ V −1 ⊂ V 0 ⊂ V 1 ⊂ ··· ⊂ V j ⊂ ··· of closed linear subspaces of L 2 (R) such that (a) j∈Z V j = {0}; (b) j∈Z V j = L 2 (R); (c) f (x) ∈ V j ⇔ f (2x) ∈ V j+1 . To obtain the MRA we just have to take as above V j the closure of the linear span of the functions {ϕ(2 jx − n)}n∈Z. Fulfillment of items (a) and (b) for the spaces V j 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 L 2 (R), generated with a given refinable function. Mallat [6] showed that if the system {ϕ(x − n)}n∈Z constitutes a Riesz basis of the space V 0 , then there exists a refinable function φ ∈ V 0 with a symbol mφ such that the functions {φ(x − n)}n∈Z form an orthonormal basis of V 0 . If we denote by Wj the orthogonal complement of the space V j in the space V j+1 , then the function ψ (which is called a wavelet), defined by the relation ψ(ˆ 2ω) := mψ (ω)φ(ˆ ω), where mψ (ω) = e iωmφ(ω + π ), generates orthonormal basis {ψ(x − n)}n∈Z of the space W0 . Thus, the system 2 k/2ψ(2 k x − n) n,k∈Z (1) constitutes an orthonormal basis of the space L 2 (R). We see that if we have a refinable 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 L 2 (R) 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 finding orthonormal wavelet bases, generated by a scaling function, can be reduced to solving the matrix equation M(ω)M∗ (ω) = I, (2)
LETTER TO THE EDITOR m0(+r)m1(a+丌) ind mo(o), mI(o) are essentially bounded functions mo(-o)=mo(o); i.e., Fourier series of these functions have real coefficients. It is known(see [4]that for any scalin function (r)and the associated wavelet y(x), generating an orthogonal wavelet basi the corresponding symbols mo(o), mI(o) satisfy(2). Any refinable function whose symbol mo is solution to(2), generates a tight frame(see [5] for the case when mo is polynomial, the general case was proved in [2]) We cannot independently look for the functions mo and mI. In fact, usually we find solution of the equation m(o)2+|mo(a+m)2=1 and then all possible functions mI can be represented in the form mI(o=a(@mo(o+T) where a(o)is an arbitrary T-periodic function, satisfying la(o)l=l,a(-o)=a(o) Now suppose we have an arbitrary refinable function (o) with the symbol mo which does not satisfy (3). Then the set lo(r-n)Inez does not constitute an orthonormal basis If this set forms a Riesz basis, then we can use orthogonalization, proposed in [6] However, in this case, when the function o 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 refinable function 1/2,|x|≤ 0 x|>1 with the symbol mo(o)=cos 20. In this case the MRa coincides with the Haar MRA Thus. the function 1,0≤x≤1; g(x)= x>lor x <0: is the natural orthogonalization Nevertheless, it is easy to design a refinable function such that its mRa does not allow orthogonalization. Indeed, let us introduce a refinable function (x)=sinax/tx where< a< 1. It generates the space Vo which consists of functions of L2(R)with Fourier transform supported on [-a, a]. Thus, for any function f E v the function chez If(o 2k)l vanishes on the set [-, T]a, ar]. Hence, its integer translates do not form an orthonormal bases(see [4D). 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 mo of a refinable function p does not satisfy (3)we cannot onstruct an orthonormal bases of v of the form (x-k), y(x-k)). However, we car
LETTER TO THE EDITOR 315 where M(ω) = m0(ω) m1(ω) m0(ω + π ) m1(ω + π ) , and m0(ω), m1(ω) are essentially bounded functions m0(−ω) = m0(ω); i.e., Fourier series of these functions have real coefficients. It is known (see [4]) that for any scaling function ϕ(x) and the associated wavelet ψ(x), generating an orthogonal wavelet basis, the corresponding symbols m0(ω), m1(ω) satisfy (2). Any refinable function ϕ, whose symbol m0 is solution to (2), generates a tight frame (see [5] for the case when m0 is polynomial, the general case was proved in [2]). We cannot independently look for the functions m0 and m1. In fact, usually we find a solution of the equation |m0(ω)| 2 + |m0(ω + π )| 2 = 1, (3) and then all possible functions m1 can be represented in the form m1(ω) = α(ω)e iωm0(ω + π ), (4) where α(ω) is an arbitrary π-periodic function, satisfying |α(ω)| = 1, α(−ω) = α(ω). Now suppose we have an arbitrary refinable function ϕ(ω) with the symbol m0 which does not satisfy (3). Then the set {ϕ(x − n)}n∈Z does not constitute an orthonormal basis of V 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 refinable function ϕ(x) = 1/2, |x| ≤ 1; 0, |x| > 1; with the symbol m0(ω) = cos 2ω. In this case the MRA coincides with the Haar MRA. Thus, the function ϕ(x) = 1, 0 ≤ x ≤ 1; 0, x > 1 or x < 0; is the natural orthogonalization. Nevertheless, it is easy to design a refinable function such that its MRA does not allow orthogonalization. Indeed, let us introduce a refinable function ϕ(x) = sinπax/πx, where 0 < a < 1. It generates the space V 0 which consists of functions of L 2 (R) with Fourier transform supported on [−aπ, aπ]. Thus, for any function f ∈ V 0 the function k∈Z |f (ˆ ω + 2kπ)| 2 vanishes on the set [−π,π]\[aπ, aπ]. 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 m0 of a refinable function ϕ does not satisfy (3) we cannot construct an orthonormal bases of V 1 of the form {ϕ(x − k),ψ(x − k)}. However, we can
316 LETTER TO THE EDITOR hope that there exists a collection of several framelets y, v2,.,w"E V, satisfying the following conditions (4(=2m每 (2)for any fEL(R), algorithms of decomposition and reconstruction the recurrent formulac (k,f=c=∑c+1.-2 k∈Z 1 (5) (q3k,f)= Cj+. kgk c+1=∑ckh-k+∑∑k8,- k∈z where hk, gi are coefficients of the expansions mo(o)=2-Ekez hke-iko and k∈z8ke~k 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 mo(o) is either a rational function or a polynomial we can choose mI(o), m2(o)as rational functions or polynomials respectively 2. GENERAL FRAMELETS Let be a refinable function with a symbol mo, v(o)=mk(o /2)(o/2)E V,where each symbol mk is a 2T-periodic and essentially bounded function for k= l, 2,..., n. It is well known that for constructing practically important tight frames the matrix m0(u) mn(o) m0(a+丌)m1(a+丌) plays an important role It is easy to see that the equality M(o)M(o)=I (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 y el generate a tight frame Remark. For n= l this theorem was proved in [5] for polynomial symbols and in [2] for the general case. For an arbitrary n it was proved in [8] under some additional decay assumption for and in [3] for an arbitrary polynomial symbol. In[8] Theorem 2. 1 wa alled the unitary extension principle
316 LETTER TO THE EDITOR hope that there exists a collection of several framelets ψ 1 , ψ2 ,...,ψ n ∈ V 1 , satisfying the following conditions: (1) functions {{ψ l j,k }j,k∈Z} n l=1 , where ψ l j,k (x) = 2 j/2ψl(2 j x − k), form a tight frame of the space L 2 (R); (2) for any f ∈ L 2 (R), algorithms of decomposition and reconstruction the recurrent formulae ϕj,k , f = cj,l = k∈Z cj+1,kh¯ k−2l, 1 ≤ q ≤ n, (5) ϕ g j,k , f = d q j,l = k∈Z cj+1,kg¯ q k−2l , and cj+1,l = k∈Z cj,khl−k + n q=1 k∈Z d q j,k g q l−k , (6) where hk , g q k are coefficients of the expansions m0(ω) = 2 −1/2 k∈Z hke −ikω and mq (ω) = 2 −1/2 k∈Z g q k e −ikω, q = 1,..., n 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 m0(ω) is either a rational function or a polynomial we can choose m1(ω), m2(ω) as rational functions or polynomials respectively. 2. GENERAL FRAMELETS Let ϕ be a refinable function with a symbol m0, ψˆ k (ω) = mk(ω/2)φ(ˆ ω/2) ∈ V 1 , where each symbol mk is a 2π-periodic and essentially bounded function for k = 1, 2,..., n. It is well known that for constructing practically important tight frames the matrix M(ω) = m0(ω) m1(ω) ... mn(ω) m0(ω + π ) m1(ω + π) ... mn(ω + π ) , plays an important role. It is easy to see that the equality M(ω)M∗ (ω) = I (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 {ψ k } n k=1 generate a tight frame of L 2 (R). Remark. For n = 1 this theorem was proved in [5] for polynomial symbols and in [2] for the general case. For an arbitrary n 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 We split the proof of Theorem 2.1 into several lemmas. LEMMA 2.1. Let the symbols (mk k-o satisfy(7). Then for any o m(o)2+lm(a+x)2≤1,=0,1,,n. Proof. Obviously, without lose of generality it suffices to prove inequality(8)only for 1=0. Let us rewrite relation (7)in the form Imo(o)12 mo(a)mo(a+丌) M(o): =My(o)My(o) o(a)mo(a+丌) m0(0+丌 m1(a)m2(a) My(o) m1(ox)m2(a+丌) The Hermitian matrix M(o) has eigenvalues 入1()=1,A2(a)=1-|m0(a)2-|mo(a+r)2 By definition(9), M(o) is a positive definite matrix. Hence, 12(0)>0, which is(8)for 0 LEMMA 2.2. If peLZ(R)is a refinable function with a symbol m(o) that satisfies the m(a)2+m(a+丌)≤1ae then Sj:=∑ezl(f,中,k)2<∞ for any function f∈L2(R)and (i)imS;=‖f‖ (ii lim Si=0 where ;. k=2/4(2Jx-k Proof. First, we prove that ∑|中(x+2x)2≤2 We note that due to (10)and the continuity (o)at a=0 we have |d(o)l <( 2x)-/2a.e Thus, for any positive /EZ we obtain ∑(+2xmk)2=∑∏m(2-"(o+2mk)21(2--1(o+2k)2 k==21 k==2ln=1 2-11+1 ∑∏m(2-"(o+2xk)2
LETTER TO THE EDITOR 317 We split the proof of Theorem 2.1 into several lemmas. LEMMA 2.1. Let the symbols {mk} n k=0 satisfy (7). Then for any ω |ml(ω)| 2 + |ml(ω + π )| 2 ≤ 1, l = 0, 1,..., n. (8) Proof. Obviously, without lose of generality it suffices to prove inequality (8) only for l = 0. Let us rewrite relation (7) in the form M(ω) := Mψ (ω)M∗ ψ (ω) = 1 − |m0(ω)| 2 −m0(ω)m0(ω + π ) −m0(ω)m0(ω + π ) 1 − |m0(ω + π )| 2 , (9) where Mψ (ω) = m1(ω) m2(ω) ... mn(ω) m1(ωπ ) m2(ω + π) ... mn(ωπ ) . The Hermitian matrix M(ω) has eigenvalues λ1(ω) ≡ 1, λ2(ω) = 1 − |m0(ω)| 2 − |m0(ω + π )| 2 . By definition (9), M(ω) is a positive definite matrix. Hence, λ2(ω) ≥ 0, which is (8) for l = 0. LEMMA 2.2. If " ∈ L 2 (R) is a refinable function with a symbol m(ω) that satisfies the condition |m(ω)| 2 + |m(ω + π )| 2 ≤ 1 a.e., (10) then Sj := k∈Z |f,"j,k|2 < ∞ for any function f ∈ L 2 (R) and (i) lim j→∞ Sj = f 2 ; (ii) lim j→−∞ Sj = 0, where "j,k = 2 j/2"(2 j x − k). Proof. First, we prove that k∈Z |"(x ˆ + 2πk)| 2 ≤ 1 2π . (11) We note that due to (10) and the continuity "(ω ˆ ) at ω = 0 we have |"(ˆ ω)| ≤ (2π )−1/2 a.e. Thus, for any positive l ∈ Z we obtain 2 l−1 k=−2 l |"( ˆ ω + 2πk)| 2 = 2 l−1 k=−2 l l+1 n=1 |m(2 −n (ω + 2πk))| 2 |"( ˆ 2 −l−1 (ω + 2πk))| 2 ≤ 1 2π 2 l−1 k=−2 l l+1 n=1 |m(2 −n (ω + 2πk))| 2