Davidson K.R., Donsig A.P. Real Analysis with Real Applications

Подождите немного. Документ загружается.

15.5 Daubechies Wavelets 533

–1

–1 1

FIGURE 15.4. The Daubechies wavelet.

D. Write out the details of the argument that

ϕ(x) dx = 1 implies that

= 2.

E. Deﬁne Q[

√

3] as the set of numbers x +

√

3y, where x, y ∈ Q.

(a) Show that if a +

√

3b = x +

√

3y, then a = x and b = y. Thus we can represent

elements of Q[

√

3] uniquely as ordered pairs.

(b) Show that addition, multiplication, and division operations in Q[

√

3] are closed and

can be expressed using rational operations.

uating ϕ and ψ given at the end of this section.

F. Let ϕ be the Daubechies scaling function. Let D

be the set {a/2

: k ∈ N, a ∈ Z}

and deﬁne the set of dyadic rationals to be D = ∪

n≥1

. Further, deﬁne D

[

√

3] to

be the set {a +

√

3b : a, b ∈ D

} and likewise deﬁne D[

√

3].

(a) Show that for d ∈ D, ϕ(d) ∈ D[

√

3].

(b) If a +

√

3b is deﬁned as a −

√

3b, show that for d ∈ D, ϕ(3 −d) = ϕ(d).

HINT: Prove it for D

using induction on n.

k∈Z

ϕ(d − k). HINT: See the previous hint.

(d) Show that

k=0

kϕ(k) =

j=0

2ja

3 −

√

(e) Show that for d ∈ D, d =

k∈Z

3 −

√

+ k

ϕ(d − k).

HINT: Using part (c), show that it is enough to prove d−

3 −

√

k∈Z

kϕ(d−k)

Then use induction, part (d), and considerable calculation.

(f) Using the continuity of ϕ, deduce that for all x ∈ R,

1 =

k∈Z

ϕ(x − k), x =

k∈Z

3 −

√

+ x

ϕ(x − k).

534 Wavelets

G. Suppose that ϕ is any scaling function of compact support arising from a multiresolu-

tion analysis and its scaling relation ϕ(x) =

ϕ(2x − j).

(a) Show that

ϕ(2

−k

n) = 2

ϕ(n) for all k ≥ 1.

(b) Show that

ϕ(x) dx =

ϕ(n). HINT: Use Riemann sums and part (a).

ϕ(x − n) is constant.

H. Consider the sequence of functions ϕ

(x) = 2

k/2

ϕ(2

x) for k ≥ 0, where ϕ is the

Daubechies scaling function. Compare this family of functions to the Fej

er kernel

(Deﬁnition 14.6.1). Precisely, which properties of Fej

er kernel (Theorem 14.6.3) carry

over directly to the functions ϕ

? If a property does not carry over directly, is there

an analogous property that the functions ϕ

have?

I. The construction used in this section can be extended to wavelets of higher order (i.e.,

with more moments vanishing).

(a) Use Equation (15.5.2) and

ψ(x) dx =

ψ(x) dx = 0 to derive two addi-

