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

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

15.8 The Franklin Wavelet 543

15.8.1. DEFINITION. A subset {x

: n ∈ Z} of a Hilbert space H is a Riesz

basis if span{x

: n ∈ Z} = H and there are constants A > 0 and B < ∞ so that

1/2

≤

≤ B

1/2

for all sequences (a

) with only ﬁnitely many nonzero terms.

15.8.2. THEOREM. The translates {h(x −j) : j ∈ Z} of the hat function form

a Riesz basis for V

PROOF. Consider the inner product of two compactly supported functions in V

say f (x) =

j=−n

h(x − j) and g(x) =

j=−n

h(x − j). For convenience, set

= b

= 0 for |j| > n.

hf, gi =

+∞

−∞

f(x)g(x) dx =

j=−n−1

j+1

f(x)g(x) dx

j=−n−1

+ (a

j+1

− a

¢¡

+ (b

j+1

− b

j=−n−1

j+1

−b

j+1

−a

j+1

−a

)(b

j+1

−b

)

j=−n−1

+ a

j+1

+ a

j+1

+ 2a

j+1

It is convenient to rearrange this sum further by moving the term 2a

j+1

to the

next index to obtain

hf, gi =

j=−n−1

+ a

j+1

+ a

j+1

To make sense of this, we introduce two linear transformations.

Recall that `

(Z) is the Hilbert space of all square summable doubly indexed

sequences a = (a

)

+∞

−∞

, where we have

ha, bi =



), (b

)

+∞

n=−∞

and kak

= ha, ai

1/2

+∞

n=−∞

1/2

Let e

for k ∈ Z denote the standard basis for `

(Z). Deﬁne the bilateral shift

on `

(Z) by Ue

= e

k+1

or (Ua)

= a

n−1

. It is easy to see that kUak

= kak

for all vectors a ∈ `

(Z). Also, it is clear that U maps `

(Z) one-to-one and onto

itself. Thus, U is a unitary map.

We also recall from linear algebra that the adjoint (or transpose since we are

working over the real numbers) of a linear transformation T is the linear map T

∗

544 Wavelets

such that

∗

x, yi = hx, T yi for all vectors x, y ∈ H.

For the unitary operator U, we have that U

∗

= U

−1

is the backward bilateral shift

∗

= e

k−1

or (U

∗

= a

n+1

Second, we deﬁne a linear map H from `

(Z) onto V

Ha =

+∞

n=−∞

h(x − n).

Looking back at our formula for the inner product in V

, we see that

hHa, Hbi =

j=−n−1

j+1



(4I +U +U

∗

)a, b

.(15.8.3)

By the Cauchy–Schwarz inequality (7.3.4), since kUak

= kak

= kU

∗

hUa, ai

∗

a, ai

≤ kak

Hence we obtain

kfk

= hHa, Hai =



(4I + U + U

∗

)a, a

≤

4kak

+ |hUa, ai| + |hU

∗

a, ai|

≤ kak

Similarly, we obtain a lower bound

kfk

= hHa, Hai =



(4I + U + U

∗

)a, a

≥

4kak

− |hUa, ai| − |hU

∗

a, ai|

≥

kak

So while the translates of h are not an orthonormal set, we ﬁnd that they do

form a Riesz basis for V

. ¥

Our problem now is to replace the hat function h by a scaling function ϕ. This

function ϕ must have the property that the translates ϕ(x −j) form an orthonormal

set spanning V

. We make use of another property relating the maps U and H. If

f(x) = Ha =

h(x − n), then

HUa =

n−1

h(x − n) =

h(x − n − 1)

= f (x − 1) = (T f)(x) = T Ha,

where T g(x) = g(x − 1) is the translation operator. So HU = T H, namely H

carries a translation by U in `

(Z) to translation by 1 in V

. This suggests that if

we can ﬁnd a vector c such that the translates U

c form an orthonormal basis with

respect to the inner product

[a, b] =



(4I + U + U

∗

)a, b

then ϕ = Hc will be the desired scaling function. Indeed, (15.8.3) becomes

hHa, Hbi = [a, b].

15.8 The Franklin Wavelet 545

We make use of the correspondence between `

(Z) and L

(−π, π) provided

by complex Fourier series (see Remark 14.1.5). We identify the basis e

with

ikθ

, which is an orthonormal basis for L

(−π, π). This identiﬁes the sequence

a in `

(Z) with the function in L

(−π, π) given by f(θ) =

+∞

n=−∞

inθ

. Now

compute

Uf(θ) = U

inθ

i(n+1)θ

= e

iθ

f(θ).

Thus U is the operator that multiplies f(θ) by e

iθ

. We will write M

to denote the

operator on L

(−π, π) that multiplies by g. Such operators are called multiplica-

tion operators. For example, U = M

iθ

. Hence

(4I + U + U

∗

) =

(4I + M

iθ

+ M

∗

iθ

)

= M

(4+e

iθ

−iθ

)

= M

(2+cosθ)

15.8.4. THEOREM. There is an `

sequence (c

) so that ϕ(x) =

h(x−j)

is a scaling function for V

PROOF. Deﬁne the operator X = M

, where g(θ) =

√

3(2 + cos θ)

−1/2

. Notice

that X = X

∗

, XU = U X and X

= 3M

−1

2+cosθ

= 6(4I + U + U

∗

)

−1

. Now deﬁne

c = Xe

and ϕ = Hc. Compute



ϕ(x − j), ϕ(x − k)

= hT

Hc, T

Hci = hHU

c, HU

= [U

c, U

c] =



(4I + U + U

∗

c, U

= hX

−2

, U

i = hX

−2

, XU

= hXX

−2

, U

i = hU

, U

i = δ

This shows that the translates of ϕ form an orthonormal set in the subspace V

Since e

is identiﬁed with the constant function 1,

ϕ(x) = HX1 = Hg.

To compute Hg, we need to ﬁnd the (complex) Fourier series g ∼

inθ

. Now

g is an even function and thus c

−n

= c

; and so g ∼ c

∞

n=1

cosnθ. Moreover,

= c

−n

√

2π

−π

cosnθ

√

2 + cos θ

dθ for n ≥ 0.

Hence

(15.8.5) ϕ(x) =

+∞

n=−∞

h(x − n).

This is the continuous piecewise linear function with nodes at the integers taking

the values ϕ(n) = c

546 Wavelets

A similar argument shows that the translates of ϕ span all of V

. Indeed, note

that

ijθ

g = HU

g = T

Hg = ϕ(x − j).

Now h = He

= HXg

−1

. Express g

−1

(x) =

(2 + cos θ)/3, which is continu-

ous, as a complex Fourier series g

−1

∼

ijθ

. Then

(15.8.6) h = HXg

−1

= H

ijθ

g =

ϕ(x − j).

This expresses h as an `

combination of the orthonormal basis of translates of ϕ,

and thus h lies in their span. Evidently, this span also contains all translates of h,

and so they span all of V

. Therefore, ϕ is the desired scaling function. ¥

Using two formulas from the previous proof, we can write the scaling relation

for ϕ, in terms of the sequences (b

) and (c

). Verify that the hat function satisﬁes

the simple scaling relation

h(x) =

h(2x − 1) + h(2x) +

h(2x + 1).

Equation (15.8.6) gives

h(2x) =

ϕ(2x − j)

and similar formulas for h(2x − 1) and h(2x + 1). Putting these formulas into the

scaling relations gives h(x) as an inﬁnite series involving ϕ(2x − k) as k ranges

over the integers. Substituting this series for h in Equation (15.8.5), we obtain

ϕ(x) =

l∈Z

j∈Z

2j−l

2j−l+1

2j−l−1

ϕ(2x − l).

This formula does not appear tractable, but the sequences (c

) and (b

) decay quite

rapidly, so it is possible to obtain reasonable numerical results by taking sums over

relatively small ranges of j, say −10 to 10.

We can then apply Theorem 15.4.2 to obtain a formula for the Franklin wavelet

itself. This is plotted in Figure 15.6, along with the scaling relation. Notice that the

wavelet is continuous and piecewise linear with nodes at the half integers, as we

would expect since Theorem 15.4.2 implies that the wavelet is in V

. Incidentally,

the numerical values of the ﬁrst few a

in the scaling relation for ϕ are

= 1.15633, a

= a

−1

= .56186, a

= a

−2

= −.09772,

= a

−3

= −.07346, a

= a

−4

= −.02400.

Exercises for Section 15.8

These exercises are all directed toward the analysis of a different wavelet, known as the

Str

omberg wavelet, that has the same multiresolution subspaces V

as the Franklin

wavelet. See [36] for more details.

Write P L(X) to denote the space of L

(R) functions that are continuous and piece-

wise linear with nodes on a discrete subset X of R. Let h be the hat function.

15.8 The Franklin Wavelet 547

1−1 2−2 3−3 4−4

−1

1−1 2−2 3−3 4−4

−1

FIGURE 15.6. The Franklin scaling function and wavelet.

A. Show that P L(−

∪ N) is spanned by {h(2x + k + 1), h(x − k) : k ≥ 0}.

B. Show that P L(−

∪ {

} ∪ N) is spanned by P L(−

∪ N) and h(2x). Hence

show that there is a norm 1 function ψ in P L(−

∪ {

} ∪ N) that is orthogonal to

P L(−

∪ N).

C. Show that ψ is orthogonal to 2

−k/2

ψ(2

−k

x − j) for all k < 0 and j ∈ Z and to

ψ(x + j) for j > 0. Hence deduce that {ψ

: k, j ∈ Z} is orthonormal.

HINT: Some are in P L(−

∪ N). Do a change of variables for the rest.

D. Let V

= P L(2

−k

Z) and let W

be the orthogonal complement of V

in V

k+1

. Show

that span{ψ

: j ∈ Z} = W

. Hence deduce that ψ is a wavelet.

HINT: Show that the span{ψ

: −n ≤ j ≤ n} is the orthogonal complement of

P L(Z∪{k/2 : k ≤ −2n −1}) in PL(Z ∪{k/2 : k ≤ 2n +1}). Let n tend to inﬁnity.

E. The piecewise linear continuous function ψ is determined by its values at the nodes,

ψ(

) = a

for k ≤ 0, ψ(

) = b and ψ(k) = c

for k ≥ 1. Show that the orthogonality

relations coming from the fact that ψ is orthogonal to the basis of PL(−

∪N) yield

548 Wavelets

the equations

k−1

+ a

k+1

= 0 for k≤ −1

k−1

+ c

k+1

= 0 for k ≥ 2

−2

+ 6a

−1

+ 10a

+ 6b + c

= 0

+ 6b + 13c

+ 4c

= 0.

Verify that the solution is the one-parameter family

= C(2

√

3 − 2)(

√

3 − 2)

|k|

for k ≤ 0

b = −C(

√

3 +

)

= C(

√

3 − 2)

k−1

for k ≥ 1.

F. Show that the Franklin scaling function is even, and deduce that the wavelet is sym-

metric about the line x =

. Show that the Str

omberg wavelet does not have this

symmetry, and thus they are different wavelets with the same resolution.

15.9. Riesz Multiresolution Analysis

In this section, we will formalize the structure used in the previous section.

We then apply this to construct another family of wavelets, called Battle–Lemari

wavelets. Since they will be based on cubic splines, instead of the hat function,

they will be smoother than the Franklin wavelet. The following important charac-

terization of Riesz bases is our starting point.

15.9.1. THEOREM. A set of vectors {x

: n ∈ Z} in a Hilbert space H is a

Riesz basis if and only if there is a continuous linear map T from `

(Z) onto H

such that Te

= x

for n ∈ Z and there are constants 0 < A < B < ∞ such that

Akak

≤ kT ak ≤ Bkak

for all a ∈ `

(Z).

PROOF. Let `

denote the vector space of all sequences (a

) with only ﬁnitely

many nonzero terms. For any set {x

: n ∈ Z}, we may deﬁne a linear map from

into H by T a =

, which makes sense because the sum is ﬁnite.

Suppose that {x

: n ∈ Z} is a Riesz basis. The Riesz condition is readily

restated as

Akak

≤ kT ak ≤ Bkak

for all a ∈ `

In particular, the map T satisﬁes the Lipschitz condition

kT a − T bk = kT (a − b)k ≤ Bka − bk

and thus T is uniformly continuous.

Suppose that a ∈ `

(Z). Then we may choose a sequence a

in `

that con-

verges to a in the `

norm. Consequently, (a

) is a Cauchy sequence in `

(Z).

Therefore, since kT a

−T a

k ≤ Bka

−a

, it follows that (T a

) is a Cauchy

sequence in H. Since H is complete, we may deﬁne T a = lim

T a

. See the

Exercises for the argument explaining why this deﬁnition does not depend on the

15.9 Riesz Multiresolution Analysis 549

choice of the sequence. So the deﬁnition of T has been extended to all of `

(Z).

Moreover, we obtain that

kT ak = lim

n→∞

kT a

k ≤ B lim

n→∞

= Bkak

So T is (uniformly) continuous on all of `

(Z).

We similarly obtain

kT ak = lim

n→∞

kT a

k ≥ A lim

n→∞

= Akak

Clearly T maps `

onto the set of all ﬁnite linear combinations of {x

: n ∈ Z}.

So the range of T is dense in H by hypothesis.

Let y ∈ H. Choose vectors y

∈ span{x

: n ∈ Z} that converge to y. Then

) is a Cauchy sequence. Since y

belongs to the range of T , there are vectors

∈ `

with T a

= y

. Therefore,

− a

≤ A

−1

kT (a

− a

)k = A

−1

− y

Consequently, (a

) is Cauchy. Since `

(Z) is complete by Theorem 7.5.8, we

obtain a vector a = lim

. The continuity of T now ensures that

T a = lim

n→∞

T a

= lim

n→∞

= y.

So T maps `

(Z) onto H.

Conversely, if the operator T exists, then the Riesz norm condition holds (by

restricting T to `

). Now because T is continuous and `

is dense in `

