APPENDIX B

SOLUTIONS TO SELECTED EXERCISES

Chapter 0

3. Suppose A is the given matrix with first row 1 2 and second row 2 4; if V = (v₁, v₂), then the first element of AV is v₁ + 2v₂ and the second element is 2v₁ + 4v₂ = 2(v₁ + 2v₂). Note that if v₁ + 2v₂ = 0, then AV = 0; and so V, V = V^T AV = 0. This shows that , is not an inner product since any nonzero vector V with v₁ + 2v₂ = 0 satisfies V, V = 0 (thus violating the positivity axiom).

4. (2nd part) Part a: We wish to show that the L² inner product on the interval [a, b] satisfies the positivity axiom; this means we must show that if dt, then f(t) = 0 is zero for all a < t < b. Part b: Suppose by contradiction that there is a t₀ with f(t₀) ≠ 0. Let ∈ = |f(t₀|/2 > 0 in the definition of continuity; which states that there is a δ > 0 such that if |t – t₀| < δ, then |f(t₀) < ∈ = |f (t₀)|/2 > ∈ = |f(t₀)|/2 > 0. This implies |f (t)|>|f (t₀)|/2 for |t –l t₀| < δ. Part c: Assuming δ is chosen small enough so that the interval [t₀ – δ, t₀ + δ] is contained in [a, b], then

This shows that if f (t₀) ≠ 0, then > 0. Therefore, we conclude that if = 0, then f(t₀) = 0 for all a < t₀ < b. By taking limits as t₀ a or t₀ b, we conclude that f (a) = f(b) = 0, as well.

6. . However, f_n(t) does not converge to zero uniformly since the rate of convergence depends on how close t is to the origin.

8. No. Consider the sequence and define f_n(t) = 0 otherwise; then which does not converge to zero as n → δ; however, for all t; and so f_n → 0 uniformly.

10. The orthogonal complement of the given function f (t) = 1 is the set of all functions g that satisfy = average(g).

12. The orthonormal basis is .

13. Set b_j = cos x, e_j for 1 ≤ j ≤ 4, where e₇ is the orthonormal basis given in the solution to exercise 12; then the projection is , where

15. Note that the given functions ϕ(x), ψ(x), ψ(2x), and ψ(2x – 1) are orthogonal. The first two functions have unit L² length; the latter two have L² length equal to and . Then {e₁, e₂, e₃, e₄} is an orthonormal set. The projection of f (x) = x is

17. If u₀, v = u₁, v, then u₀ – u₁,v = 0; for all v ∈ V. Set v = u₀ – u₁ and this equation says ||u₀ – u₁||² = 0; this implies u₀ – u₀ = 0 or u₀ = u₁.

20. Suppose w belongs to Ker (A*); then A*w =0, which means that 0 = A*w, v = w, Av for all v ∈ V. This implies that w is orthogonal to the range of A. Conversely, if w is orthogonal to the range of A, then 0 = w, Av = A*w, v for all v ∈ V. This means that A*w = 0 and hence w ∈ Ker(A*).

22. If v₀ ∈ V₀ and w ∈ , then (vo,w) =0, thus showing that any vector in V₀ belongs to the orthogonal complement of , i.e. V₀ ⊂ . Now suppose w belongs to the orthogonal complement of ; then w,v = 0 for all v₁ ∈ . By Theorem 0.25, we have w = v₀ + v₁, where v₀ ∈ v₁ and v₁ ∈ . Since w, v = 0, we have

Therefore v₁ = 0 and so w = v₀, which belongs to V₀. Thus, ⊂ V₀.

27. Best-fit line is y = 4x + 1.

Chapter 1

1. The partial Fourier series of f (x) = x² with N = 1 is

The plot of both f(x) = x² and F(x) over the interval – 2π ≤ x ≤ 2π is given in Figure B.1.

3. Cosine series for x² on .

5. Cosine series for x³ on I cos(nx).

7. Since | sin(x)| is an even function, only cosine terms appear in its Fourier expansion on [–π, π],which is

9. The Fourier sine series for cos x on the interval 0 ≤ x ≤ π is

12. Let

then, the Fourier series is . The plot of the partial Fourier series with N = 10 is given in Figure B.2.

16. Proof of Lemma 1.16, part 4. e^it e^is = e^i(t+s; the right side is cos(t + s) + i sin(t + s), which by the addition formula for cosine and sine is (cos t cos s – sin t sin s) + i (cos t sin s + cos s sin t). This agrees with the left side by expanding out e^it e^is = (cos t + i sin t)(cos s + i sin s) into its real and imaginary parts. Proof of Lemma 1.16, part 6. d/dt{e^it} = ie^it; the left side is d/dt{cos t + i sin t} which equals – sin t + i cos t; this is the same as the right side: ie^it = i(cos t + i sin t). Proof of Theorem 1.20. To show that the functions is orthonormal, we compute using Lemma 1.16, parts 4 and 6:

If n ≠ m, then the above integral is , then the above integral becomes . The formula for the α_n given in Theorem 1.20 now follows from Theorem 0.18.

19. First, extend f so that it is periodic with period 2; and note that its periodic extension is discontinuous at ±1/2, ±1, ±3/2,... and continuous everywhere else. Using Theorem 1.22, the Fourier series, F(x), of f converges to f(x) at each point, x, where f is continuous. At the points of discontinuity, F(x) is the average of the left and right limits of f by Theorem 1.28. Therefore, the value of F(x) at x = ±1/2, ±1, ±3/2,... is equal to 1/2.

21. Since the function, ƒ, in the sawtooth graph of Example 1.10 is everywhere continuous and piecewise differentiable, its Fourier series converges to f (in fact, the convergence is uniform by Theorem 1.30). Thus, from Example 1.10

Setting x = 0, we obtain

which after rearrangement becomes .

23a. Convergence is pointwise, but not uniform, to the graph in Figure B.3 (three periods drawn).

23d: Convergence is uniform to the graph in Figure B.4, which is the periodic extension of f (three periods drawn):

25. Using the change of variables x = t – 2π, we have

where the last equality uses the fact that F is periodic: F(t – 2π) = F(t). Now relabel the variable t back to x in the integral on the right. To prove Lemma 1.3, we have

Using the first part of this problem, the first integral on the right is Reversing the order of the summands gives

29. Let sin nx; let F(x) be the same expression where the upper limit on the sum is ∞; we want to show that F_N converges to F uniformly; that is, we want to show that for every ∈ there is an N₀, independent of x, such that for all N ≥ N₀, and all x. We have

Since converges, there is an N₀ with N₀. From the above inequality, we conclude that for N ≥ N₀ and all x.

33. Answer = π⁴/90.

38.

Chapter 2

2. We have

Since f (t) = sin 3t cos λt is an odd function, the integral of this part is zero; so

Subtracting the identities

with u = 3t and v = λt and then integrating gives

So,

4. We have

If f is even, then f (t) sin λt is odd and so its integral over the entire real line is zero. Therefore , which is real-valued if f is real-valued. Similarly, if f is odd, then f(t)cos λt is odd and so its integral over the entire real line is zero. In this case, sin λt, which is purely imaginary if f is real-valued.

6. We have

where the last equality follows by completing the square in t of the exponent. We then have

where the last equality follows from a complex translation u = t + iλ/(2s) [this translation requires some complex variable theory (i.e., Cauchy’s Theorem, etc.) to justify rigorously]. Therefore

We now let to obtain

The value of the integral on the right is .

8. We wish to show that if h (t₀) ≠ 0 for some t₀ < 0, then the filter L, defined by , is not causal. Let’s assume that h (t₀) > 0 (the case when h (t₀) < 0 is similar). We must find a function f which is zero for x < 0, but where L(f) is nonzero on t < 0. If h (t₀) > 0, then let ∈ = h (t₀)/2 > 0. Since h is continuous, there is a δ > 0, such that h(t) > ∈ for t₀ – δ < t < t₀ + δ. Now let f(t) be the function that has the value 1 on the interval [0, δ] and zero everywhere else. We then have

So, we have found a function f, which is zero on {x < 0}, but L(f)(t) > 0 at t = t₀ < 0. Therefore L is not causal.

10. We have

From part 8 of Theorem 2.6, we have .

13. If , then

If is nonzero only on the interval ω₁ ≤ λ ≤ ω₂, then is nonzero only on the interval

So we can apply Theorem 2.23 to g with the value and obtain

Inserting the formula for g and simplifying, we obtain

Chapter 3

2. Theorem 3.4, Part 1: Let z_k = y_k+1 and ω = e2^πi/n; then

Let k′ = k + 1, then

Since y₀ = y_n, and term in the sum on the right is unchanged by letting k′ = 0; so

which establishes Part 1.

Theorem 3.4, Part 3: We have

We can now switch order of summation and factor to obtain

where the last equality holds with the change of index j′ = j – l. The term on the right is

4, 5. With the given values, ω = 6 is the vibrating frequency for the sinusoidal part of u(t). A plot of the fft of the values of u over 256 grid points on the interval [0,4] indicates that the largest frequency component is ; this corresponds to the vibrating frequencies 4(2π/4) = 2π which is close to the value ω = 6 as expected.

8. If the tolerance is set at 5 (so zero-out all the terms with absolute value less than 5), then approximately 213 of the 256 FFT coefficients will be set to zero (about 83% compression); the resulting relative error of the signal is approximately 13%.

12. Equation (3.11) states that . We now wish to take the DFT of both sides. The first part of Theorem 3.4 states the following:

Using these two equations, the DFT of Eq. (3.11) is

Dividing both sides by (assuming this is nonzero) yields Eq. (3.12).

14a. If u is a sequence in S_n, then the sequence z (defined by Z_k = U_k+1) and the sequence w (defined by w_k = Z_k–1) are both in S_n. Since L[u] = z + w – 2u, clearly L[u] belongs to S_n as well.

14b. Let et be the sequence with 1 in the kth slot and zeros elsewhere. The kth column of the matrix M₄ is comprised of the coefficients of the sequence L[e]. Since L[e] = e_k–1 – 2_ek + e_k+1, the kth column has the values 1, –2, and 1 in the k – 1, k, and k + 1 entries, respectively. When k = 1, then k – 1 = 0, which corresponds to the fourth entry (using mod 4 arithmetic), which is why the 1 appears in the (4,1) entry; similar considerations occur in the fourth column.

14c. The eigenvalues are 0, –2, –4, –2 with corresponding eigenvectors equal to the columns of F₄.

15a. A_j,k = a_j–k.

15b. Note that A_j,kx_k = a_j–kx_k; The jth entry of AX is . This is just the j’th entry of a * x.

Chapter 4

1. The decomposition of f into V₂ elements is

The decomposition of f into V₀, W₀, and W₁ components is

3. Suppose v₁,... ,v_n is an orthonormal basis for A and w₁,..., w_m is an orthonormal basis for B; then the collection v₁,...,v_n, w₁,... ,w_m is orthonormal since the v′s are orthogonal to the w′s. This collection also spans A ⊕ B (since the v′s span A and the w′s span B). Therefore, the collection v₁,..., v_n, w₁,..., w_m is a basis for A ⊕ B. The dimension of A ⊕ B is the number of its basis elements so dim(A ⊕ B) = n + m = dim A + dim B. If A and B are not orthogonal, then there could be some nonzero intersection A ∩ B. Then

(see any standard linear algebra text).

5. Suppose is orthogonal (in L²) to each ϕ(x – l). Then we will show that a_2l+1 = –a_2l, for each l. From the given information, we have Since ϕ(2x – k) has value one on the interval [k/2, k/2 + 1/2] and is zero everywhere else, the only contributions to the sum on the right are the terms when k = 2l and k = 2l + 1. So the above equation becomes

Therefore a₂i+i + a₂¡ = 0, as desired.

7. We use the reconstruction algorithm: is even, and is odd. Since we are given and , the reconstruction algorithm with j =2 gives

Now, we use this information and the given values for with the reconstruction algorithm with j = 3 to obtain

So, the reconstructed h is where given above.

10. With the tolerance = 0.1, we can achieve 80% compression (i.e., 80% of the wavelet coefficients set equal to zero); the resulting reconstruction is accurate to within a relative error of 2.7% (i.e., the compressed signal, yc, is accurate to within the original signal y to within a relative error 0.027). With a tolerance of 0.5, we can achieve 94% compression with a relative error of 8%.

Chapter 5

2b. Support is {x ≥ –5}. Note that the support must be a closed set; so even though f = 0 at the isolated points x = 0 and x = 1, these points must be included in the support. This function is not compactly supported.

3. The proof of Parseval’ s equation here is analogous to the proof of Parseval’ s equation for Fourier series given in Theorem 1.40. We let and . We have

where the last equality uses the orthonormality of the u_j. We will be done once we show that we can let N ∞. This argument is the same as that given after Eq. (1.43).

4a. From the two-scale relationship, we have

where the last equation follows by a change of index j =2l + k. Since the collection {2^1/2ϕ(2x – k), k = ... –2, –1, 0, 1,...} is an orthonormal set, Parseval’s Equation states that

Since the left side is δ_0.l, the identity in Theorem 5.9, Part 1 now follows.

5. First note the scaling equation: . Next note that the set of ϕ(2x – k)2^1/2, where k is any integer, is an orthonormal collection of functions. So we have the following:

Therefore . If the support of ϕ is compact, say contained in the set [–M, M], then for |j| > 3M the supports of ϕ(x) and ϕ(2x – j) do not overlap (i.e., one or both of these functions is zero for any x). Therefore, p_j is zero for |j| 3M, and the set of nonzero p_j is finite.

6a. From Theorem 0.21, the orthogonal projection of u onto V_j) is

where ϕ_j,k(x) = 2^j/2ϕ(2^j x – k). The inner product on the right is

(B.1)

For later use in 6b, note that

This inequality is established by letting y = 2^jx – k in the right side of the previous equation.

6b. Now suppose the support of ϕ is contained in the set [–M, M]. As x ranges over the interval [0, 1], then 2^jx – k ranges over the interval 2^j[0, 1] – k. If this set is disjoint from the interval [–M, M] or contains it, then . Let Q be the set of indices, k, where this does not occur. The number of indices in Q is approximately 2M. Therefore, examining the equation for u_j from 6a and using (B.1), we conclude that

since ||ϕ_j,k|| = 1. Note that the right side goes to zero as j ∞. Therefore ||u – u_j|| ≥ (1/2)||u|| = 1/2 for large enough j. Note: A simpler proof can be given using Schwarz’s inequality.

8a. The set V_j) is the collection of L² functions whose Fourier transform has support in [–2^jπ 2^jπ]. Note that this set increases as j increases, thus establishing Property 1 of Definition 5.1. The closure of the union of the V_j over all j contains L² functions without any restriction on the support of their Fourier transform; this includes all L² functions, which is Property 2. The intersection of V_j) is the set of functions whose Fourier transform is supported only at the origin (i.e., when j = 0). An L² function with support at only one point (the origin) is the zero function; thus the intersection of all the V_j is the zero function, establishing Property 3. For Property 4, note that we have

