A First Course in Wavelets with Fourier Analysis

By Albert Boggess and Francis J. Narcowich

A comprehensive, self-contained treatment of Fourier analysis and wavelets—now in a new edition

Through expansive coverage and easy-to-follow explanations, A First Course in Wavelets with Fourier Analysis, Second Edition provides a self-contained mathematical treatment of Fourier analysis and wavelets, while uniquely presenting signal analysis applications and problems. Essential and fundamental ideas are presented in an effort to make the book accessible to a broad audience, and, in addition, their applications to signal processing are kept at an elementary level.

The book begins with an introduction to vector spaces, inner product spaces, and other preliminary topics in analysis. Subsequent chapters feature:

• The development of a Fourier series, Fourier transform, and discrete Fourier analysis

• Improved sections devoted to continuous wavelets and two-dimensional wavelets

• The analysis of Haar, Shannon, and linear spline wavelets

• The general theory of multi-resolution analysis

• Updated MATLAB code and expanded applications to signal processing

• The construction, smoothness, and computation of Daubechies' wavelets

• Advanced topics such as wavelets in higher dimensions, decomposition and reconstruction, and wavelet transform

Applications to signal processing are provided throughout the book, most involving the filtering and compression of signals from audio or video. Some of these applications are presented first in the context of Fourier analysis and are later explored in the chapters on wavelets. New exercises introduce additional applications, and complete proofs accompany the discussion of each presented theory. Extensive appendices outline more advanced proofs and partial solutions to exercises as well as updated MATLAB routines that supplement the presented examples.

A First Course in Wavelets with Fourier Analysis, Second Edition is an excellent book for courses in mathematics and engineering at the upper-undergraduate and graduate levels. It is also a valuable resource for mathematicians, signal processing engineers, and scientists who wish to learn about wavelet theory and Fourier analysis on an elementary level.

• Language: English
• Publisher: Wiley
• Release date: Sep 20, 2011
• ISBN: 9781118211151

Book preview

Texas

0

INNER PRODUCT SPACES

0.1 MOTIVATION

For two vectors X = (x1, x2, x3), Y = (y1, y2, y3) in R³, the standard (Euclidean) inner product of X and Y is defined as

This definition is partly motivated by the desire to measure the length of a vector, which is given by the Pythagorean Theorem:

The goal of this chapter is to define the concept of an inner product in a more general setting that includes a wide variety of vector spaces. We are especially interested in the inner product defined on vector spaces whose elements are signals (i.e., functions of time).

0.2 DEFINITION OF INNER PRODUCT

The definition of an inner product in R³ naturally generalizes to Rn for any dimension n. For two vectors X = (x1, x2, …, xn), Y = (y1, y2,… , yn) in Rn, the Euclidean inner product is

When we study Fourier series and the Fourier transform, we will use the complex exponential. Thus, we must consider complex vector spaces as well as real ones. The preceding definition can be modified for vectors in Cn by conjugating the second factor. Recall that the conjugate of a complex number z = x + iy which by definition is |z|² [the square of the length of z = x + iy regarded as a vector in the plane from (0, 0) to (x, y)].

If Z = (z1, z2,…, zn), W = (w1, w2,..., wn) are vectors in Cn, then

The purpose of the conjugate is to ensure that the length of a vector in Cn is real:

The inner products just defined share certain properties. For example, the inner product is bilinear, which means

The rest of the properties satisfied by the aforementioned inner products are set down as axioms in the following definition. We leave the verification of these axioms for the inner products for Rn and Cn as exercises.

Definition 0.1 An inner product on a complex vector space V is a function 〈·, ·〉 : V × V→ C that satisfies the following properties.

Positivity: 〈v, v〉 > 0 for each nonzero v ∈ V.

Conjugate symmetry: for all vectors v and w in V.

Homogeneity: 〈cv, w〉 = c〈v, w〉 for all vectors v and w in V and scalars c ∈ C.

Linearity: 〈u + v, w〉 = 〈u, w〉 + 〈v, w〉 for all u, v, w ∈ V.

A vector space with an inner product is called an inner product space.

To emphasize the underlying space V, we sometimes denote the inner product on V by

The preceding definition also serves to define a real inner product on a real vector space except that the scalar c in the homogeneity property is real and there is no conjugate in the statement of conjugate symmetry.

Note that the second and fourth properties imply linearity in the second factor: 〈u, v + w〉 = 〈u, v〉 + 〈u, w〉. The second and third properties imply that scalars factor out of the second factor with a conjugate:

The positivity condition means that we can assign the nonzero number, ||v, as the length or norm of the vector v. The notion of length gives meaning to the distance between two vectors in V, by declaring that

Note that the positivity property of the inner product implies that the only way ||v – w|| = 0 is when v = w. This notion of distance also gives meaning to the idea of a convergent sequence {vk; k = 1, 2,...}; namely, we say that