(Z), it

follows that span{x

: n ∈ Z} = T `

is dense in T `

(Z) = H. That is,

span{x

: n ∈ Z} = H. ¥

15.9.2. COROLLARY. If {x

: n ∈ Z} is a Riesz basis for a Hilbert space H,

then every vector y ∈ H may be expressed in a unique way as y =

for

some a = (a

) in `

(Z).

PROOF. The existence of a vector a ∈ `

(Z) such that T a = y follows from

Theorem 15.9.1. Suppose that T b = y as well. Then T (a − b) = 0. However,

0 = kT (a −b)k ≥ Aka−bk

. Hence b = a. So T is one-to-one and a is uniquely

determined. ¥

15.9.3. REMARK. Note that the norm estimates show that the linear map T

has a continuous inverse. Indeed, Corollary 15.9.2 shows that T

−1

y = a is

well deﬁned. It is easy to show that the inverse of a linear map is linear. Now

Theorem 15.9.1 shows that Akak

≤ kT ak. Substituting y = T a, we obtain

−1

≤

kyk for all y ∈ H. This shows that T

−1

is Lipschitz and hence

uniformly continuous.

In fact, a linear map is continuous if and only if it is bounded, meaning that

kT k = sup{kT xk : kxk = 1} is ﬁnite. (See Exercise 15.9.D.) A basic theorem

