Wavelets with ompat

support

1. Introdution

In this hapter we study wavelets with ompat supp ort. It is quite easy

toseethatif thefatherwaveletorsaling funtion 'hasompatsupp ort,

then the lter has ompat supp ort as well, i.e., it is a nite sequene.

Atleast in theasewhere 'deayssuÆiently rapidly at1theonverse

also holds.

First we onsider some results that are somewhat more general than

whatwe atuallyneed for theanalysisof wavelets.

2. Dilation equations

InChapter 4we found thataruial prop ertyofthefatherwaveletorsal-

ingfuntion 'determining a multiresolution is thatit satisesthe dilation

equation

'=2 X

k 2Z

(k )'(2 k ):

(5.1)

Inthissetionwelo okatsomeprop ertiesofageneralizationofthisequation.

First we observe that every sequene ((k ))

k 2Z

an b e identied with

a Radon measure, i.e. alo al measure, bydening

(E) =

P

k 2E

(k ) for

every b ounded set E 2R. If we assume that 2l 1

(Z), then

is a nite

measure. Now (5.1)an b erewrittenas

'=2(

')(2)

41

wheredenotesonvolution. Thus thegeneralized equationthatwewillb e

lo oking athere is

f =(f)();

(5.2)

where is some real numb er > 1 and 2 M(R;C), i.e., is a omplex

measure onR.

Firstwe prove an auxiliary result on the onvergeneof pro duts. We

usethe notationjj

+

=maxf0;g.

Lemma 5.1. Let 2 M(R;C) be suh that (R) = 1 and R

R

(jlogjxjj

+ +

1)jj(dx) < 1. Then the produt Q

1

k =1

^ (

k

!) onverges uniformly on

ompat subsets of Rtowards a ontinuousfuntion.

Pro of. Sine (R)=1wehave ()^ 1= R

R (e

i2 x

1)(dx), andhene

j^() 1j Z

R

2jsin(x)jjj(dx); 2R:

Letmb eap ositiveintegerandlet!2R. Nowitislearfromthepreeding

inequality, Fubini's theorem, andthefat thatjsin (t)jmin f1;jtjgthat

1

X

k =m

^ (

k

!) 1

2 1

X

k =m Z

R jsin(

k

x!)jjj(dx)

2 Z

R dlog

( jx! j)e

X

k =m

1+

1

X

k =maxfdlog

( jx! j)e+1;mg

k

jx!j

jj(dx)

2 Z

R

dlog

(jx!j)e+1 m

+ +

1

1

jm dlog

( jx! j)e 1j

+

jj(dx):

From this inequality we get the uniform onvergene on ompat in-

