Construction of Orthonormal Multivariate Wavelets by Brian Lindmark A thesis submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Master of Science Auburn, Alabama August 6, 2011 Copyright 2011 by Brian Lindmark Approved by Richard Zalik, Chair, Professor of Mathematics and Statistics Bertram Zinner, Associate Professor of Mathematics and Statistics Stephen Stuckwisch, Assistant Professor of Mathematics and Statistics Abstract The purpose of this paper is to explain the construction of orthonormal multivariate wavelets associated with a multiresolution analysis. This paper primarily uses the work of R. A. Zalik [10], where he outlines a method of constructing orthonormal multivariate wavelets given an existing orthonormal multivariate wavelet associated with an MRA, and attempts to clarify it for a wider audience. In the last section, I use the result in constructing some orthonormal multivariate wavelets in various examples. ii Acknowledgments I?d like to thank my wife Kirsten for her encouragement throughout this process. I?d also like to thank my adviser, Dr. Zalik, for introducing me to the subject of wavelets and helping to guide my studies for the past two years, as well as for his help in my editing process. Finally, I?d like to thank Dr. Angel San Antol n Gil for helping to focus my e orts and being available for additional help when needed. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 iv Chapter 1 Introduction In what follows, d > 1 will be an integer, arbitrary but xed; Z will denote the set of integers and R the set of real numbers; boldface lowcase letters will always denote elements of Rd; x y will stand for the standard dot product of the vectors x and y; i will be reserved for the imaginary number p 1. The inner product of two functions f;g2L2(Rd) will be denoted by hf;gi, their bracket product by [f;g], and the norm of f by jjfjj; thus, hf;gi:= Z Rd f(t)g(t)dt; [f;g](t) := X k2Zd f(t + k)g(t + k); and jjfjj:= p hf;fi: The Fourier transform of a function f will be denoted by bf. If f2L(Rd), bf(x) := Z Rd e 2 it xf(t)dt For every j2Z and k2Zd, the operators Dj and Tk are de ned in L2(Rd) by Djf(t) := 2dj=2f(2jt) and Tkf(t) := f(t k) 1 A set of functions f 1;:::; mg L2(Rd) is called an orthonormal multivariate wavelet, if the sequence fDjTk l;j2Z;k2Zd;1 l mg it generates is an orthonormal basis of L2(Rd). A multiresolution analysis (MRA) in L2(Rd) is a sequence fVj;j2Zg of closed linear subspaces of L2(Rd) such that: Vj Vj+1 for every j2Z (i) For every j2Z;f(t)2Vj if and only if f(2t)2Vj+1 (ii) [ j2Z Vj is dense in L2(Rd): (iii) There is a function u such that fTku;k2Zdg is an orthonormal basis of V0: (iv) Let T := [0;1], and let Td denote the d-dimensional torus. A function f will be called Zd-periodic if it is de ned in Rd, and for every k2Zd and x2Rd we have f(x + k) = f(x). Claim: It follows from the de nition of MRA that there is a Zd-periodic function p2L2(Td) such that bu(2x) = p(x)bu(x) a.e. Proof. Let fTku;k2Zdg be an orthonormal basis of V0. In particular, u(t)2V0. Thus, by (ii), u(t2)2V 1. By (i) and (iv), we can write u t 2 = X k2Zd akTku(t) 2 Where ak = u(t2);Tku(t) . By taking the Fourier transform of both sides, we get Z Rd e 2 it xu(t=2)dt = Z Rd e 2 it x X k2Zd aku(t k)dt: By changing variables, we get Z Rd e 2 i(2s) xu(s)2dds = Z Rd e 2 i(s+k) x X k2Zd aku(s)ds: Which yields, 2dbu(2x) = X k2Zd ake 2 ik xbu(x) If we let p(x) = 2 d X k2Zd ake 2 ik x, then the result follows. The functionuis called ascalingfunctionfor the MRA, andpis called thelowpassfilter associated with u. We will denote the orthogonal complement of Vj in Vj+1 by Wj. Thus, Vj+1 = Vj Wj. Let f 1;:::; mg be an orthonormal multivariate wavelet in L2(Rd); for j2Z, let Pj denote the closure of the linear span of fDjTk l;k2Zd;1 l mg and let Vj := X r< >: [P(x)] 1 if P(x) is nonsingular 0 if P(x) is singular ; yields that Q(x) is Zd-periodic and H(x) = Q(x)U(x) a.e. If we let Q(x) := ql;r(x) m l;r=1 ; then bhl(x) = mX r=1 ql;r(x)bur(x): 11 We then have 1 =jjbhljj2 =jj mX r=1 ql;rburjj2 = * mX r=1 ql;r(x)bur(x); mX s=1 ql;s(x)bus(x) + = Z Rd mX r=1 mX s=1 ql;r(x)bur(x)ql;s(x)bus(x)dx = X k2Zd Z Td mX r=1 mX s=1 ql;r(y + k)bur(y + k)ql;s(y + k)bus(y + k)dy = Z Td mX r=1 mX s=1 ql;r(y)ql;s(y) X k2Zd bur(y + k)bus(y + k)dy (since q is Zd periodic) = Z Td mX r=1 mX s=1 ql;r(y)ql;s(y)[bur;bus](y)dy = Z Td mX r=1 jql;r(y)j2dy (by Lemma 1) Z Td jql;n(y)j2dy for any n2[1;:::;m] =jjql;njj2L2(Td) Therefore ql;n2L2(Td) for l;n = 1;:::;m and thus S(u1;:::;um) = S(h1;:::;hm). Conversely, assume that S(u1;:::;um) = S(h1;:::;hm). Then (3) implies that there are Zd-periodic matrices P(x) = pl;r(x) m l;r=1 and Q(x) = ql;r(x) m l;r=1 such that pl;r;ql;r2L2(Td); l;r = 1;:::;m U(x) = P(x)H(x) a.e. H(x) = Q(x)U(x) a.e. Thus U(x) = P(x)Q(x)U(x) a.e. 12 Which implies that P(x)Q(x) = I a.e. and thus P(x) is nonsingular almost everywhere. Theorem 7. Assume that T(h1;:::;hm) is an orthonormal sequence in L2(Rd), and let fu1;:::;ung be a set of functions de ned on Rd. Then T(u1;:::;un) is an orthonormal se- quence and S(h1;:::;hm) = S(u1;:::;un) if and only if m = n, there are Zd-periodic functions pl;r(x)2L2(Td) such that (3) is satis ed and the matrix (5) is orthogonal almost everywhere. Proof. Assume thatT(h1;:::;hm) andT(u1;:::;un) are orthonormal and such thatS(h1;:::;hm) = S(u1;:::;un). Then m = n by Theorem 1. Lemma 2 implies that (3) is satis ed. Since (3) is satis ed and T(h1;:::;hm) is orthonormal, Lemma 3 implies that (4) is satis ed. If we de ne Pl(x) as the l-th row of P(x), we see that the left hand side of (4) is equivalent to Pl(x) Pj(x) , which tells us that (5) is orthogonal. Now assume m = n, there are Zd-periodic functions pl;r(x) 2L2(Td) such that (3) is satis ed and (5) is orthogonal a.e.. Since (3) is satis ed, S(u1;:::;um) S(h1;:::;hm): Since (5) is orthogonal a.e., (4) is satis ed. We can then use Lemma 3 to show that T(u1;:::;um) is an orthonormal sequence. Since (5) is orthogonal a.e., it is also nonsingular a.e., and we can then use Lemma 4 to conclude that S(h1;:::;hm) = S(u1;:::;um): 13 As we remarked above, iff 1;:::; mgis an orthonormal multivariate wavelet in L2(Rd) associated with an MRA, then m = 2d 1. Thus, an immediate consequence of Theorem 7 is Theorem 8. Assume that f 1;:::; mg is an orthonormal multivariate wavelet in L2(Rd) associated with an MRA, and let f 1;:::; ng be a set of functions de ned in L2(Rd). Then f 1;:::; ng is an orthonormal multivariate wavelet associated with the same MRA as f 1;:::; mg, if and only if m = n = 2d 1, and there are Zd-periodic functions pl;r(x) 2 L2(Td) such that b l(x) = mX r=1 pl;r(x)b r(x) a.e., l = 1;:::;m and the matrix (5) is orthogonal a.e. 14 Chapter 3 Examples We?ll start with some basic constructions of the matrix P(x), and then move to some more complicated formulations. The following de nitions will hold for all of the examples section. (x) = [0;1)(x) (x) = 8 >>>> < >>> >: 1 if x2[0; 12) 1 if x2[12;1) 0 elsewhere Note that (x) is known as the Haar Wavelet. For more information on its construction and properties, see [5, 6, 7] Let 1(x;y) = (x) (y) 2(x;y) = (x) (y) 3(x;y) = (x) (y) The construction of f 1; 1; 3g is outlined in [6, p.82], and is shown to be orthonormal wavelet in L2(R2) generated by the scaling function (x;y) = (x) (y). For information regarding the construction of multivariate wavelets from a scaling function, see [9, Theorem 15 9]. Since each j is separable, the Fourier transforms are easily found and equal to, b 1(u;v) = b (u)b (v) b 2(u;v) = b (u)b (v) b 3(u;v) = b (u)b (v) Example 1. Let P(u;v) = 0 BB BB @ cos(2 u) sin(2 u) 0 sin(2 u) cos(2 u) 0 0 0 1 1 CC CC A This is a basic rotation matrix, which has the property of being Z2-periodic and or- thogonal, hence ful lling the conditions for Theorem 8. If we apply this to our equation, we get, 0 BB BB @ b~ 1(u;v) b~ 2(u;v) b~ 3(u;v) 1 CC CC A = 0 BB BB @ cos(2 u) sin(2 u) 0 sin(2 u) cos(2 u) 0 0 0 1 1 CC CC A 0 BB BB @ b 1(u;v) b 2(u;v) b 3(u;v) 1 CC CC A Recall that cos(2 u) = 12(e2 iu +e 2 iu) and sin(2 u) = 12i(e2 iu e 2 iu). Hence, 0 BB BB @ ~ 1(x;y) ~ 2(x;y) ~ 3(x;y) 1 CC CC A = 0 BB BB B@ 1 2 (x+ 1) + (x 1) 12i (x+ 1) (x 1) (y) 1 2i (x+ 1) (x 1) + 12 (x+ 1) + (x 1) (y) (x) (y) 1 CC CC CA Note that in the above example, the new wavelets are linear combinations of shifted versions of our original ( ) and ( ) in each variable. Thus, it is clear that the new wavelets have bounded support since ( ) and ( ) have bounded support. This will hold true for all of the future examples by the same reasoning. 16 Example 2. For a more general case, we can look back to our introduction of pl;r(x), where we de ned it as X k2Zd al;r;ke2 ik x. Hence, we can choose each pl;r(u;v) to be linear com- binations of two-dimensional Zd-periodic complex exponentials. We will maintain the or- thogonality condition by only using the main diagonal and single terms, rather than linear combinations. Let P(u;v) = 0 BB BB @ e4 iue12 iv 0 0 0 e2 iue 6 iv 0 0 0 e 2 iu 1 CC CC A Once again, nding the inverse Fourier transform is simple since the wavelet and each pl;r(u;v) are separable. Thus, 0 BB BB @ ~ 1(x;y) ~ 2(x;y) ~ 3(x;y) 1 CC CC A = 0 BB BB @ (x+ 2) (y + 6) (x+ 1) (y 3) (x 1) (y) 1 CC CC A Example 3. For the most general case, we begin with three rows which are linearly inde- pendent, and use the Gram-Schmidt Process to orthogonalize the rows, and thus create an orthogonal matrix. Let ~P(u;v) = 0 BB BB @ 3e4 iu 0 4 e4 iu 4e 2 iue 2 iv 0 0 0 5e10 iv 1 CC CC A Note that all these rows are linearly independent. If we de ne our inner product hPl(x);Pj(x)i:= 3X r=1 Z T2 pl;r(u;v)pj;r(u;v)dudv; 17 then by using Gram-Schmidt orthogonalization on our example ~P(u;v), we get that P(u;v) = 0 BB BB @ 3 5e 4 iu 0 4 5 4 25p26e 4 iu 1p 26e 2 i(u+v) 3 25p26 0 0 e10 iv 1 CC CC A Which yields our new wavelet, 0 BB BB @ ~ 1(x;y) ~ 2(x;y) ~ 3(x;y) 1 CC CC A = 0 BB BB @ 3 5 (x+ 2) (y) + 4 5 (x) (y) 4 25p26 (x+ 2) (y) + 1p 26 (x 1) (y 1) 3 25p26 (x) (y) (x) (y + 5) 1 CC CC A 18 Bibliography [1] Bownik, M., On characterizations of multiwavelets in L2(Rn), Proc. American Math. Soc. 129 (2001), 3265-3274. [2] Calogero, A., Wavelets on general lattices associated with general expanding maps of Rn, Electron. Res. Announc. Amer. Math. Soc. 5 (1999), 1-10. [3] Calogero, A., A characterization of wavelets on general lattices, J. Geom. Anal. 10 (2000), 597-622. [4] Guo, K., D. Labate, W-Q. Lim, G. Weiss, and E. Wilson, Wavelets with composite dilations and their MRA properties, Appl. Comput. Harmon. Anal. 20 (2006) 202-236. [5] Hern andez, E., and G. Weiss, A First Course on Wavelets, CRC Press, Boca Raton, FL, 1996. [6] Meyer, Y., Wavelets and Operators, Cambridge University Press, 1992. [7] Strichartz, R. S., Construction of orthonormal wavelets, in Wavelets: Mathematics and Applications, J. J. Benedetto and M. W. Frazier (eds.), CRC Press, Boca Raton, FL, 1994, 1-50. [8] Weiss, G., and E. N. Wilson, The mathematical theory of wavelets, in Twentieth Century Analysis- A Celebration. Proceedings of the NATO Advanced Study Institute, Il Ciocco, Italy, July 2-15, 2000, J. S. Byrnes (ed.), Dordrecht: Kluwer Academic Publishers. NATO Sci. Ser. II, Math. Phys. Chem. 33 (2001), 329-366. [9] Zalik, R.A., Bases of translates and multiresolution analyses, Appl. Comput. Harmon. Anal. 24 (2008) 41-57. [10] Zalik, R.A., Representation of orthonormal multivariate wavelets, in Wavelets and Splines: Athens 2005, G. Chen and M-J. Lai (eds.), Nashboro Press, Brentwood, TN, 2005, 507-515. 19