of functional analysis known as Banach’s Isomorphism Theorem states that a

550 Wavelets

continuous linear map between complete normed spaces that is one-to-one and onto

is invertible. Consequently, the existence of the constants A and B required in

Theorem 15.9.1 are automatic if we can verify that T is a bijection.

Now we specialize these ideas to a subspace V

of L

(R) spanned by the trans-

lates of a single function h. To obtain a nice condition, we need to know some easy

facts about multiplication operators. Let g ∈ C[−π, π]. Recall that the linear map

on L

(−π, π) is given by M

f(θ) = g(θ)f(θ).

15.9.4. PROPOSITION. Suppose that the complex Fourier series of g is given

by g ∼

ikθ

. Then the matrix

of M

with respect to the orthonormal

basis {e

ikθ

: k ∈ Z} for L

(−π, π) is given by a

= t

j−k

PROOF. This is an easy computation. Indeed,

= hM

ikθ

, e

ijθ

i =

2π

−π

g(θ)e

ikθ

ijθ

dθ

2π

−π

g(θ)

i(j−k)θ

dθ = t

j−k

We also need these norm estimates for M

15.9.5. THEOREM. If g ∈ C[−π, π], then M

is a continuous linear map

on L

(−π, π) such that kM

≤ kgk

∞

kfk