In words, vk → v if the distance between vk and v gets small as k gets large.

Here are some further examples of inner products.

Example 0.2 Let V be the space of polynomials p = anxn +…+ a1x + a0, with aj ∈ C. An inner product on V is given as follows: If p = a0 + a1x +… + anxn and q = b0 + b1x +… + bnxn, then

Note that this inner product space looks very much like Cn+1 where we identify a point (a0,..., an) ∈ Cn+1 with a0 + a1x + … + anxn.

Example 0.3 Different inner products can be imposed on the same vector space. This example defines an inner product on C² which is different than the standard Euclidean inner product. Suppose v = (v1, v2) and w = (w1, w2) are vectors in C², define

There is nothing special about the particular choice of matrix. We can replace the matrix in the preceding equation with any matrix A which is needed for conjugate symmetry) and positive definite (meaning that all eigenvalues are positive, which is needed for the positivity axiom). Verification of these statements will be left as exercises.

0.3 THE SPACES L² AND l²

0.3.1 Definitions

The examples in the last section are all finite-dimensional. In this section, we discuss a class of infinite-dimensional vector spaces which is particularly useful for analyzing signals. A signal (for example, a sound signal) can be viewed as a function, f(t), which indicates the intensity of the signal at time t. Here t varies in an interval a ≤ t ≤ b which represents the time duration of the signal. Here, a could be –∞ or b could be +∞.

We will need to impose a growth restriction on the functions defined on the interval a ≤ t ≤ b. This leads to the following definition.

Definition 0.4 For an interval a ≤ t ≤ b, the space L²([a, b]) is the set of all square integrable functions defined on a ≤ t ≤ b. In other words,

Functions that are discontinuous are allowed as members of this space. All the examples considered in this book are either continuous or discontinuous at a finite set of points. In this context, the preceding integral can be interpreted in the elementary Riemann sense (the one introduced in Freshmen Calculus). The definition of Lphysically means that the total energy of the signal is finite (which is a reasonable class of signals to consider).

The space L²[a, b] is infinite-dimensional. For example, if a = 0 and b = 1, then the set of functions {1, t, t², t³...} is linearly independent and belongs to L²[0, 1]. The function f(t) = 1/t is an example of a function that does not belong to L.

L² Inner Product. We now turn our attention to constructing an appropriate inner product on L²[a, b]. To motivate the L² inner product, we discretize the interval [a, b]. To simplify matters, let a = 0 and b = 1. Let N be a large positive integer and let tj = j/N for 1 ≤ j ≤ N. If f is continuous, then the values of f on the interval [tj, tj+1) can be approximated by f(tj). Therefore, f can be approximated by the vector

as illustrated in Figure 0.1. As N gets larger, fN becomes a better approximation to f.

If f and g are two signals in L²[0, 1], then both signals can be discretized as fN and gN. One possible definition of 〈f, g〉L² is to examine the ordinary RN inner product of fN and gN as N gets large:

Figure 0.1. Approximating a continuous function by discretization.

The trouble with this approach is that as N gets large, the sum on the right typically gets large. A better choice is to consider the averaged inner product:

Since fN and gN approach f and g as N gets large, a reasonable definition of 〈f, g〉L² is to take the limit of this averaged inner product as N → ∞.

The preceding equation can be written as

over the partition [0, t1, t2,..., tN = 1] of [0, 1]. This approximation gets better as N gets larger. Thus, a reasonable definition of an inner product on LThis motivation provides the basis for the following definition.

Definition 0.5 The L² inner product on L²([a, b]) is defined as

The conjugate symmetry, homogeneity, and bilinearity properties are all easily established for this inner product and we leave them as exercises.

and if f is continuous, then f(t) = 0 for all t (see Exercise 4). If f(t) is allowed to be discontinuous at a finite number of points, then we can only conclude that f(t) = 0 at all but a finite number of t values. For example, the function

is not the zero function yet ∫–1¹ |f(t)|² dt = 0. However, we stipulate that two elements f and g in L²([a,b]) are equal if f(t) = g(t) for all values of t except for a finite number of t for such functions. With this convention, the positivity condition holds.

This notion of equivalence is reasonable from the point of view of signal analysis. The behavior of a signal at one instant in time (say t = 0) is rarely important. The behavior of a signal over a time interval of positive length is important. Although measure theory and the Lebesgue integral are not used in this text, we digress to discuss this topic just long enough to put the notion of equivalence discussed in the previous paragraph in a broader context. The concept of measure of a set generalizes the concept of length of an interval. The measure of an interval {a < t < b} is defined to be b – a. The measure of a disjoint union of intervals is the sum of their lengths. So the measure of a finite (or countably infinite) set of points is zero. The measure of a more complicated set can be determined by decomposing it into a limit of sets that are disjoint unions of intervals. Since intervals of length zero have no effect on integration, it is reasonable to expect that if a function f is zero on a ≤ t ≤ b except on a set of measure zero, then ∫ab f(t) dt = 0. The converse is also true: If