tervals of the series and this implies the laim of the lemma by [1, Th.

15.4℄.

Wepro eed withan easyresult.

Prop osition 5.2. Assume >1andthat 2M(R;C) satisesj(R)j1

and R

R

jlog(jxjj

+ +1

jj(dx) < 1 if j(R)j = 1. If equation (5.2) has a

nontrivial solution f 2L 1

(R;C), then(R) =1 and this solutionis unique

in L 1

(R;C) up to a multipliative onstant.

Pro of. TakingFourier transformsof b oth sides of (5.2)we get

^

f(! )= (! )^

^

f(!):

(5.3)

If j(R)j < 1, then it is lear that lim

m!1 Q

m

j=1 j^(2

j

!)j = 0 for every

! 2R. Thus we seefrom (5.3)that

^

f(!)=0forall ! 2R,so we an have

no nontrivialsolution f.

Supp ose next that j(R)j=1. If

^

f(0)6=0,thenweonlude from(5.3)

that(R)= (0)^ =

^

f(0)=

^

f(0)=1. If

^

f(0)=0then we have

j

^

f(!)j= lim

m!1 m

Y

k =1 j(^

k

!)jj

^

f(

m

!)j=0; !2R:

b eause thepro dut Q

1

k =1 j^(

k

!)j onvergesbyLemma5.1. Thus we see

thatf isidentially 0.

Ifnow(R)=1,thenwehave bylemma 5.1and (5.3)that

^

f(!)=

^

f(0) 1

Y

k =1

^ (

k

!); !2R;

and we see thatf isunique uptothemultipliative onstant

^

f(0).

Nextwe onsider thease where in (5.2) hasompat supp ort. First

weprovean auxiliary resulton howthesupp ort of(f)()is related to

thesupp ortsof and f.

Lemma 5.3. Assume that >1, 2M(R;C) with supp() [M ;M

+

℄

and that f 2L 1

(R;C) with supp(f)[F ;F

+

℄. Then

supp

(f)()

h

F +M

; F

+ +M

+

i

: (5.4)

Pro of. Letx<(M +F )=. Thenx t<M +F tF iftM .

Similarly when x >(M

+ +F

+

)= we have x t>M

+ +F

+

t F

+ if

tM

+

. Thisgivesthe desiredonlusion.

Sine the previous result says that theop erator f ! (f)()fores

thesupp ortloser tothatof itisnaturaltoexp et thatif hasompat

supp ort and there is a solution of (5.2), then this solution has ompat

supp ort aswell. This turns outto b ethease,atleast if f isintegrable.

Prop osition 5.4. Assume that > 1, 2 M(R;C) has ompat support

ontained in the interval [M ;M

+

℄andthat (R)=1. Iff 2L 1

(R;C) sat-

sies (5.2), thenf has ompatsupportontainedin theinterval [ M

1

; M+

1

℄.

Pro of. Let f 2 L 1

(R;C) b e some nontrivial funtion that satises (5.2).

If we an show that f has ompat supp ort, then it follows from rep eated

appliations of Lemma 5.3 that thesupp ort is ontained in the desired in-

terval.

Let usfor simpliity assumethat M <0 and that M

+

>0Let m0

b e an integer and let f

m

= f f

[ m

M ; m

M+℄

. Moreover, we dene the

linearop eratorT :L 1

(R;C)!L 1

(R;C)byT(g)=(g)().Ifweapply

Lemma 5.3 m times we see that T m

(f f

m

) hassupp ort ontained in the

interval[ M

1

; M+

1

℄. OntheotherhandwehaveT m

(f

m

)=f T m

(f f

m ),

and this meansthat

f(x)=T m

(f

m

)(x); x62 h

M

1

; M

+

1

i

: (5.5)

Moreover,we easily seethat

\

T m

(f

m )(!)=

m

Y

k =1

^ (

k

!)

f

m (

m

! ):

(5.6)

Lethb esomeinnitely manytimesdierentiablefuntionwithsupp ort

ontained in [ 1;1℄ and let h

= h(), > 0. Now it follows from the

inversiontheorem forFourier transforms(Theorem2.3.(b)),(5.5)and(5.6)

that

Z

R h

(x t)T m

(f

m

)(t)dt= Z

R e

i2 x!

h

(!)

m

Y

k =1

^ (

k

!)

f

m (

m

!)d!:

(5.7)

NowweknowbyLemma5.1thatj Q

1

k =1

^ (

k

!)jisb oundedwhen j!j1.

Then itfollows forall m1and !2Rthat

m

Y

k =1

^ (

k

!)

( sup

! 2R j^(!j)

dlog

2 (j! j)e

sup

j j1 j

1

Y

k =1

^ (

k

)jC(j!j+1) C

whereC issomeonstant. Sine h isinnitely manytimes dierentiable, it

follows that

Z

R j

h

(!)j(j!j+1) C

d! <1;

andthereforeit followsfrom(5.7),thedominatedonvergenetheorem and

from the fat that f

m

! 0 in L 1

(R;C) and hene

f

m

! 0 in L 1

(R;C) as

m!1 that

lim

m!1 Z

R h

(x t)T m

(f

m

)(t)dt=0; x2R; k1:

But when we let ! 1 we see from (5.5) that f must have ompat

supp ort.

3. Constrution of wavelets with ompat

support

Whenp erformingalulationswiththelteronsomerealdataitislearly

advantageous tohave thesequene to b e real. This requirement we will

make throughout this setion where we want to nd suitable sequenes

thatgeneratemultiresolutions. FromTheorems 4.12and4.13we seethat

mustsatisfy (4.11),(4.46), and(4.48).

Weget thefollowing haraterization of theFourier transformof lters

withompat (i.e.,nite) supp ort.

Theorem5.5. Letf(k )g

k 2Z

beasequeneofrealnumberswithonlynitely

many nonzero terms. Then (4.11) and (4.46) hold if and only if

^ (! )=

1

2 1+e

i2 !

N

Q(e i 2 !

)e i2 L!

; (5.8)

whereN 1, L2Z and Q isa polynomial withreal oeÆientssuh that

(5.9)

Q(e i2 !

)

2

= N 1

X

k =0

N +k 1

k

sin(! ) 2k

+sin(!) 2N

R os(2! )

;

whereR isan odd realpolynomial.

Pro of. Supp ose rst that (4.11) and (4.46) hold. Sine we require that

^

(0)= 1, it follows from (4.11) that (^ 1

2

) =0. In order to see that ^ an

b e written in the form (5.8) we argue as follows: For some integer L the

funtion z L

P

k 2Z (k )z

k

is a p olynomial and this p olynomial vanishes in

thep ointz= 1. Thusitanb ewrittenin theform( 1

2

(1+z)) N

Q(z)where

N 1and Q isa realp olynomial. Substitutinge i 2 !

for zweget (5.8).

IfQ(z)= P

M

j=0 q

j z

j

,thenwe have

jQ(e i2 !

)j 2

= M

X

k = M

~ q

k e

i2 k !

=q~

0 +

M

X

k =1

~ q

k (e

i2 k !

+e i2 k !

)

=q~

0 +2

M

X

k =1

~ q

k

os(2k ! );

sine q~

k

= q~

k

for all k b eause q~

k

= P

minfM;M k g

j=maxf0; k g q

j q

j+k

and the o eÆ-

ientsq

j

in Qarereal. Sineeverytermos(2k ! )anb ewrittenasap oly-

nomialinos(2! )(useDeMoivre'sformulaandsin (2!) 2

=1 os(2! ) 2

)

orequivalently asa p olynomial in sin (! ) 2

we seethat there existsa p oly-

nomial P suh that

jQ(e i2 !

)j 2

=P(sin (! ) 2

):

(5.10)

Sinesin ((!+

1

2 ))

2

=os(! ) 2

=1 sin(! ) 2

andj 1

2 (1+e

i2 !

)j=os(! ) 2

itfollows from (4.11)that

(1 z) N

P(z)+z N

P(1 z)=1;

(5.11)

on the interval [0;1℄and therefore also on R. We an write P in the form

P(z) = P

N 1

j=0 p

j z

j

+ N

R

0

(z). Inserting this expression into (5.11) we get

thefollowing system ofequationsfor theo eÆients p

j ,

p

0

=1;

p

k

= k 1

X

j=0 ( 1)

k j 1

N

k j

p

j :

Nexthavetowehekthatthesolutionofthisreursivesystemofequations

is

p

k

=

N+k 1

k

; 0kN 1:

Fork=0thisisertainlytheaseandanindutionargumentworksb eause

wehave

k 1

X

j=0 ( 1)

k j+1

N

k j

N +j 1

j

= N

k ! ( 1)

k +1 k 1

X

j=0

k

j

( 1) j

(N+j 1)!

(N+j k )!

x N+j k

x=1

= N

k ! ( 1)

k +1 k 1

X

j=0

k

j

( 1) j d

k 1

dx k 1

x N+j 1

x=1

= N

k ! ( 1)

k +1

d k 1

dx k 1

x N 1

(1 x) k

( 1) k

x N+k 1

x=1

= N

k ! d

k 1

dx k 1

x N+k 1

x=1

=

N +k 1

k

:

Thuswe dene thep olynomial P

N by

P

N (z)=

N 1

X

k =0

N+k 1

k

x k

: (5.12)

Next we observe that this p olynomial is in fat a solution of (5.11),

b eause theonstrution oftheo eÆeientsp

k

guaranteesthat

(1 z) N

P

N

(z)+z N

P

N

(1 z) 1=z N

V(1 z);

(5.13)

whereV is p olynomial ofat mostdegree N 1. But thenit followsthat

z N

V(1 z)=(1 z) N

V(z):

(5.14)

Itfollowsfromaalulationsimilartotheoneusedforndingtheo eÆients

p

k

,thatV is identiallyzero sine itis of amostdegree N 1.

Theoriginalp olynomialP waswrittenintheformP =P

N (z)+z

N

R

0 (z).

Ifweinsert this expression in (5.11)weonlude that

(1 z) N

z N

R

0

(z)+(1 z) N

z N

R

0

(1 z)=0;

(5.15)

that isR

0

(z) = R

0

(1 z) and this implies that R

0

(z)=R(1 2z) where

Ris ano ddp olynomial. But this isexatly whatwe wantedtoprove.

The onverse go esin exatlythesameway.

If we want to onstrut a lter sequene , one p ossibility is to use

Theorem5.5. Butthenwemustb eabletondthetrigonometrip olynomial

Q(e i2 !

) if jQ(e i 2 !

)j 2

isknown. Thislassial result isgivenin thenext

lemma.

Lemma 5.6. Assume that A(!)= P

M

k = M a

k e

i2 k !

,wherea

k

=a

k 2R

for k=0;1;:::;M,isnonnegativeand A

M

6=0. Thenthe 2M zeros of the

polynomial P

M

k = M a

k

! k +M

areof the form w

j ,w

j ,w

1

j , w

j 1

2C nR, for

j=1;:::;J,and r

k , r

1

k

2R, for k=1;:::;K,and

B(!)= v

u

u

t

ja

M j

K

Y

k =1 jr

k j

1 J

Y

j=1 jw

j j

2

K

Y

k =1 e

i2 !

r

k

J

Y

j=1 e

i 4 !

2e i 2 !

Re(w

j )+jw

j j

2

;

isatrigonometripolynomialwithrealoeÆientssuhthatjB(!)j 2

=A(!).

Pro of. LetP

A (z)=

P

M

k = M a

k z

k +M

. Thisp olynomialhas2M zeros(ount-

ingmultipliities) andsine theo eÆients arerealwehaveP

A

(z)=P

A (z)

for all z, so that if z is a zero, then z is a zero as well. Moreover, sine

a

k

= a

k

for k = 1;:::;M, it follows that P

A

(z) = z 2M

P

A (

1

z

) and this

implies that if z is a zero of P

A

, then so is z 1

. (The assumption a

M 6= 0

guarantees that P

A

(0) 6= 0.) Moreover, every zero on the unit irle has

even multipliity b eause z M

P

A

(z) is by assumption nonnegative on the

unitirle. 1isazero,thenweseefromtherelationP

A

(z)=z 2M

P

A (

1

z )that

itisatuallyazeroofevenmultipliity. Thisgivestheonlusionab outthe

zerosof P

A .

Thuswe anwrite P

A

in theform

P

A

(z)=a

M

K

Y

k =1 (z r

k

)(z r 1

k )

J

Y

j=1 (z w

j

)(z w

j

)(z w 1

j

)(z w

j 1

)

:

Sine we forevery z2C n0 have

j(e i2 !

z)(e i2 !

z 1

)j=jzj 1

j(e i2 !

z)(z e i2 !

)j

=jzj 1

je i2 !

zj 2

;

itfollowsfromthenonnegativityofAandthefatthatjA(! )j=jP

A (e

i 2 !

)j

that

A(!)=jA(!)j=jP

A (e

i2 !

)j=ja

M j

K

Y

k =1 jr

k j

1 J

Y

j=1 jw

j j

2

K

Y

k =1 e

i2 !

r

k

J

Y

j=1 (e

i2 !

w

j )(e

i2 !

w

j )

2

=jB(!)j 2

:

This ompletesthepro of.

If we want to onstrut a wavelet with ompat supp ort, the simplest

approah aording to Theorem 5.5 isto ho ose a p ositive integerN,take

L = 0 for simpliity, sine another hoie only amounts to a translation,

ho osethep olynomial in (5.9)tob eidentially zero,and soon.

Weleaveitasan exerisetoshowthatinthiswaywe getalter thatin

addition to (4.11) and (4.46) also satises (4.48) and therefore generates a

father wavelet orsaling funtion thatturns outtob eontinuous if N >1.

Infatonean saymuhmoreab outthesmo othnessof thesefuntionsbut

this question will notb estudied here.

4. Propertiesof ompatly supported wavelets

FirstweonsiderbrieythequestionofhowoneaneÆiently alulatethe

values ofthefuntion '.

Prop osition 5.7. Assumethat ((k ))

k 2Z

issuh that(k )=0whenk<

a or k>a

+ ,

P

k =a a

+

(k )=1 and '2C

(R), with'60, is a solution

to the equation

'(x)=2 X

k 2Z

(k )'(2x k ):

Then the matrix A dened by A(i;j) =2(2i j), i;j =a =1;:::;a

+ 1

has the eigenvalue 1, ('(a +1);:::;'(a

+ 1))

T

is an eigenvetor for this

eigenvalue and the values of ' at the points 2 j

n, j 1 an be reursively

alulated fromthe equation

'(2 j

n)=2 a+

X

k =a

(k )'(2 j+1

n k ); n2Z; j1:

Observethatwedonotlaim thattheeigenvalue1frothematrixAhas

geometrimultipliity1soitismaynotb elearwhiheigenvtortoho ose,

but in mostasesthis turns outnottob ethe ase.

Our next result restrits the smo othness of the saling funtion ' in

termsof thesupp ort of thelter .

Theorem5.8. If m 0 and f 2 C m

(R;C), f 6 0, has ompat support

and satises

f =2 a+

X

k =a

(k )f(2 k );

(5.16)

for some numbers f(k )g, thenm<a

+

a 1.

Pro of. If we apply Lemma 5.3,we see thatthe supp ortof f mustb e on-

tained in the losed interval [a ;a

+

℄. Thus the supp ort of f (j)

must also

b e ontained in this interval for0 j m. Moreover,dierentiating b oth

sides of (5.16) weget

f (j)

=2 j+1

a

+

X

k =a

(k )f (j)

(2 k ):

(5.17)

Let A b e a matrix with elements A(i;j) = 2

2i j

for i, j = a +

1;:::;a

+

1 (the indexing is nonstandard but this is of no onsequene).

Nowweseefrom(5.17)thatifthevetor(f (j)

(a +1);f (j)

(a +2);:::;f (j)

(a

+

1)) T

is not the zero vetor, then it is an eigenvetor of the matrix A or-

resp onding to the eigenvalue 2 j

. We leave it as an exerise to show that

this vetor annot b e thezero vetor. Thus A has at least m+1 distint

eigenvalues so thatA mustb e atleast an m+1m+1 matrix. Thus we

seethat m+1a

+

a 1 andthis givesthedesired onlusion.

Next we show that exept for the Haar funtion, no father wavelet or

saling funtion foramultiresolutionan notb e symmetriwithresp et to

anyp oint.

Prop osition 5.9. Let (fV

m g

m2Z

;') be a multiresolution of L 2

(R;C) suh

that ' is real-valued and has ompat support. Then ' is not symmetri

(norantisymmetri) withrespetto anypoint unless'is theHaar funtion

[0;1℄

.

Pro of. Itislear thatweannothave'(+)= '( )forsome2R,

b eausethenwewouldhave R

R

'(x)dx=0whihisimp ossible byTheorem

4.9.

Supp ose onthe otherhand that'(+)='( ). Ifisan integer,

thenantakeanintegertranslationof',sowemaywithoutlossofgenerality

asumethat'isan evenfuntion. Itfollows thatthelter isevenaswell

andhas ompatsupp ort. Weshall showthatthisleads toaontradition.

Let us intro due the notation that if p is a trigonometri p olynomial

withp erio d 1,i.e.,p= P

k

^ p(k )e

i2 k

,then

N

+

(p)=maxfkjp(k )^ 6=0g;

N (p)=minfkjp(k )^ 6=0g:

It iseasytohekthat

N

+ (jpj

2

)= N (jpj 2

)=N

+

(p) N (p):

(5.18)

Let e

b e the sequene e

k

= 1

2

(1+( 1) k

)(k ) with nonzero even indies

and o

thesequene o

k

= 1

2

(1 ( 1) k

)(k )withnonzeroo ddindies. Sine

e

= 1

2

(()+^ (^ + 1

2 ))and

o

= 1

2

(()^ (^ + 1

2

)),itfollowsfrom(4.11)

that

j

e

j 2

+j

o

j 2

= 1

2 : (5.19)

Sineneither e

nor o

annot b eidentiallyzero(b eause

e

(0)=

o

(0)=

1

2

) itfollows from(5.18) that

N

+ (

e

N

+ (

e

=N

+ (

o

N

+ (

e

: (5.20)

From thedenition of e

and o

we get

N

+

()^ =maxfN

+ (

e

);N

+ (

o

)g;

N ()^ =min fN (

e

);N (

o

)g;

Ifweombinethis resultwith(5.20)we onlude that

N

+

()^ N ()^ =maxfN

+ (

e

) N (

o

);N

+ (

o

) N (

e

)g:

(5.21)

SineN

(

e

)areevennumb ersandN

(

o

)areo ddnumb ers,itfollowsthat

N

+

()^ N ()^ isano ddnumb er. But then annotb ean even sequene

and we have aontradition.

Assume next that '(+)= '( ) where is not an integer. We

mayagainshiftthefuntion'sothat2(0;1). TakingFouriertransforms

weget

^ '()=e

4 i

^ '( ):

(5.22)

Butthen itfollows from (4.10)thatwealso have

^

()=e 4 i

^ ( ):

(5.23)

Now ^ and (^ ) are b oth trigonometri p olynomials with p erio d 1 and

therefore wemusthave= 1

2

. Thus wehave '(+1)='( ). It follows

from (4.8)after somehanges of variables that

2k +1

=

2k

forall k2Z.

Sine 'isreal-valued, is real-valued aswell, andhene we have

e

=

o

; (5.24)

and ombining thisresult with(5.19) we get

j

e

j 2

= 1

4 : (5.25)

It followsthat thereexistsan index ksuhthat

j

= 1

2

when j=2k+1 or

j= 2k . If k=0,thenwe getthe Haarfuntion and otherwise we get

^ =e

i

os((4k+1)):

(5.26)

Butthen itfollowsfrom Prop osition 4.15that (4.48)annothold true,and

this ontraditsTheorem4.13.