. Moreover, kgk

∞

is the smallest

constant B such that kM

≤ Bkf k

for all f.

Similarly, if A = inf{|g(θ)| : θ ∈ [−π, π]}, then A is the largest constant such

that kM

≥ Akfk

for all f ∈ L

(−π, π).

PROOF. A straightforward calculation shows that

2π

−π

|g(θ)|

|f(θ)|

dθ ≤

2π

−π

kgk

∞

|f(θ)|

dθ

= kgk

∞

2π

−π

|f(θ)|

dθ = kgk

∞

kfk

In particular, M

is Lipschitz and hence continuous. Similarly,

2π

−π

|g(θ)|

|f(θ)|

dθ ≥

2π

−π

|f(θ)|

dθ = A

kfk

On the other hand, suppose that B < C < kgk

∞

. Then there is an nonempty

open interval (a, b) on which |g(θ)| > C. Let f be a continuous function on [−π, π]

15.9 Riesz Multiresolution Analysis 551

such that kfk

= 1 and the support of f is contained in [a, b]. Then

2π

−π

|g(θ)|

|f(θ)|

dθ =

2π

|g(θ)|

|f(θ)|

dθ

≥

2π

|f(θ)|

dθ = C

2π

−π

|f(θ)|

dθ > B

kfk

Therefore, Bkf k

