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

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

15.3 Multiresolution Analysis 523

We now are ready to derive the inﬁnite decomposition.

15.3.5. THEOREM. Suppose that V

⊂ V

k+1

for k ∈ Z is the nested sequence

of subspaces from a multiresolution of L

(R). Then L

(R) decomposes as the

inﬁnite direct sum

k∈Z

PROOF. The ﬁnite decompositions are valid. So, in particular,

= V

−n

⊕ W

−n

⊕ ··· ⊕ W

n−1

Thus if f belongs to V

and is orthogonal to V

−n

, then f decomposes uniquely as

f =

n−1

k=−n

for f

∈ W

, namely f

= Q

f. Moreover, Parseval’s Theorem

shows that kf k

n−1

k=−n

If f is an arbitrary function in L

(R) and ε > 0, then by the lemma we may

choose a positive integer n so that k(I − P

)fk

+ kP

−n

< ε

. Therefore,

:= P

f − P

−n

f belongs to V

and is orthogonal to V

−n

. Consequently, we

may write g

n−1

k=−n

for f

∈ W

, where f

= Q

f. By Parseval’s

Theorem,

kf − g

= k(I − P

)f + P

−n

= k(I − P

)fk

+ kP

−n

< ε

Since ε is arbitrary, it follows that g

converges to f . That is,

f = lim

n→∞

n−1

k=−n

∞

k=−∞

and

kfk

= lim

n→∞

= lim

n→∞

n−1

k=−n

∞

k=−∞

To establish uniqueness, suppose that f =

are two decom-

positions with f

and h

in W

. Then 0 =

− h

. The norm formula from

the previous paragraph shows that 0 =

− h

. Therefore, h

= f

for all

k ∈ Z. ¥

Exercises for Section 15.3

A. Let V

be the span of integer translates of the Haar scaling function ϕ. Suppose that

f ∈ V

has bounded support and the set {f(x −j) : j ∈ Z} is orthonormal. Prove that

f(x) = ±ϕ(x − n) for some integer n.

HINT: Compute hf (x), f(x − j)i when the supports overlap on a single interval.

B. Suppose that ϕ ∈ L

(R) such that the subspaces V

satisfy orthogonality, nesting, and

scaling. Let M =

k∈Z

. Show that if f ∈ M , then f(x −t) ∈ M for every t ∈ R.

HINT: First prove this for t = j2

−k

. Then apply Exercise 15.1.F.

524 Wavelets

C. Suppose that ϕ is continuous with compact support [a, a + M], and that {ϕ

: j ∈ Z}

are orthonormal.

(a) Suppose that f ∈ V

, and express f(x) =

k/2

ϕ(2

x−j). Use the Cauchy–

Schwarz inequality to show that |f (x)| ≤ 2

k/2

Mkϕk

∞

kfk

(b) Show that

k∈Z

= {0}.

HINT: Let f ∈

k∈Z

. Use part (a) to estimate

−N

|f(x)|

dx, and let N → −∞.

15.4. Recovering the Wavelet

Let us look at the decomposition obtained in the previous section in the case of

the Haar system. Notice that ϕ =

[0,1)

satisﬁes the identity

ϕ =

[0,.5)

[.5,1)

√

On the other hand, we can write ϕ

and ϕ

in terms of ϕ and ψ. Recalling that

ψ =

[0,.5)

−

[.5,1)

, we have

√

ϕ +

√

ψ and ϕ

√

ϕ −

√

ψ.

More generally,

√

k+1,2j

√

k+1,2j+1

and

k+1,2j

√

and ϕ

k+1,2j+1

√

−

√

The subspace V

consists of those L

(R) functions that are constant on the

dyadic intervals of length 2

−k

. Now ψ

belongs to V

k+1

, it is supported on one

interval of length 2

−k

, and integrates to 0. Thus hψ

, ϕ

i = 0 for all j, j

∈ Z.

In particular, ψ

lies in W

. So W

= span{ψ

: j ∈ Z} is a subspace of W

On the other hand, the identities show that every basis vector ϕ

k+1,j

belongs

to V

+ W

, and thus V

k+1

