PREFACE AND OVERVIEW

Fourier series and the Fourier transform have been around since the 1800s, and many research articles and books (at both the graduate and undergraduate levels) have been written about these topics. By contrast, the development of wavelets has been much more recent. While its origins go back many decades, the subject of wavelets has become a popular tool in signal analysis and other areas of applications only within the last decade or two, partly as a result of Daubechies’ celebrated work on the construction of compactly supported, orthonormal wavelets. Consequently, most of the articles and reference materials on wavelets require a sophisticated mathematical background (a good first-year real analysis course at the graduate level). Our goal with this book is to present many of the essential ideas behind Fourier analysis and wavelets, along with some of their applications to signal analysis to an audience of advanced undergraduate science, engineering, and mathematics majors. The only prerequisites are a good calculus background and some exposure to linear algebra (a course that covers matrices, vector spaces, linear independence, linear maps, and inner product spaces should suffice). The applications to signal processing are kept elementary, without much use of the technical jargon of the subject, in order for this material to be accessible to a wide audience.

FOURIER ANALYSIS

The basic goal of Fourier series is to take a signal, which will be considered as a function of the time variable t, and decompose it into its various frequency components. The basic building blocks are the sine and cosine functions

Figure P.1. Plot of f(t) = sin(f) + 2cos(3f) + .3 sin(50f).

which vibrate at a frequency of n times per 2it interval. As an example, consider the function

This function has three components that vibrate at frequency 1 (the sin t part), at frequency 3 (the 2 cos(3t) part), and at frequency 50 (the 0.3 sin(50t) part). The graph of f is given in Figure P.1.

A common problem in signal analysis is to filter out unwanted noise. The background hiss on a cassette tape is an example of high frequency (audio) noise that various devices (Dolby filters) try to filter out. In the previous example, the component, 0.3 sin(50t), contributes the high-frequency wiggles to the graph of f in Figure P.1. By setting the coefficient 0.3 equal to zero, the resulting function is

whose graph (given in Figure P.2) is the same as the one for f but without the high frequency wiggles.

The preceding example shows that one approach to the problem of filtering out unwanted noise is to express a given signal, f (t), in terms of sines and cosines,

and then to eliminate (i.e., set equal to zero) the coefficients (the a_n and b_n) that correspond to the unwanted frequencies. In the case of the signal f just presented, this process is easy since the signal is already presented as a sum of sines and cosines. Most signals, however, are not presented in this manner. The subject of Fourier series, in part, is the study of how to efficiently decompose a function into a sum of cosine and sine components so that various types of filtering can be accomplished easily.

Figure P.2. Plot of f(t) = sin(t) + 2cos(3t).

Another related problem in signal analysis is that of data compression. Imagine that the graph of the signal f(t) in Figure P.1 represents a telephone conversation. The horizontal axis is time, perhaps measured in milliseconds, and the vertical axis represents the electric voltage of a sound signal generated by someone’s voice. Suppose this signal is to be digitized and sent via satellite overseas from America to Europe. One naive approach is to sample the signal every millisecond or so and send these data bits across the Atlantic. However, this would result in thousands of data bits per second for just one phone conversation. Since there will be many such conversations between the two continents, the phone company would like to compress this signal into as few digital bits as possible without distorting the signal. A more efficient approach is to express the signal into its Fourier series: f(t) = ∑_n ^a_n cos(nt) + b_n sin(nt) and then discard those coefficients, a_n and b_n, which are smaller than some tolerance for error. Only those coefficients that are above this tolerance need to be sent across the Atlantic, where the signal can then be reconstructed. For most signals, the number of significant coefficients in its Fourier series is relatively small.

WAVELETS

One disadvantage of Fourier series is that its building blocks, sines and cosines, are periodic waves that continue forever. While this approach may be quite appropriate for filtering or compressing signals that have time-independent wave-like features (as in Figure P.1), other signals may have more localized features for which sines and cosines do not model very well. As an example, consider the graph given in Figure P.3. This may represent a sound signal with two isolated noisy pops that need to be filtered out. If these pops are isolated, then sines and cosines do not model this signal very well. A different set of building blocks, called wavelets, is designed to model these types of signals. In a rough sense, a wavelet looks like a wave that travels for one or more periods and is nonzero only over a finite interval instead of propagating forever the way sines and cosines do (see Figure P.4 for the graph of the Daubechies N = 2 wavelet). A wavelet can be translated forward or backwards in time. It also can be stretched or compressed by scaling to obtain low- and high-frequency wavelets (see Figure P.5). Once a wavelet function is constructed, it can be used to filter or compress signals in much the same manner as Fourier series. A given signal is first expressed as a sum of translations and scalings of the wavelet. Then the coefficients corresponding to the unwanted terms are removed or modified.