is not an upper bound for kM

fk for all f . So kgk

∞

is the

optimal choice.

Likewise, if D > C > A, there is a continuous function f with kfk

= 1

supported on an interval (c, d) on which |g(θ)| < C. The same calculation shows

that kM

fk ≤ Ckfk

< Dkfk

. Therefore, A is the best constant in the lower

bound. ¥

We are now ready to obtain a practical characterization of when the translates

of h form a Riesz basis.

15.9.6. THEOREM. Let h ∈ L

(R) and V

span{h(x − j) : j ∈ Z}. Set

= hh(x), h(x −j)i for j ∈ Z. Assume that there is a continuous function g with

Fourier series t

∞

j=1

cosjθ. Then {h(x − j) : j ∈ Z} is a Riesz basis for

if and only if there are constants 0 < A

≤ B

such that A

≤ g(θ) ≤ B

for

all −π ≤ θ ≤ π.

PROOF. Let T a =

h(x − n) for all a ∈ `

. By Theorem 15.9.1, the set

{h(x − j) : j ∈ Z} is a Riesz basis for V

if and only if there are constants

0 < A

≤ B

< ∞ such that

kak

≤ kT ak

h(x − n)

≤ B

kak

Now

kT ak

= hT a, T ai = hT

∗

T a, ai

The linear map T

∗

T has a matrix

with respect to the orthonormal basis e

given by

= hT

∗

T e

, e

i = hT e

, T e

= hh(x − j), h(x − i)i = hh(x), h(x − i + j)i = t

i−j

So the matrix of T

∗

T is constant on diagonals. Note that by symmetry, t

−k

= t

All orthonormal bases are created equal, so we can identify e

with e

inθ

(−π, π), so that `

corresponds to all ﬁnite complex Fourier series. With this

identiﬁcation, we see from Proposition 15.9.4 that T

∗

T = M

, where

g(θ) =

ikθ

= t

I +

∞

k=1

coskθ.

We used t

−k

= t

to obtain a real function g, which returns us to the real domain

from this brief foray into complex vector spaces.

552 Wavelets

Next we observe that g(θ) ≥ 0. Indeed, we have

2π

−π

g(θ)|f(θ)|

dθ = hT

∗

T f, fi = kT fk

≥ 0.

Suppose that g were not positive. Then by the continuity of g, we may choose an

interval (a, b) on which g(θ) < −ε < 0. Then as in the proof of Theorem 15.9.5,

we deduce that for any continuous function f supported on [a, b] we have

2π

−π

g(θ)|f(θ)|

dθ ≤ −εkfk

< 0

which contradicts the previous inequality. So g is positive.

This allows us to deﬁne the multiplication operator M

√

. Since

√

g ≥ 0, we

ﬁnd that M

∗

√

= M

√

∗

T = M

= M

√

= M

∗

√

(Be warned that this does not show that T is equal to M

√

. They do not even map

into the same Hilbert space.) Consequently,

kT fk

= hT

∗

T f, fi = hM

f, fi = hM

√

f, M

√

fi = kM

√

Finally, an application of Theorem 15.9.5 shows that

kfk

≤ kM

√

≤ k

√

∞

kfk

= kgk

∞

kfk

for all f ∈ L

(−π, π) if and only if

≤ inf

θ∈[−π,π]

√

g(θ)|

= inf

θ∈[−π,π]

|g(θ)|.

Thus A

> 0 is possible only if g is bounded away from 0. ¥

We are now ready to modify a Riesz basis of translations of h to obtain an

orthonormal basis of translates. This is the keyto ﬁnding waveletsby the machinery

we have already developed.

15.9.7. THEOREM. Let h ∈ L

(R) be a function such that the set of translates

{h(x−j) : j ∈ Z}is a Riesz basis for its span V

. Assume that t

∞

j=1

cosjθ

is the Fourier series of a continuous function, where t

= hh(x), h(x − k)i. Then

there is a function ϕ ∈ L

(R) such that {ϕ(x − j) : j ∈ Z} is an orthonormal

basis for V

PROOF. By Theorem 15.9.1, there is a continuous, invertible linear map T from

(Z) ontoV

given by T a =

h(x−n). By Theorem 15.9.6, the (continuous)

function g with Fourier series t

∞

j=1

cosjθ satisﬁes T

∗

T = M

and there

are constants 0 < A

≤ B

< ∞ so that

≤ g(θ) ≤ B

for all − π ≤ θ ≤ π.

In particular, g

−1/2

is bounded above by 1/A.