Contents NTRODUCTION PRELIMINARIES AND NOTATION I CHAPTER I: The What, Why, and How of Wavelets C. 1.- CHAPTER 2: The Continuous Wavelet Transform CHAPTER 3: Discrete Wavelet Transforms: frames 107 CHAPTER 4: Time-Frequency Density and Orthonormal Bases 129. CHAPTER 5 Orthonormal Bases of Wavelets and Multiresolution Analysis [67 CHAPTER 6: Orthonormal Bases of Compactly Supported Wavelets 215 CHAPTER 7: More Aboul the Regularity of Compactly Supported Wavelets 251. CHAPTER 8: Symmetry for Compactly Supported Wavelet Bases 2:289 CHAPTER 9: Characterization of Functional Spaces by Means of Wavelets /313. CHAPTER 10: Generalizations and Tricks for Orthonormal Wavelet Bases 2.341 REfERENCES SUBJECT INDEX 355. AUTHOR INDEX
Introduction Wavelets are a relatively recent .evelopment in applied mathematics. Their name itself was coined approximately a decade ago(Morlet, Arens, Fourgeau and Giard(1982), Morlet(1983), Grossmann and Morlet( 1984); in the last ten years interest in them has grown at an explosive rate. There are several rea- sons for their present success. On the one hand the concept of wavelets can bi viewed as a synthesis of ideas which originated during the last twenty or thirty years in engineering(subband coding), physics(coherent states, renormalization group), and pure mathematics(study of Calderon-Zygmund operators).As a consequence of these interdisciplinary origins, wavelets appeal to scientists and engineers of many different backgrounds. On the other hand, wavelets are a fairly simple mathematical tool with a great, variety of possible applications. Already they have led to exciting applications in signal analysis(sound, images)(some early references are Kronland-Martinet, Morlet and Grossmann(1987), Mallat (1989b),(1989c); more recent references are given later)and numerical analy- sis(fast algorithms for integral transforms in Beylkin, Coifman, and Rokhlin (1991)); many other applications are being studied. This wide applicability alse contributes to the interest they generate V This book contains ten lectures I delivered as the principal speaker at the CBMS conference on wavelets organized in June 1990 by the Mathematics De- partment at the University of Lowell, Massachusetts. according to the usual format or the CBMS conferences, other speakers(G. Battle, G. Beylkin, C. Chui A. Cohen, R. Coifman, K. Grochenig, J. Liandrat, S. Mallat, B. Torresani and A. Willsky) provided lectures on their work related to wavelets. Moreover three workshops were organized, on applications to physics and inverse problems (chaired by B. DeFacio), group theory and harmonic analysis(H. Feichtinger and signal analysis(M. Vetterli). The audience consisted of researchers active in the field of wavelets as well as of mathematicians and other scientists and ngineers who knew little about wavelets and hoped to learn more. This second group constituted the largest part of the audience I saw it as my task to provide a tutorial on wavelets to this part of the audience, which would then be a solid grounding for more recent work exposed by the other lecturers and myself. Con sequently, about two thirds of my lectures consisted of "basic wavelet theory
ITRODUCTION the other third being devoted to more recent and unpublished work. This divi- sion is refected in the present write-up as well. As a result, I believe that this book will be useful as an introduction to the subject, to be used either for indi- vidual reading, or for a seminar or graduate course. None of the other lectures or, workshop papers presented at the CBMs conference have been incorporated here, As a result, this presentation is biased more toward my own work than the CRMS conference was. In many instances I have included pointers to references trther reading or a detailed exposition of particular applications, comple- ting the present text. Other books on wavelets published include Wavelets Tame Frequency Methods(Combes, Grossmann, and Tchamitchian(1987)) contains the proceedings of the International Wavelet Conference held in lille, France, in December 1987, Ondelettes, by Y Meyer(1990)(in French lish translation expected soon), which contains a mathematically more ex ded treatment than the present lectures, with fewer forays into other fields " wever, Les Ondelettes en 1989, edited by P G. Lemarie(1990), a collection of cks given at the Universite Paris XI in the spring of 1989, and An Introduction Wavelets, by C. K. Chui(1992b), an introduction from the approximation theory viewpoint. The proceedings of the International Wavelet Conference In May 1989, held again in Marseille, are due to come out soon(Meyer(1992)) Moreover, many of the other contributors to the CBMS conference, as well as some wavelet researchers who could not attend, were invited to write an essay on their wavelet work, the result is the essay collection Wavelets and their Ap- placations(Ruskai et al. (1992), which can be considered a companion book to thIs one. Another wavelet essay book is Wavelets: A Tutoral in Theory and Applacations, edited by C. K. Chui(1992c); in addition, I know of several other wavelet essay books in preparation(edited by J. Benedetto and M Frazier, an- other by M. Barlaud ) as well as a monograph by M. Holschneider; thele was a, special wavelet issue of IEEE Trans. Inform. Theory in March of will be another one, later in 1992, of ConstructIve Approzzmation Theory, and gne in 1993, of IEEE Trans. Sign. Prmc. In addition, several recent books in- clude chapters on wavelets. Examples are Multraie Systems and Falter Banks by P. P. Vaidyanathan(1992)and Quantum Fhysacs, Relatunty and Compler Spacetime: Towards a New Synthesus by G. Kaiser(1990 ). Readers interested in the present lectures will find these books and special issues useful for many details and other aspects not fully presented here. It is moreover clear that the subject is still developing rapidly This book more or less follows the path of my lectures: each of the ten chap- ters stands for one of the ten lectures, presented in the order in which they were delivered. The first chapter presents a quick overview of different aspects of the wavelet transform. It sketches the outlines of a big fresco; subsequent chapters then fill in more detail. From there on, we proceed to the continu ous wavelet transform( Chapter 2; with a short review of bandlimited functions and Shannon, s theorem), to discrete but redundant wavelet transforms(frames Chapter 3)and to a general discussion of time-frequiency density and the possible existence of orthonormal basis(Chapter 4). Many of the results in Chapters 2-4 can be formulated for the windowed Fourier transform as well as the wavelet
INTRODUCTION transform, and the two cases are presented in parallel, with analogies and differ ences pointed out as we go along. The remaining chapters all focus on orthonor- mal bases of wavelets. multiresolution analysis and a first general strategy for the construction of orthonormal wavelet bases( Chapter 5), orthonormal bases of compactly supported wavelets and their link to subband coding(Chapter 6) sharp regularity estimates for these wavelet bases(Chapter 7), symmetry for compactly supported wavelet bases(Chapter 8)Chapter 9 shows that orthonor- mal bases are"good"bases for many functional spaces where Fourier methods are not well adapted. This chapter is the most mathematical of the whole book most of its material is not connected to the applications discussed in other chap- ters, so that it can be skipped by readers uninterested in this aspect of wavelet theory. I included it for several reasons: the kind of estimates used in the proof are very important for harmonic analysis, and similar(but more complicated) estimates in the proof of the"r(1)"-theorem of David and Journe have turned out to be the groundwork for the applications to numerical analysis in the work of Beylkin, Coifman, and Rokhlin(1991)Moreover, the Calderon-Zygmuin theorem, explained in this chapter, illustrates how techniques using different scales, one of the forerunners of wavelets, were used in harmonic analysis long before the advent of wavelets. Finally, Chapter 10 sketches several extensions of the constructions of orthonornal wavelet bases: to more than one dimension to dilation factors different from two(even noninteger), with the possibility of better frequency localization, and to wavelet bases on a finite interval instead of the whole line. Every chapter concludes with a section of numbered"note referred to in the text of the chapter by superscript numbers. These contai additional references, extra proofs excised to keep the text Rowing, remarks, etc This book is a mathematics book: it states and proves many theorems. It also presupposes some mathematical background. In particular, I assume that the reader is familiar with the basic properties of the fourier transform and Fourier series. I also use some basic theorems of measure and integration theory (Fatou' s lemma, dominated convergence theorem, Fubini's theorem; these cath be found in any good book on real analysis). In some chapters, familiarity with basic Hilbert space techniques is useful. A list of the basic notions and theorems used in the book is given in the preliminaries The reader who finds that he or she does not know all of these prerequisites should not be dismayed, however; most of the book can be followed with just the basic notions of Fourier analysis. Moreover, I have tried to keep a very pedes- trian pace in almost all the proofs, at the risk of boring some mathematically ophisticated readers. I hope therefore that these lecture notes will interest peo- ple other than mathematicians. For this reason I have often shied away from he "Definition-Lemma-Proposition-Theorem-Corollary"sequence, and I have tried to be intuitive in many places, even if this meant that the exposition be- came less succinct. I hope to succeed in sharing with my readers some of the excitement that this interdisciplinary subject has brought into my scientific life I want to take this opportunity to express my gratitude to the many people ho made the lowell conference happen: the cbms board, and the Mathematics Department of the University of Lowell, in particular Professors G. Kaiser and
INTRODUCTION 4. B. Ruskai. The success of the conference, which unexpectedly turned out to have many more participants than customary for CBMS conferences, was due in large part to its very efficient organization. As experienced conference organizer . M. James(1991)says, "every conference is mainly due to the efforts of a single individual who does almost all the work" for the 1990 Wavelet CBMs conference, this individual was Mary Beth Ruskai. I am especially grateful to her for proposing the conference in the first place, for organizing it in such a way that I had a minimal paperwork load, while keeping me posted about all the developments, and for generally being the organizational backbone, no small task. Prior to the conference I had the opportunity to teach much of this material as a graduate course in the Mathematics Department of the University of Michigan, in Ann Arbor. My one-term visit there was supported jointly by a Visiting Professorship for Women from the National Science Foundation, and by the University of Michigan. I would like to thank both institutions for their support. I would also like to thank all the faculty and students who sat in on the course and who provided feedback and useful suggestions. The manuscri was typeset by Martina Sharp, who I thank for her patience and diligence, and for doing a wonderful job. I wouldn't even have attempted to write this book without her. I am grateful to Jeff Lagarias for editorial comments. Several people helped me spot typos in the galley proofs, and i am grateful to all of them; I would like to thank especially Pascal Auscher, Gerry Kaiser, Ming-Jun Lai, and Martin Vetterli. All remaining mistakes are of course my responsiblity. I also would like to thank Jim Driscoll and Sharon Murrel for helping me prepare the author index. Finally, I want to thank my husband Robert Calderbank for being extremely supportive and committed to our two-career-track with family, even though it occasionally means that he as well as i prove a few theorems less ngri ATET Bell Laboratories Rutgers University In this second printing several minor mistakes and many typographical errors have been corrected. I am grateful to everybody who helped me to spot them I have also updated a few things: some of the previously unpublished references have appeared and some of the problems that were listed as open have been solved. I have made no attempt to include the many other interesting papers on wavelets that have appeared since the first printing; in any case, the list of references was not and is still not meant as a complete bibliography of the subject ngrid Daubechies, Sept. 1992
Preliminaries and Notation This preliminary chapter fixes notation conventions and normalizations. It also states some basic theorems that will be used later in the book. For those less familiar with Hilbert and Banach spaces, it contains a very brief primer. (This primer should be used mainly as a reference to come back to in those instances when the reader comes across some Hilbert or Banach space language that she or he is unfamiliar with. For most chapters, these concepts are not used. Let us start by some notation conventions. For E E R, we write z for the argest integer not exceeding =max{m∈z;n≤x} For example, 13/2=1,[-3/2=-2, 1-2]=-2 Similarly, [=l is the smallest integer which is larger than or equal to z If a-0(or oo), then we denote by o(a)any quantity that is bounded by a constant times a, by o(a)any quantity that tends to o(or oo) when a does. The end of a proof is always marked with a s; for clarity, many remarks or examples are ended with a o In many proofs, C denotes a "generic"constant, which need not have the same value throughout the proof. In chains of inequalities, I often use C,C,C",……orC1,C2,C3,…… to avoid confusion We use the following convention for the Fourier transform(in one dimension) (万∫)(E)=f()= dxe-1ff(a) (0.0.1) With this normalization, one has )12‖fE 1/p IfM p= dz If(z)IP (0.0.2)
PRELIMINARIES AND NOTATION Inversion of the Fourier transform is then given by ∫(r) V2n/de(F)()=(f)y(x), (0.03 (x)=9(-x) Strictly speaking, (0.0.1),(0.0. 3) are well defined only if f, respectively Ff, are bsolutely integrable; for general L-functions f, e.g. we should define Ff via a limiting process(see also below). We will implicitly assume that the adequate limiting process is used in all cases, and write, with a convenient abuse of no- tation, formulas similar to(0.0. 1)and (0.0.3)even when a limiting process is understood A standard property of the Fourier transform is =(i)4()() drfo()26, where -oo< a<6<oo. then its Fourier transform f(E)is well defined also for complex 5, and 1(E) s(2m)-1/ dr e(lme)r 1f(z) eb(m)ifIm≥0 (Im E) ifIm5≤0 If f is moreover infinitely differentiable, then the same argument can be applied to f(e), leading to bounds on IEI If(E). For a Coo function f with support a, bl there exist therefore constants CN so that the analytic extension of the Fourier transform of f satisfies (0.0.4) Conversely, any entire function which satisfies bounds of the type(0.0.4)for all NN is the analytic extension of the fourier transform of a Coo function with support in (a, b]. This is the Paley-Wiener theorem We will occasionally encounter (tempered)distributions. These are linear naps T from the set S(R)(consisting of all Coo functions that decay faster than any negative power (1+a)-)to C, such that for all m, n E N, there exists n m for which T()≤ +1fm()
PRELIMINARIES AND NOTATION i hoids, for all f E S(R)The set of all such distributions is called S(R).Any polynomially bounded function F can be interpreted as a distribution, with F()dr F(E)f(a). Another example is the so-called" 6-function"of Dirac, &()=f(O). A distribution T is said to be supported in a, b l if T()=0 for all functions f the support of which has empty intersection with [a, b]. One can define the Fourier transform FT or T of a distribution T by T()=T()(if T is a function, then this coincides with our earlier definition). There exists a version of the Paley-Wiener theorem for distributions: an entire function T(S) is the analytic extension of the Fourier transform of a distribution T in S(R) supported in a, bl if and only if, for some NEN, CN>0, T()|≤Cx(1+|) lmIm≥0 ≤0 The only measure we will use is Lebesgue measure on R and R". We will often denote the(Lebesgue)measure of S by SI; in particular, l(a, bl=b-a (where b>a) Well-known theorems from measure and integration theory which we will use include Fatou,s lemma. In20,fn(r)-f(z)almost everywhere(i.e, the get o f points where pomtuLse convergence fauls has zero measure wnth respect to Lebesgue measure), then dr f(=)s limsup dr/n(=) In particular, if thus lim sup is finite, then f is integrable (The lim sup of a sequence is defined by limsup an= lim [sup ak;k2n; every sequence, even if it does not have a limit(such as an =(-1)"),has a lim sup(which may be oo); for sequences that converge to a limit, the lim sup coincides with the limit. Dominated convergence theorem. Suppose fn(r)-f(=)almost every where.Jf|∫n(x)≤g(x) for all n,and∫drg(x)<∞, then f is integrable,, and dxf(=)=lim dr fn(z) Fubini' g theorem.Jf∫dr∫d|f(x,y)<o,ten ∫(x,y) dy dr f(a,y)
PRELIMINARIES AND NOTATION i. e, the order of the integrations can be permuted In these three theorems the domain of integration can be any measura bset of R(or R- for Fubini) When Hilbert spaces are used, they are usually denoted by H, unless t already have a name. We will follow the mathematician's convention and scalar products which are linear in the first argument (A11+入2u2,u)={u1,t)+A2{u2,t) As usual. we have v,u)={u,u, where a denotes the complex conjugate of a, and (u, u)>0 for all u E H. define the norm Mull of u by In a Hilbert space, ull=0 implies u 0, and all Cauchy sequences respect to‖‖ have limits within the space.( More explicitly,iftn∈Ra Jun -uml becomes arbitrarily small if n, m are large enough-i. e, for all depending on 6, so that llun-umll se if n, m2 n0-, the exists 1∈ H so that the un tend to u for n→oo,ie,limn-∞‖u-tn‖= A standard example of such a Hilbert space is L2 (R),with (,9)=/d∫(x)9(x) Here the integration runs from -oo to oo; we will often drop the integr bounds when the integral runs over the whole real line Another example is e (Z), the set of all square summable sequences of plex numbers indexed by integers, with (c, d) dn Again, we will often drop the limits on the summation index when w over all integers. Both L(R)and e (z) are infinite-dimensional Hilbert Even simpler are finite-dimensional Hilbert spaces, of which C is the sta example, with the scalar product vanik hilbert spaces always have orthonormal bases, i. e, there exist fam ctors e in H #2=∑en)2
PRELIMIN ARIES AND NOTATION for all uE H.( We only consider separable Hilbert spaces, i.e., spaces in which orthonormal bases are countable ) Examples of orthonormal bases'are the Her mite functions in L(R), the sequences en defined by (en),=8n,,, with n,jE Z in e (Z)(i. e, all entries but the nth vanish), or the k vectors el,.,ek in C defined by( ec)m= &L, m, with 1 0 there should exist &( depending on e)so that‖l-ⅶ≤ 8 implies‖Aa-A啡≤∈. If we take v=0,e=1, then we find that, for some b>0,‖Al≤1if|≤b. For any w∈ we can define clearly/l≤ b and therefore Awll=ll‖Anln≤b-l.fr I Aw/lull(w#0)is bounded, then the operator A is called bounded. We have just seen that any continuous operator is bounded; the reverse is also true. The norm‖A‖ of A is defined by ‖A= sup Aull/ll=sup‖Au‖l (0.0.8) t∈,‖u‖10 It immediately follows that, for all uE 7 ‖Atll≤‖Alll Operators from H td c are called "linear functionals. " For bounded linear functionals one has Riesz@representation theorem: for any &: H-C, linear and