by Property 7 of Theorem 2.6. If f belongs to V_j), then the support of f(ξ) is contained in [–2^jπ, 2^jπ]. This implies that the support of f(2^jξ) is contained in [–2⁰π, 2⁰π]. By the above equation, this means that f(2^–j) is contained in V₀. Conversely, if f(2^–jx) is contained in V₀, then the above reasoning can be reversed to conclude that f is in Vj).

8b. By the Sampling Theorem (Theorem 2.23 with Ω = 2^jπ), any f in V_j can be expressed as

By canceling the common factors of π, we conclude that

which shows that sinc(2^jx – k) is a basis for V_j). To show that sinc(x – k) is orthogonal, we use Theorem 5.18. Note that an easy computation, analogous to that in Eq. (5.27), shows that if g is the function that is one on the interval (–π, π], then . Therefore . We therefore have

So, sine satisfies the orthogonality condition by Theorem 5.18.

9b. The scaling relation for the tent function is

12. Let a_j = f (j/2ⁿ) and . Since ϕ is the Haar scaling function, the value of ϕ(2ⁿx – j) is one on the interval I_j = [j2^–n, (j + 1)2^–n] and zero otherwise. So, on this interval, we have

The Mean Value Theorem implies that if |f′(x)| ≤ M for all |f (x) –1 f (y)| ≤ M|x – y|. Therefore the right side is bounded above by M(length of I_j), or M2^–n. Thus we obtain