tional conditions on the sequence (a

(b) Show that the following values, with all other a

zero, give an approximate solution

to these conditions.

= .470467 a

= 1.141117 a

= .650365

= −.190934 a

= −.120832 a

= .049817

functions. Although the graph suggests otherwise, this scaling function is actually

differentiable.

15.6. Existence of the Daubechies Wavelet

The purpose of this section is to establish the following:

15.6.1. THEOREM. The sequence of functions (ϕ

) converges in the L

(R)

norm to a function ϕ.

We need two computational lemmas that enable us to estimate kϕ

n+1

− ϕ

First, we compute hϕ

n+1

(x), ϕ

(x − k)i.

15.6.2. LEMMA. Deﬁne c

(k) = hϕ

n+1

, ϕ

(x − k)i for k ∈ Z and n ≥ 0.

Then c

(k) = 0 if |k| > 2, and the sequence of 5-tuples

(−2), c

(−1), c

(0), c

(1), c

(2)

for n ≥ 0

satisﬁes c

= (0, 0,

√

2−

√

, 0) and c

n+1

= T c

, where

T =







0 −1/16 0 0 0

1 9/16 0 −1/16 0

0 9/16 1 9/16 0

0 −1/16 0 9/16 1

0 0 0 −1/16 0







15.6 Existence of the Daubechies Wavelet 535

PROOF. Since ϕ

[0,1)

and

i=0

(2x − i) = a

[0,.5)

+ a

[.5,1)

+ a

[1,1.5)

+ a

[1.5,2)

we easily compute c

(0) =

+ a

2 +

√

and c

(1) =

+ a

2 −

√

and c

(k) = 0 in all other cases. Proceed by induction on n.

n+1

(k) = hϕ

n+1

, ϕ

(x − k)i

i=0

(2x − i),

j=0

n−1

(2x − 2k − j)

i=0

j=0



(2x − i), ϕ

n−1

(2x − 2k − j)

Notice that making the substitution y = 2x − i in the inner product results in a

factor of

from the change of variable of integration.

i=0

j=0



(y), ϕ

n−1

(y + i − 2k − j)

Now set l = j − i to obtain

i=0

l=−3

i+l



(y), ϕ

n−1

(y − 2k − l)

l=−3

i=0

i+l

n−1

(2k + l).

Observe immediately that if |k| ≥ 3 and |l| ≤ 3, then |2k + l| ≥ 3. Therefore,

n+1

(k) for |k| ≥ 3 depend linearly on c

(k) for |k| ≥ 3. However, c

(k) = 0 for

|k| ≥ 3, so c

(k) = 0 for all n ≥ 0 and |k| ≥ 3. So we need only be concerned

with the 5-tuple c

(−2), c

(−1), c

(0), c

(1), c

(2)

A routine calculation yields

i=0

i+l











1 when l = 0

9/16 when l = ±1

−1/16 when l = ±3

0 otherwise.

Plugging this into our identity and writing the ﬁve relations as a matrix, we obtain

n+1

= T c

. ¥

536 Wavelets

Next we compute the Jordan form of T . Note immediately that T e

= e

is an

obvious eigenvector.

15.6.3. LEMMA. The matrix T factors as T = V JV

−1

, where

V =







0 −1 2 −1 4

0 8 −4 4 0

1 0 0 −6 −8

0 −8 4 4 0

0 1 −2 −1 4







and J =







1 0 0 0 0

0 1/2 0 0 0

0 0 1/8 0 0

0 0 0 1/4 1

0 0 0 0 1/4







PROOF. We leave it to the reader to show that V J = T V and to check that V is

invertible (see the formula for V

−1

given in the proof of Theorem 15.6.4). ¥

15.6.4. THEOREM.

n≥0

kϕ

n+1

−ϕ

< ∞ and thus lim

n→∞

exists in L

(R).

PROOF. The ﬁrst step is to compute c

(0). Notice that c

= T

= V J

−1

We ﬁnd that







1 0 0 0 0

0 2

−n

0 0 0

0 0 8

−n

0 0

0 0 0 4

−n

1−n

0 0 0 0 4

−n







and V

−1







1 1 1 1 1

0 −

−

0 −

−







Thus a straightforward multiplication yields

hϕ

n+1

, ϕ

i = c

(0) = 1 −4

−n−2

(2 −

√

3)(3n + 4).

Set ε

= 4

−n−2

(2 −

√

3)(3n + 4). Notice that

kϕ

n+1

− ϕ

= hϕ

n+1

− ϕ

, ϕ

n+1

− ϕ

= kϕ

n+1

− 2hϕ

n+1

, ϕ

i + kϕ

= 2 − 2(1 −ε

) = 2ε

Consequently,

n≥0

kϕ

n+1

− ϕ

n≥0

2(2 −

√

3)(3n + 4)

n+2

n≥0

n + 2

n+2

By Exercise 4.2.B, this implies that (ϕ

) is a Cauchy sequence. Thus the limit

function ϕ is deﬁned. ¥

15.7 Approximations Using Wavelets 537

Exercises for Section 15.6

A. Verify that V J = T V and that the formula for V

−1

is correct.

B. Do the calculation to compute c

(0) as indicated in Theorem 15.6.4.

C. Verify that

n≥0

n + 2

n+2

converges. Do not compute its exact value.

D. Observe that the columns of T all sum to 1. Interpret this as saying that a related

matrix has a certain eigenvector.

E. Find lim

n→∞

. HINT: Use the Jordan form.

15.7. Approximations Using Wavelets

In this section, we approximate functions using the Daubechies wavelet sys-

tem. Our goal is to show how properties of the wavelet basis result in better (or

worse) approximations. Given that the point of wavelets is to use different kinds of

wavelets for different problems, it is worthwhile to see how to use properties of the

wavelet and scaling function. We have already devoted Chapter 14 to approxima-

tion by Fourier series and Chapter 10 to approximation by polynomials, so we can

compare approximation by wavelets to these alternatives.

Recall from the discussion of Haar wavelets that we may construct approx-

imants to functions by ﬁrst computing the projection P

f of f onto V

. Let ϕ

and {ψ

} denote the Daubechies wavelet. Let us deﬁne the projections D

onto

= span{ϕ

n,j

: j ∈ Z} by

f(x) =

j∈Z

hf, ϕ

n,j

iϕ

n,j

For n ≥ 1, we also realize this as

f(x) = D

f(x) +

n−1

k=0

j∈Z

hf, ψ

iψ

(x).

If f has compact support, then only ﬁnitely many of these coefﬁcients are nonzero

at each level. For example, if the support is [0, 1], then there are at most three

nonzero terms in the computation of D

and at most 2

n−1

+ 2 additional terms to

compute D

f knowing D

n−1

For any wavelet arising from a multiresolution analysis, the approximants P

converge to f in L

(R). So, in particular, this is true for the Daubechies wavelets.

In this case, we can also establish uniform convergence when f is uniformly con-

tinuous. We need a variation on the ﬁrst part of the proof of Theorem 15.2.3.

15.7.1. LEMMA. Consider the Daubechies wavelets. Fix k ∈ N, j ∈ Z, and

x ∈ [j/2

, (j + 3)/2

]. For any continuous function f on R,

f(x) − 2

k/2

hf, ϕ

≤

√

3ω(f, 3 · 2

−k

538 Wavelets

PROOF. Using the substitution z = 2

t − j and

ϕ(t) dt = 1, we have

f(x) − 2

k/2

hf, ϕ

f(x) − 2

f(t)ϕ(2

t − j) dx

f(x) −

z + j

ϕ(z) dz

f(x) − f

z + j

´i

ϕ(z) dz

≤ ω(f; 3 ·2

−k

)

|ϕ(z)|dz

since for z ∈ [0, 3], we have |x−(z+j)/2

| ≤ 3/2

. Finally, the Cauchy–Schwarz

inequality shows that

|ϕ(z)|dz ≤

|ϕ(z)|

1/2

1dz

1/2

√

15.7.2. THEOREM. If f ∈ L

(R) is uniformly continuous on R, then the ap-

proximants D

f by Daubechies wavelets converge uniformly to f.

PROOF. From Exercise 15.5.G, we have

j∈Z

ϕ(2

x − j) = 1. Multiplying this by

f(x), we have

|f(x) − D

f(x)| =

j∈Z

f(x)ϕ(2

x − j) −

j∈Z

hf, ϕ

iϕ

(x)

≤

j∈Z

f(x) − 2

k/2

hf, ϕ

ϕ(2

x − j)

≤

√

3ω(f, 3 · 2

−k

)

j∈Z

|ϕ(2

x − j)|

≤ 3

√

3kϕk

∞

ω(f, 3 · 2

−k

because for any x, there at most three j so that ϕ(2

x − j) 6= 0. By the uniform

continuity of f, lim

k→∞

ω(f, 3 · 2

−k

) = 0. Thus lim

k→∞

kf − D

f(x)k

∞

= 0. ¥

15.7.3. REMARK. This proof does something even better because of the local

nature of the Daubechies wavelets. If f is not continuous everywhere, but is con-

tinuous on a neighbourhood [a −δ, a + δ], the same argument shows that the series

converges uniformly on [a−ε, a+ε] for ε < δ. We will use this in Example 15.7.4.

Theorem 15.2.3 likewise shows that when f is continuous, H

f converges to

f uniformly. In fact, kH

f − fk

∞

≤ ω(f;2

−n

). So if f has Lipschitz constant

L, the error is at most 2

−n

L. Since the number of coefﬁcients in H

f doubles

15.7 Approximations Using Wavelets 539

when n increases by 1, this is not surprising. We now have a comparable rate of

convergence for Daubechies wavelets.

In approximating a function, a reasonable measure of the size of the approxi-

mant is the number of coefﬁcients used. For f ∈ L

(0, 1), we have

f(x) = hf, ϕiϕ(x) +

n−1

k=0

−1

j=0

hf, ψ

iψ

(x)

and so H

f uses 2

coefﬁcients. If there is a bound on the number of coefﬁcients

that we can use, due to storage limitations, for example, one choice is to use the

largest value of n so that H

f does not have too many coefﬁcients. It is frequently

better to use a larger value of n and then replace small coefﬁcients with zero. This

has the advantage that if f has large irregularities at small resolution, these will

appear in the approximation.

15.7.4. EXAMPLE. Consider the function given by

f(x) =

(

x if x ∈ (−π, π),

0 if |x| ≥ π.

In Section 14.5, we analyzed the how the partial sums S

f of the Fourier series

approximated f near the discontinuity at π. The Fourier series for f on (−π, π) is

f(x) ∼ 2

∞

k=1

(−1)

k+1

sinkx,

which converges very slowly. Even at a point well away from the discontinuity,

convergence is slow. For example, if x = π/2, then we get

f(π/2) = 2

∞

k=0

(−1)

2k + 1

To get 2

k=0

(−1)

/(2k + 1) within 10

−6

of the exact sum of the series, we need

n ≥ 500, 000. (To be fair, we can do better with Fej

er kernels, but the behaviour is

not optimal even then.)

The Haar wavelet approximations H

f are the step functions taking the av-

erage value of f over each interval of length 2

−n

. It is not difﬁcult to see that

except for two intervals about the discontinuities ±π, the convergence is uniform.

The maximum error is 2

−n−1

. Since the number of coefﬁcients needed is roughly

n+1

π, we see that this convergence is not much more efﬁcient than the Fourier se-

ries globally. However, to compute f(π/2), note that only n terms in the expansion

f are nonzero at π/2. Thus to compute this value within 10

−6

, we only need 19

terms since 2

−20

< 10

−6

Even better, the vanishing moments of the Daubechies wavelets ensure that so

long as the support of ψ

does not contain ±π, thecoefﬁcient hf, ψ

iwill be zero.

Since ψ has support in [0, 3], each ψ

has support in an interval of length 3/2

540 Wavelets

namely [j/2

, (j + 3)/2

]. So for each k, there are only six nonzero coefﬁcients

for ψ

to contribute to the whole series.

Returning to the point π/2, notice that for the support of ψ

to contain both

π/2 and π, we must have 3 · 2

−k

> π/2 or k ≤ 0. Thus D

f(π/2) = D

f(π/2)

for all n ∈ N. Indeed by Remark 15.7.3, this series converges uniformly to f on

any interval around π/2 that is bounded away from ±π. In particular, we have

f(π/2) = lim

n→∞

f(π/2) = D

f(π/2). So only three nonzero coefﬁcients are

involved in recovering this value exactly.

We can use the vanishing of the moments to obtain a better bound when the

function f is C

. Thus as for Fourier series, the Daubechies wavelet coefﬁcients

will die off quickly if the function is smooth. Moreover, because of the local nature

of these wavelets, if f is smooth on some small interval, the same analysis shows

that the wavelet series converges rapidly on that interval.

15.7.5. THEOREM. If f is twice differentiable on [(j − 2)/2

, (j + 2)/2

where j, k ∈ Z, and f

bounded by B on this interval, then

hf, ψ

≤

5k/2

PROOF. Substituting t = 2

x − j, we obtain

hf, ψ

i =

+∞

−∞

f(x)2

k/2

ψ(2

x − j) dx = 2

−k/2

+∞

−∞

t + j

ψ(t) dt.

This integral may be limited to [−1, 2], the support of ψ.

On [(j − 2)/2

, (j + 2)/2

], we have a Taylor series expansion for f centred

at the point b = j/2

, namely

f(x) = f(b) + f

(b)(x − b) +

(c)

(x − b)

for some point c between x and b. The vanishing moment conditions on ψ imply

that

(mx + d)ψ(x) dx = 0. As x − b = (t + j)/2

− j/2

= t/2

, we end up

with

hf, ψ

i = 2

−k/2

(c)

−1

ψ(t) dt.

Since t

≤ 4, we obtain

hf, ψ

≤

5k/2

−1

|ψ(t)|dt.

Finally, the Cauchy–Schwarz inequality shows that

−1

|ψ(t)|dt ≤

−1

|ψ(t)|

1/2

−1

1dt

1/2

√

3 < 2.

15.8 The Franklin Wavelet 541

Exercises for Section 15.7

A. Show that

ϕ +

n−1

k=0

−1

j=0

∞

≤ |b

| +

n−1

k=0

3 · 2

k/2

max

| : j ∈ Z

HINT: For each x and k, how many ψ

(x) 6= 0?

B. Recall the Cantor function f on [0, 1] from Example 5.7.8. Find the zero coefﬁcients

hf, ψ

i for k = 1, 2, 3, 4. What can you conclude about the functions D

C. (a) For the function f in Example 15.7.4, ﬁnd the least k ∈ N so that f (3) = D

f(3).

(b) In general, ﬁnd a function K(δ) so that for k ≥ K(δ), f(π − δ) = D

f(π − δ).

D. For the higher-order Daubechies wavelets of Exercise 15.5.I, state and prove a version

of Theorem 15.7.5.

E. Given a function f, we can represent P

f in two ways: b

ϕ +

n−1

k=0

j∈Z

(a) For the Haar wavelets, what is the signiﬁcance of the coefﬁcients b

and a

(b) For the Haar wavelets, describe how to obtain one set of coefﬁcients from the other.

HINT: Exercise 15.2.A.

the other.

15.8. The Franklin Wavelet

It is not easy to just write down a wavelet or a scaling function. However, it is

much easier to ﬁnd a multiresolution with a scaling function that does not generate

an orthonormal basis but does something a bit weaker. The goal is to construct a

continuous piecewise linear wavelet by starting with such a system. The technique

that we describe here can be adapted and reﬁned to obtain wavelets with greater

smoothness and/or with compact support. In this section, we restrict our attention

to a single example known as the Franklin wavelet.

In these last sections, we need to take a more sophisticated view of linear maps

between Hilbert spaces.

Consider the subspaces V

of L

(R) consisting of continuous functions in

(R) that are linear on each interval [(j − 1)2

−k

, j2

−k

]. These subspaces sat-

isfy most of the requirements of a multiresolution. It is immediately evident that

is contained in V

k+1

for all k ∈ Z. Also by deﬁnition, f(x) belongs to V

ex-

actly when it is continuous and linear on each dyadic interval of length 2

−k

, which

holds precisely when f (2x) is continuous and linear on each dyadic interval of

length 2

−k−1

, which means that f(2x) belongs to V

k+1

. So the V

satisfy scaling.

The union of the V

’s is dense in all of L

(R). To see this, note that any

continuous function g with bounded support, say contained in [−2

, 2

], may be

uniformly approximated to any desired accuracy by a piecewise linear continuous

542 Wavelets

function f that is linear on dyadic intervals of length 2

−k

provided that k is sufﬁ-

ciently large. Given ε > 0, choose k and f ∈ V

so that f is also supported on

[−2

, 2

] and kg − fk

∞

< 2

−(N+1)/2

ε. It is easy to see that

kg − fk

−2

|g(x) − f(x)|

dx ≤

−2

−(N+1)/2

dx = ε

Because C

(R) is dense in L

(R), it follows that we have the density property

k∈Z

= L

(R).

Finally, we will demonstrate the separation property

k∈Z

= {0}. Suppose

that f belongs to this intersection. Let f(i) = a

for i = −1, 0, 1. Since f ∈ V

−k

for each k > 0, it is linear on [0, 2

] and on [−2

, 0]. So f(x) = a

+ (a

− a

on [0, 2

] and f (x) = a

− (a

−1

− a

)x on [−2

, 0]. Thus

kfk

≥

|f(x)|

dx =

− a

)

+ a

− a

+ a

− a

)

+ a

− a

+ a

= 2

− a

As n tends to inﬁnity, the right-hand side must remain bounded by kfk

. This

forces a

= a

= 0. Likewise, integration from −2

to 0 shows that a

−1

= 0.

Consequently f = 0 on [−2

, 2

] for every k ≥ 0. So f = 0 and the intersection

is trivial.

We have constructed a multiresolution except for the important scaling func-

tion. There is a function h, known as the hat function, which has all but one of

the properties of a scaling function. It is supported on [−1, 1], has h(0) = 1 and

h(−1) = h(1) = 0, and is linear in between. Figure 15.5 gives its simple graph.

1−1

FIGURE 15.5. The graph of the hat function h.

Notice that f(x) =

j=−n

h(x − j) is the piecewise linear function in V

which is supported on [−n −1, n + 1] and satisﬁes f(j) = a

for −n ≤ j ≤ n and

f(j) = 0 for |j| > n. So V

is spanned by translates of the hat function. Likewise,

is spanned by

k/2

h(2

x − j) : j ∈ Z

. The problem with h is that these

translates are not orthogonal to each other. But it does have a weaker property that

serves as a substitute.