then f (t) = 0 on a ≤ t ≤ b except possibly on a set of measure zero. For this reason, it is reasonable to declare that two functions, f and g in L²[a, b], are equivalent on [a, b] if f (t) = g(t) for all t in [a, b] except possibly for a set of measure zero. This general notion of equivalence includes the definition stated in the previous paragraph (that two functions are equivalent if they agree except at a finite number of points). For more details, consult a text on real analysis [e.g., Folland (1992)].

The Space l². For many applications, the signal is already discrete. For example, the signal from a compact disc player can be represented by a discrete set of numbers that represent the intensity of its sound signal at regular (small) time intervals. In such cases, we represent the signal as a sequence X =..., x–1, x0, x1,... where each Xj is the numerical value of the signal at the jth time interval [tj, tj+1]. Theoretically, the sequence could continue indefinitely (either as j → ∞ or as j→ – ∞ or both). In reality, the signal usually stops after some point, which mathematically can be represented by xj = 0 for |j| > N for some integer N.

The following definition describes a discrete analogue of L².

Definition 0.6 The space l² is the set of all sequences X =..., x–1, x0, x1 ,..., xi ∈ CThe inner product on this space is defined as

for X =..., x–1, x0, x1,..., and Y =...,y–1 y0, y1,....

Verifying that 〈·, ·〉 is an inner product for l² is relatively easy and will be left to the exercises.

Relative Error. For two signals, f and g, the L² norm of their difference, || f – g || L2, provides one way of measuring how f differs from g. However, often the relative error is more meaningful:

(the denominator could also be || g || L2). The relative error measures the L² norm of the difference between f and g in relation to the size of || f || L2. For discrete signals, the l² norm is used.

0.3.2 Convergence in L² Versus Uniform Convergence

As defined in Section 0.2, a sequence of vectors {vn; n = 1, 2,...} in an inner product space V is said to converge to the vector v ∈ V provided that vn is close to v when n is large. Closeness here means that ||vn – v|| is small. To be more mathematically precise, vn converges to v if || vn – v || → 0 as n → ∞.

In this text, we will often deal with the inner product space L²[a,b] and therefore we discuss convergence in this space in more detail.

Definition 0.7 A sequence fn converges to f in L²[a, b] if || fn – f ||L2 → 0 as n → ∞. More precisely, given any tolerance ∈ > 0, there exists a positive integer N such that if n ≥ N, then || f – fn||L2 < ∈.

Convergence in L² is sometimes called convergence in the mean. There are two other types of convergence often used with functions.

Definition 0.8

1. A sequence fn converges to f pointwise on the interval a ≤ t ≤ b if for each t ∈ [a, b] and each small tolerance ∈ > 0, there is a positive integer N such that if n ≥ N, then |fn(t) – f(t)| < ∈.

2. A sequence fn converges to f uniformly on the interval a ≤ t ≤ b if for each small tolerance ∈ > 0, there is a positive integer N such that if n ≥ N, then |fn(t) – f(t)| < ∈ for all a ≤ t ≤ b

For uniform convergence, the N only depends on the size of the tolerance ∈ and not on the point t, whereas for pointwise convergence, the N is allowed to also depend on the point t.

How do these three types of convergence compare? If fn uniformly converges to f on [a,b], then the values of fn are close to f over the entire interval [a,b]. For example, Figure 0.2 illustrates the graphs of two functions which are uniformly close to each other. By contrast, if fn converges to f pointwise, then for each fixed t, fn(t) is close to f(t) for large n. However, the rate at which fn(t) approaches f(t) may depend on the point t. Thus, a sequence that converges uniformly also must converge pointwise, but not conversely.

Figure 0.2. Uniform approximation.

Figure 0.3. L² approximation.

If fn converges to f in L²[a, b], then, on average, fn is close to f; but for some values, fn(t) may be far away from f(t). For example, Figure 0.3 illustrates two functions that are close in L² even though some of their function values are not close.

Example 0.9 The sequence of functions fn(t) = tn, n = 1, 2, 3..., converges pointwise to f(t) = 0 on the interval 0 ≤ t < 1 because for any number 0 ≤ t < 1, tn → 0 as n → ∞. However, the convergence is not uniform. The rate at which tn approaches zero becomes slower as t approaches 1. For example, if t = 1/2 and ∈ = 0.001, then |tn| < ∈ provided that n ≥ 10. However, if t = 0.9, then |tn| is not less than ∈ until n ≥ 66.