Figure P.3. Graph of a signal with isolated noise.

Figure P.4. Graph of Daubechies wavelet.

Figure P.5. High-frequency Daubechies wavelet.

In order to implement efficient algorithms for decomposing a signal into an expansion (either Fourier or wavelet based), the building blocks (sines, cosines or wavelets) should satisfy various properties. One convenient property is orthogo-nality, which for the sine function states

The analogous properties hold for the cosine function as well. In addition, f₀ sin(nf) cos(mt) dt = 0 for all n and m. We shall see that these orthogonality properties result in simple formulas for the Fourier coefficients (the a_n and b_n) and efficient algorithms (fast Fourier transform) for their computation.

One of the difficult tasks in the construction of a wavelet is to make sure that its translates and rescalings satisfy analogous orthogonality relationships, so that efficient algorithms for the computation of the wavelet coefficients of a given signal can be found. This is the reason why one cannot construct a wavelet simply by truncating a sine or cosine wave by declaring it to be zero outside of one or more of its periods. Such a function, while satisfying the desired support feature of a wavelet, would not satisfy any reasonable orthogonality relationship with its translates and rescales and thus would not be as useful for signal analysis.

OUTLINE

The text has eight chapters and two appendices. Chapter 0, which discusses inner product spaces, contains the necessary prerequisites for Chapters 1 through 7. The primary inner product space of interest is the space of square integrable functions, which is presented in simplified form without the use of the Lebesgue integral. Depending on the audience, this chapter can be covered at the beginning of a course or this material can be folded into the course as the need arises. Chapter 1 contains the basics of Fourier series. Several convergence theorems are presented with simplifying hypothesis so that their proofs are manageable. The Fourier transform is presented in Chapter 2. Besides being of interest in its own right, much of this material is used in later chapters on wavelets. An informal proof of the Fourier inversion formula is presented in order to keep the exposition at an elementary level. A formal proof is given in the Appendix. The discrete Fourier transform and fast Fourier transform are discussed in Chapter 3. This chapter also contains applications to signal analysis and to the identification of the natural vibrating frequency (or sway) of a building.

Wavelets are discussed in Chapters 4–7. Our presentation on wavelets starts with the case of the Haar wavelets in Chapter 4. The basic ideas behind a mul-tiresolution analysis and the desired features of wavelets, such as orthogonality, are easy to describe with the explicitly defined Haar wavelets. However, the Haar wavelets are discontinuous and so they are of limited use in signal analysis. The concept of a multiresolution analysis in a general context is presented in Chapter 5. This gives a general framework that generalizes the structure of the wavelet spaces generated by the Haar wavelet. Chapter 6 contains the construction of the Daubechies wavelet, which is continuous and orthogonal. Prescriptions for smoother wavelets are also given. Chapter 7 contains more advanced topics, such as wavelets in higher dimensions and the wavelet transform.

The proofs of most theorems are given in the text. Some of the more technical theorems are discussed in a heuristic manner with complete proofs given in Appendix A. Some of these proofs require more advanced mathematics, such as some exposure to the Lebesgue integral.

MATLAB® code that was used to generate figures or to illustrate concepts is found in Appendix C. Answers to selected exercises are given in Appendix B.

This text is not a treatise. The focus of the latter half of the book is on the construction of orthonormal wavelets. Little mention is made of bi-orthogonal wavelets using splines and other tools. There are ample references for these other types of wavelets [see, for example, Chui (1992)] and we want to keep the amount of material in this text manageable for a one-semester undergraduate course.

The basics of Fourier analysis and wavelets can be covered in a one-semester undergraduate course using the following outline.

• Chapter 0, Sections 0.1–0.5 (Sections 0.6 and 0.7, which discuss adjoints, least squares, and linear predictive coding, are more topical in nature). This material can either be covered first or covered as needed throughout the rest of the course.
• Chapter 1 (Fourier Series)—all sections.
• Chapter 2 (The Fourier Transform)—all sections except the ones on the adjoint of the Fourier transform and on the uncertainty principle, which are more topical in nature.
• Chapter 3 (Discrete Fourier Analysis)—all sections except the Z-transform, which is more topical in nature.
• Chapter 4 (Haar Wavelet Analysis)—all sections.
• Chapter 5 (Multiresolution Analysis)—all sections.
• Chapter 6 (The Daubechies Wavelets)—all sections.

Albert Boggess
Francis J. Narcowich

College Station, Texas
College Station, Texas