The right side is less than ∈ whenever 2ⁿ > M/∈, or equivalently n > log₂(M/∈).

13. We have ; inserting this into the definition of Q, we obtain

If |z| = 1, then 1 = |z|² = z, and so z = z^–1. Therefore

Now change index and let j = 1 – k; note that (–1)^j = (–1)^k+1; we obtain , as claimed.

17. Suppose that there are a finite number of p_k, say for |k| ≤ N, and let

We are asked to show that if ϕ₀ is the Haar scaling function, then all the ϕ_n, and hence ϕ Theorem 5.23 has compact support. Suppose the support of ϕ_n–1 is contained in the set {|x| ≤ r}, where r is chosen larger than 1 (since the support of ϕ₀ is contained in the unit interval). Let R be the maximum of r and N. Note that the right side of the above equation is zero unless

for |k| ≤ N ≤ R. Therefore ϕ_n(x) = 0 unless |2x| ≤ 2R; or equivalently, |x| ≤ R. So we ϕ_n–1 is contained in {|x| ≤ R}, and R is larger than N, then the support of ϕ_n–1 is also contained in {|x| ≤ R}. Since the support of ϕ₀ is contained in the interval [–1, 1] and noting that R > 1, we conclude that the support of each ϕ₀ is contained in the interval [–R, R]. Letting n ∞, we see that the support of ϕ is also contained in {|x| ≤ R}, as desired.