For any fixed number r < 1, fn converges uniformly to f = 0 on the interval [0, r]. Indeed if 0 ≤ t ≤ r, then |tn| ≤ rn. Therefore, as long as rn is less than ∈, | fn(t)| will be less than ∈ for all 0 ≤ t ≤ r. In other words, the rate at which fn approaches zero for all points on the interval [0, r] is no worse than the rate at which rn approaches zero.

We also note that fn → 0 in L²[0, 1] because

As the following theorem shows, uniform convergence on a finite interval [a, b] is a stronger type of convergence than L² convergence.

Theorem 0.10 If a sequence fn converges uniformly to f as n → ∞ on a finite interval a ≤ t ≤ b, then this sequence also converges to f in L²[a, b]. The converse of this statement is not true.

Proof. Using the definition of uniform convergence, we can choose, for a given tolerance ∈ > 0, an integer N such that

This inequality implies

Therefore, if n ≥ N, Since ∈ can be chosen as small as desired, this inequality implies that fn converges to f in L².

To show that the converse is false, consider the following sequence of functions on 0 ≤ t ≤ 1.

We leave it to the reader (see Exercise 6) to show that this sequence converges to the zero function in L²[0, 1] but does not converge to zero uniformly on 0 ≤ t ≤ 1 (in fact, fn does not even converge to zero pointwise).

In general, a sequence that converges pointwise does not necessarily converge in L². However, if the sequence is uniformly bounded by a fixed function in L², then pointwise convergence is enough to guarantee convergence in L² (this is the Lebesgue Dominated Convergence Theorem; see Folland (1999)). Further examples illustrating the relationships between these three types of convergence are developed in the Exercises.

0.4 SCHWARZ AND TRIANGLE INEQUALITIES

The two most important properties of inner products are the Schwarz and triangle inequalities. The Schwarz inequality states |〈X, Y〉| ≤ ||X|| ||Y||. In R³, this inequality follows from the law of cosines:

where θ is the angle between X and Y. The triangle inequality states ||X + Y|| ≤ ||X|| + || Y ||. In R³, this inequality follows from Figure 0.4, which expresses the fact that the shortest distance between two points is a straight line.

The following theorem states that the Schwarz and Triangle inequalities hold for general inner product spaces.

Theorem 0.11 Suppose V, 〈·, ·〉 is an inner product space (either real or complex). Then for all X, Y ∈ V we have the following:

Schwarz Inequality: |〈X, Y〉| ≤ ||X|| ||Y||. Equality holds if and only if X and Y are linearly dependent. Moreover, 〈X, Y〉 = ||X|| ||Y|| if and only if X or Y is a nonnegative multiple of the other.

Triangle Inequality: ||X + Y|| ≤ ||X|| + ||Y||. Equality holds if and only if X or Y is a nonnegative multiple of the other.

Figure 0.4. Triangle inequality.

Proof.

Proof for Real Inner Product Spaces. Assume that one of the vectors, say Y, is nonzero, for otherwise there is nothing to show. Let t be a real variable and consider the following inequality:

The right side is a nonnegative quadratic polynomial in t, and so it cannot have two distinct real roots. Therefore, its discriminant (from the quadratic formula) must be nonpositive. In our case, this means

Schwarz’s inequality follows by rearranging this inequality.

If 〈X, Y〉 = ||X|| ||y||, then the preceding discriminant is zero, which means that the equation ||X – tY. On the other hand, 〈X, Y〉 = ||X|| ||yis a nonnegative multiple of Y, as claimed. The converse (i.e., if X is a nonnegative multiple of Y, then 〈X, Y〉 = ||X|| ||Y||) is easy and left to the reader.

Proof for a Complex Inner Product Space. If V is a complex inner product space the proof is similar. We let ϕ be an argument of 〈X, Y〉, which means

Then we consider the following inequality:

. In view of the choice of ϕ, the middle term is just –2t|〈X, Y〉| and so the term on the right equals the expression on the right side of (0.2). The rest of the argument is now the same as the argument given for the case of real inner product space.

Proof of the Triangle Inequality. The proof of the triangle inequality now follows from the Schwarz inequality:

Taking square roots of both sides of this inequality establishes the triangle inequality.

If the preceding inequality becomes an equality, then 〈X, Y〉 = ||X|| ||Y|| and the first part of the theorem implies that either X or Y is a nonnegative multiple of the other, as claimed.

0.5 ORTHOGONALITY

0.5.1 Definitions and Examples

For the standard inner product in R³, the law of cosines is

which implies that X and Y are orthogonal (perpendicular) if and only if 〈X, Y〉 = 0. We make this equation

Reviews for A First Course in Wavelets with Fourier Analysis

[Fariza Ruslan · Rating: 4 out of 5 stars]

good