= V

⊕ W

= V

⊕ W

. This forces the identity

= W

. So we have shown that for the Haar system, we have

= span{ψ

: j ∈ Z}.

There is a systematic way to construct a wavelet from a multiresolution. That is

the goal of this section. Let {V

} be a multiresolution with scaling function ϕ. The

construction begins with the fact that ϕ ∈ V

⊂ V

. Since ϕ

form an orthonormal

basis for V

, we may expand ϕ as

ϕ(x) =

∞

j=−∞

ϕ(2x − j) =

∞

j=−∞

√

(x),(15.4.1)

where a

= 2hϕ(x), ϕ(2x − j)i. By Parseval’s Theorem, kϕk

∞

j=−∞

Thus (a

) is a sequence in `

. Equation (15.4.1) is known as the scaling relation

for ϕ.

15.4 Recovering the Wavelet 525

15.4.2. THEOREM. Let ϕ be the scaling function generating a multiresolution

} of L

(R) with scaling relation ϕ(x) =

∞

j=−∞

ϕ(2x − j). Deﬁne

ψ(x) =

∞

j=−∞

(−1)

1−j

ϕ(2x − j).

Then ψ is a wavelet generating the wavelet basis {ψ

: k, j ∈ Z} such that

= span{ψ

: j ∈ Z} for each k ∈ Z.

PROOF. Since this proof basically consists of several long computations, we pro-

vide a brief overview of the plan. The orthonormality of {ϕ(x − j) : j ∈ Z} will

yield conditions on the coefﬁcients a

. Then we show that {ψ(x − k) : k ∈ Z} is

an orthonormal set that is orthogonal to the ϕ(x − j)’s. Finally, we show that V

spanned by V

and the ψ(x − k)’s.

In this proof, all summations are from −∞ to +∞, but for notational simplic-

ity, only the index will be indicated. We deﬁne δ

to be 1 if n = 0 and 0 otherwise.

To begin, we have



ϕ(x), ϕ(x − n)

ϕ(2x − i),

ϕ(2x − 2n − j)



ϕ(2x − i), ϕ(2x − 2n − j)

j+2n

The orthonormality of {ψ(x−j) : j ∈ Z}follows because the coefﬁcients of ψ

are obtained from ϕ by reversing, shifting by one place, and alternating sign. A bit

of thought will show that each of these steps preserves the property of orthogonality

of translations. Here we provide the direct computation:



ψ(x), ψ(x−n)

(−1)

1−i

ϕ(2x−i),

(−1)

1−j

ϕ(2x−2n−j)

(−1)

i+j

1−i

1−j



ϕ(2x − i), ϕ(2x−2n−j)

(−1)

2j+2n

1−j−2n

1−j

i+2n

= δ

So {ψ(x − j) : j ∈ Z} is orthonormal.

526 Wavelets

The fact that the ψ’s and ϕ’s are orthogonal is more subtle. Calculate



ψ(x−m), ϕ(x−n)

(−1)

1−i

ϕ(2x−2m−i),

ϕ(2x−2n−j)

(−1)

1−i



ϕ(2x−2m−i), ϕ(2x−2n−j)

but the inner product is 0 unless 2m + i = 2n + j,

(−1)

j+2n−2m

1−j−2n+2m

(−1)

p−j

where p = 2m + 1 − 2n is a ﬁxed odd integer. Thus by substituting i = p − j, we

may rearrange this sum:

(−1)

p−j

(−1)

p−i

= −

(−1)

p−i

Thus the sum must be 0. Hence the family {ψ(x − k) : k ∈ Z} is orthogonal to

the family {ϕ(x − j) : j ∈ Z}. Notice that the shift by 1 of the coefﬁcients in the

deﬁnition of ψ was to make p odd in this calculation.

Now we wish to express ϕ

(x) =

√

2ϕ(2x − p) as a linear combination of

these two families. To see what the coefﬁcients should be, we compute



(x), ϕ(x − n)

√

2ϕ(2x − p),

ϕ(2x−2n−j)

√

p−2n

since the inner product is 0 except when 2n + j = p; and similarly



(x), ψ(x − n)

√

2ϕ(2x − p),

(−1)

1−j

ϕ(2x−2n−j)

(−1)

√

1−p+2n

So now it is a matter of adding up the series to see if ϕ

(x) can be recovered.

Compute

p−2n

ϕ(x − n) =

p−2n

ϕ(2x−2n−i)

p−2n

k−2n

ϕ(2x − k)

p+2n

k+2n

ϕ(2x − k)

15.4 Recovering the Wavelet 527

and

(−1)

1−p+2n

ψ(x − n) =

(−1)

1−p+2n

(−1)

1−i

ϕ(2x−2n−i)

(−1)

p+k

1+2n−p

1+2n−k

ϕ(2x − k).

When p + k is odd,

(−1)

p+k

1+2n−p

1+2n−k

= −

2m+k

2m+p

while if p + k is even,

(−1)

p+k

1+2n−p

1+2n−k

1+2m+k

1+2m+p

When these sums over translates of ϕ(2x) and ψ(2x) are added together, the

coefﬁcients of ϕ(2x −k) are canceled when p + k is odd, while for p + k even the

two sums conveniently merge to yield the sums from the orthogonality relation for

the ϕ(x − k). Hence the sum obtained is

√

p−2n

ϕ(x − n) +

(−1)

√

1−p+2n

ψ(x − n)

k≡p mod 2

p+n

k+n

√

2ϕ(2x − k)

√

2ϕ(2x − p) = ϕ

(x).

Set W = span{ψ(x − j) : j ∈ Z}. Let us recap what we have established.

We have shown that {ψ(x − j) : j ∈ Z} is an orthonormal basis for W , that W is

orthogonal to V

, and that ϕ(2x − i) belongs to V

+ W for all i ∈ Z. Since each

ψ(x − j) is expressed in terms of the ϕ(2x − i), it is clear that W is a subspace

of V

. On the other hand, since each ϕ(2x − i) belongs to V

+ W , it follows that

= V

⊕W . Hence we deduce that W is the orthogonal complement of V

in V

;

that is, W = W

It now follows from dilation that

span{ψ

: j ∈ Z} = {2

k/2

f(2

x) : f ∈ W

} = W

Hence {ψ

: j ∈ Z} is an orthonormal basis for W

for each k ∈ Z. Since

(R) =

+∞

k=−∞

, it follows that together the collection {ψ

: k, j ∈ Z} is

an orthonormal basis for L

(R). Therefore, ψ is a wavelet. ¥

Exercises for Section 15.4

A. Show that if ϕ is a scaling function with compact support, then the scaling relation is

a ﬁnite sum.

B. Let {e

: k ∈ Z} be an orthonormal set in a Hilbert space H. Show that the vectors

x =

and y =

(−1)

p−n

are orthogonal if p is odd.

528 Wavelets

C. Given the scaling relation ϕ(x) =

ϕ(2x − j), we deﬁne the ﬁlter to be the

complex function m

(θ) =

ijθ

. Prove that |m

(θ)|

+ |m

(θ + π)|

= 1.

HINT: Compute the Fourier series of this sum, and compare the sums of coefﬁcients

obtained with those that occur in the proof of Theorem 15.4.2.

D. Suppose that ϕ is a scaling function that is bounded, has compact support, and satisﬁes

∞

−∞

ϕ(x) dx 6= 0. Let ϕ(x) =

ϕ(2x − j) be the scaling relation.

(a) Show that

= 2. HINT: Integrate over R.

(b) Show that

(−1)

= 0. HINT: Use the previous exercise for θ = 0.

15.5. Daubechies Wavelets

The multiresolution analysis developed in the last two sections can be used to

design a continuous wavelet. We start by explaining the properties we want. The

only example we have so far of a wavelet system and multiresolution analysis is

the Haar wavelet system. The Haar wavelet ψ satisﬁes

ψ(x) dx = 0

and the multiresolution analysis uses subspaces of functions that are constant on

dyadic intervals of length 2

, k ∈ Z. As a result, Haar wavelets do a good job of

approximating functions that are locally constant.

It is possible to do a better job of approximating continuous functions if we use

a wavelet that also satisﬁes

xψ(x) dx = 0.

If you computed moments of inertia in calculus, you won’t be surprised to learn

that this is called the ﬁrst moment of ψ.

Our goal in this section is to construct a continuous wavelet with this property.

To be honest, our construction is not quite complete. At one crucial point, we

will assume the uniform convergence of a sequence of functions to a continuous

function. The full construction of this wavelet requires considerable work, although

in the next section we provide a proof that the sequence converges in L

. Later in

this chapter, we give a full proof of the existence of another continuous wavelet,

known as the Franklin wavelet.

This is part of a general family of wavelets constructed by Ingrid Daubechies

in 1988. Hence these wavelets are called Daubechies wavelets.

15.5.1. THEOREM. There is a continuous function ϕ of compact support in

(R) that generates a multiresolution of L

(R) so that the associated wavelet ψ

is continuous, has compact support, and satisﬁes

ψ(x) dx =

xψ(x) dx = 0.

15.5 Daubechies Wavelets 529

PROOF. As in the last section, all of our summations are from −∞ to +∞; so only

the index is given. We will look for a function ϕ with norm 1 and integral 1, that is,

kϕk

+∞

−∞

|ϕ(x)|

dx = 1 and

+∞

−∞

ϕ(x) dx = 1.

Beyond these normalizing assumptions, we use the crucial idea of the previous

section by assuming that ϕ satisﬁes a scaling relation ϕ(x) =

ϕ(2x − j).

Since we wish ϕ to have compact support, this must be a ﬁnite sum.

Compute what follows from our assumptions:

1 = kϕk

+∞

−∞

|ϕ(x)|

dx =

+∞

−∞

ϕ(2x − j)

ϕ(2x − j),

ϕ(2x − k)

where we use the fact that {ϕ(2x − j) : j ∈ Z} is an orthogonal set of vectors in

(R) with norm 1/

√

2. In the same way,

ϕ(x) dx = 1 implies that

= 2.

From Theorem 15.4.2, if we can ﬁnd a suitable sequence (a

), then there is a

wavelet ψ, also of norm 1, which is given by

(15.5.2) ψ(x) =

(−1)

1−j

ϕ(2x − j).

Consider the consequences of the integral conditions on ψ, namely

ψ(x) dx = 0

and

xψ(x) dx = 0, to obtain two more relations that the sequence (a

) must

satisfy.

0 =

ψ(x) dx =

(−1)

1−j

ϕ(2x − j) dx

(−1)

1−j

ϕ(2x − j) dx =

(−1)

1−j

Replace 1−j with j and use (−1)

1−j

= −(−1)

to obtain

(−1)

= 0.

Similarly,

0 =

xψ(x) dx =

(−1)

1−j

xϕ(2x − j) dx

(−1)

1−j

(t + j)ϕ(t) dt

= −

(−1)

1−j

tϕ(t) dt −

(−1)

1−j

ϕ(t) dt

= −

(−1)

1−j

(−1)

(1 − k)a

530 Wavelets

(−1)

−

(−1)

= −

(−1)

Summarizing, we have the following equations:

= 2 and

(−1)

= 0.

As you can verify directly, one solution to these equations is given by

1 +

√

, a

3 +

√

, a

3 −

√

, a

1 −

√

with a

= 0 for all other j ∈ Z.

Substituting these values back into the scaling relation, we want the scaling

function to satisfy

ϕ(x) =

√

ϕ(2x)+

√

ϕ(2x−1)+

3−

√

ϕ(2x−2)+

1−

√

ϕ(2x−3)

= a

ϕ(2x) + a

ϕ(2x − 1) + a

ϕ(2x − 2) + a

ϕ(2x − 3).

It is not immediately clear why there should be a continuous function satisfying

this equation.

We can construct such a function as the limit of a sequence of functions (ϕ

deﬁned by ϕ

[0,1)

and for n ≥ 0,

n+1

(x) = a

(2x) + a

(2x − 1) + a

(2x − 2) + a

(2x − 3)

From the ﬁrst few ϕ

, graphed in Figure 15.2, it is plausible that the sequence

(ϕ

) converges to a continuous function. However, proving this requires careful

arguments using the Fourier transform, and so is beyond the scope of this book.

We content ourselves with stating the following theorem.

15.5.3. THEOREM. The sequence of functions (ϕ

) converges uniformly to a

continuous function ϕ.

We will prove convergence in L

(R) in the next section. The other properties

of the Daubechies wavelet can now be deduced. Note that except for the continuity

of ϕ and ψ, all of the other properties follow from convergence in L

(R).

15.5.4. COROLLARY. The Daubechies wavelet ϕ satisﬁes the properties:

(1) ϕ(x) = a

ϕ(2x) + a

ϕ(2x − 1) + a

ϕ(2x − 2) + a

ϕ(2x − 3).

(2) ϕ is supported on [0, 3].

(3) kϕk

= 1 and

ϕ(x) dx = 1.

(4) ψ(x) = −a

ϕ(2x − 1) + a

ϕ(2x) − a

ϕ(2x + 1) + a

ϕ(2x + 2)

is continuous with support in [−1, 2].

(5)

ψ(x) dx =

xψ(x) dx = 0.

(6) {ϕ(x − j), ψ(x − j) : j ∈ Z} is orthonormal.

15.5 Daubechies Wavelets 531

FIGURE 15.2. The graphs of ϕ

through ϕ

PROOF. The proof will be left as an exercise using the following outline.

From the deﬁnition of ϕ

n+1

in terms of ϕ

and the convergence to ϕ, it follows

immediately that ϕ satisﬁes the scaling relation. The Haar function ϕ

[0,1)

satisﬁes (2) and (3) and (6a): {ϕ

(x − j) : j ∈ Z} is orthonormal. We also

introduce the functions

n+1

(x) = −a

(2x − 1) + a

(2x) − a

(2x + 1) + a

(2x + 2)

for n ≥ 0. We show by induction that ϕ

and ψ

satisfy (2)–(6) for all n ≥ 1 with

the exception of continuity for ψ

, and thus they hold in the limit. The continuity

of ψ follows from the continuity of ϕ. ¥

At this point, a reasonable objection is that we do not have anything resembling

a formula for the scaling function ϕ, much less the wavelet ψ that goes along with

532 Wavelets

it. The remedy is to observe that the scaling relation provides a way to evaluate ϕ

at points k/2

for k, n ∈ Z, n ≥ 0.

Since ϕ is continuous and has support contained in [0, 3], ϕ(i) = 0 for all

integers i other than 1 and 2. Thus,

ϕ(2) = a

ϕ(4) + a

ϕ(3) + a

ϕ(2) + a

ϕ(1)

= a

ϕ(2) + a

ϕ(1).

Similarly, ϕ(1) = a

ϕ(2) + a

ϕ(1). Solving these equations yields

ϕ(1) = (1 +

√

3)/2 and ϕ(2) = (1 −

√

3)/2.

From the values at the integers, we can now evaluate ϕ at all numbers of the

form k/2 by using the scaling relation. For example,

= a

ϕ(1) + a

ϕ(0) + a

ϕ(−1) + a

ϕ(−2) = (2 +

√

3)/4.

Likewise, as the reader should verify, ϕ(3/2) = 0 and ϕ(5/2) = (2 −

√

3)/4.

Continuing in this way, we can then obtain the values of ϕ at points of the form

k/4 (k odd), then at k/8 (k odd), and so on. As ϕ is continuous, the values at the

points k/2

for some sufﬁciently large n will provide a reasonable graph of ϕ, such

as that given in Figure 15.3.

2 3

FIGURE 15.3. The Daubechies scaling function.

Similarly, using the relation (15.5.2), we can ﬁnd the values of ψ at points k/2

and graph ψ; see Figure 15.4.

Exercises for Section 15.5

A. Prove Corollary 15.5.4 following the outline given there.

B. Evaluate the Daubechies wavelet ψ at the points k/4 for k ∈ Z.

C. WhichDaubechies wavelet coefﬁcientsare nonzero for the function givenby f(x) = x

on [0, 2] and 0 elsewhere?