Chapter 6

2. We have , where

We are to compute derivatives of and evaluate them at ξ = 0, which corresponds to the point . Note that any derivative of (z + 1)^N of order less than N evaluated at z = – 1 is zero. Therefore and equals to . By the Chain Rule, we have

Using the product rule, any derivative of (ξ) is a sum of products of derivatives of . However, if the number of derivatives is at most N, then all the terms vanish when ξ = 0 except for the term when N derivatives fall on P_N. Therefore, we obtain

Since , Eq. (6.9) is established.

4. For exercise 9 in Chapter 4, we discretize f (t) = e^–t2/10(sin(2t) + 2cos(4t) + 0.4 sin t sin 50t) over the interval 0 ≤ t ≤ 1 into 2⁸ samples. Call the resulting vector y. Then we use the wavedec package in Matlab with “db2” (Daubechies wavelets with N = 2) on the vector y and find that 87% of the wavelet coefficients in the decomposition are less than 0.1 in absolute value. After setting these coefficients equal to zero and reconstructing (using Matlab’s waverec), we obtain a signal, y_c, with a relative error of .0174 as compared with the original vector y (i.e., .

6. The level 7 wavelet detail coefficients are zero at indices corresponding to t values less than zero or greater than 1. The largest wavelet detail occurs at t = 0 with a value of approximately –19 * 10^–4. The next largest wavelet detail occurs at t = 1 with a value of approximately –5 * 10^–4. The wavelet details between t = 0 and t = 1 are approximately 0.19 * 10^–4. The largest wavelet details correspond to (delta-function) spikes in the second derivative at these points.