Wavelets, spring 2002

Wavelets, spring 2002

8 Signal analysis and reconstruction

8.1 Notation

Recall the projections

P_j : L²(R)→V_j P_jf =

∞

X

k=−∞

hf, ϕ_j,kiϕ_j,k =

∞

X

k=−∞

c_j,kϕ_j,k

Q_j : L²(R)→W_j Q_jf =

∞

X

k=−∞

hf, ψ_j,kiψ_j,k =

∞

X

k=−∞

d_j,kψ_j,k

(8.1)

Let us also define sequences

c^j = . . . , c_j,−1, c_j,0, c_j,1, c_j,2, . . . d^j = . . . , d_j,−1, d_j,0, d_j,1, d_j,2, . . . Also for any sequencex we define ˜x by ˜x_n=x_−n.

Definition 8.1. If x is a sequence, the operators ↓2, downsampling, and ↑2, upsam- pling, are defined by

y =(↓2)x ⇔ y_n=x_2n y =(↑2)x ⇔ y_n=

(x_k , n= 2k 0 , n= 2k+ 1

Note that (↓2)(↑2)x = x for all x, but in general (↑2)(↓2)x 6= x. They are also adjoints (or transposes) of each other.

Definition 8.2. Let H be a Hilbert space and A : H →H a linear operator. Operator B is said to be adjoint of A if for all x, y ∈H

hAx, yi=hx, Byi The adjoint is of A is usually denoted by A^∗.

Now upsampling and downsampling can be taken to be operators inl²(Z) and one can easily check that

h(↑2)x, yi=hx,(↓2)yi

8.2 Fast wavelet transform

Let us consider the decompositions

V_p =V_p−1⊕W_p−1 =· · ·=V_m⊕W_m⊕W_m+1⊕ · · · ⊕W_p−1 (8.2) Theorem 8.1. Let h and g be the lowpass and highpass filters associated to MRA and let cj,k and dj,k be the coefficients of some signal f defined by the projections in (8.1).

Then

c_j,k =√ 2

∞

X

n=−∞

h_n−2kc_j+1,n

d_j,k =√ 2

∞

X

n=−∞

g_n−2kc_j+1,n

In vector notation we have

c^j =√

2 (↓2) ˜h∗c^j+1 d^j =√

2 (↓2) ˜g∗c^j+1 Proof. Sinceϕj,k ∈Vj ⊂Vj+1 we can write

ϕ_j,k(t) =

∞

X

n=−∞

hϕ_j,k, ϕ_j+1,niϕ_j+1,n(t) But

hϕj,k, ϕj+1,ni= Z ∞

−∞

ϕj,k(t)ϕj+1,n(t)dt =√ 22^j

Z ∞

−∞

ϕ(2^jt−k)ϕ(2^j+1t−n)dt

By the change of variables= 2^j+1t−2k, ds = 2^j+1dt we get hϕ_j,k, ϕ_j+1,ni= ¹₂

Z ∞

−∞

ϕ(s/2)ϕ(s+ 2k−n)ds=√ 2h_n−2k So we obtain

ϕ_j,k(t) = √ 2

∞

X

n=−∞

h_n−2k ϕ_j+1,n(t) Then taking the inner products on both sides gives

c_j,k =hf, ϕ_j,ki=√ 2

∞

X

n=−∞

h_n−2k hf, ϕ_j+1,ni=√ 2

∞

X

n=−∞

h_n−2kc_j+1,n

The proof of the formula for d_j,k is entirely analogous. To get the vector formula we note that

c^j_k=c_j,k =

∞

X

n=−∞

h_n−2kc_j+1,n =

∞

X

n=−∞

˜h_2k−nc_j+1,n = ˜h∗c^j+1)_2k

2

With this Theorem we can compute recursively the wavelet coefficients, or in other words we can go from left to right in the equation (8.2). This yields the following diagram, which is sometimes called the wavelet tree.

V_p

!!D

DD DD DD

D //V_p−1

@

@@

@@

@@

@@ // · · ·

""

EE EE EE EE

EE //V_m+1

##G

GG GG GG

GG //V_m

W_p−1 · · · W_m+1 W_m

This process is called the analysis of the signal because we hope that the computed coefficients give the desired information about the signal.

Theorem 8.2. Let h and g be the lowpass and highpass filters associated to MRA and let c_j,k and d_j,k be the coefficients of some signal f defined by the projections in (8.1).

Then

cj+1,k =√ 2

∞

X

n=−∞

hk−2ncj,k+√ 2

∞

X

n=−∞

gk−2ndj,k

In vector notation we have c^j+1 =√

2 h∗ (↑2)c^j +√

2 g∗ (↑2)d^j Proof. Now ϕ_j+1,k ∈V_j+1 =V_j ⊕W_j so we can write

ϕ_j+1,k(t) =

∞

X

n=−∞

hϕ_j+1,k, ϕ_j,niϕ_j,n(t) +

∞

X

n=−∞

hϕ_j+1,k, ψ_j,niψ_j,n(t) But in the previous proof we saw that hϕ_j+1,k, ϕ_j,ni = √

2h_k−2n and hϕ_j+1,k, ψ_j,ni =

√2gk−2n. Hence

c_j+1,k =hf, ϕ_j+1,ki=√ 2

∞

X

n=−∞

h_k−2n hf, ϕ_j,ni+√ 2

∞

X

n=−∞

g_k−2n hf, ψ_j,ni

=√ 2

∞

X

n=−∞

h_k−2nc_j,n+√ 2

∞

X

n=−∞

g_k−2nd_j,n To get the vector formula we use

∞

X

n=−∞

h_k−2nc_j,n =

∞

X

n=−∞

h_k−2n (↑2)c^j

2n =

∞

X

n=−∞

h_k−n (↑2)c^j

n=

h∗ (↑2)c^j

k

This Theorem allows us to reverse the arrows in the wavelet tree, i.e. we can go also from right to left in the equation (8.2).

V_m ^//V_m+1 ^// · · · ^//V_p−1 ^//V_p

W

;;w

ww ww ww ww

W

>>

}} }} }} }} }}

· · ·

<<

yy yy yy yy

yy W

==z

zz zz zz z

This process is calledsynthesis orreconstruction of the signal.

It remains to see how to start the process, i.e. when we have chosenm and p, how do we get c^p in the first place? It turns out that this is really relatively easy if we have sufficiently samples of the signal.

Let us start with simple

Lemma 8.1. Let α_j(t) = 2^jϕ(2^jt) and suppose that supp(ϕ)⊂[−r, r]. Then (i) R∞

−∞αj(t)dt= 1 for all j (ii) ||α_j||1 =||ϕ||1 for all j (iii) supp(α_j)⊂[−2^−jr,2^−jr]

Proof. This is easy to verify.

Now the sequence of functionsαj can be interpreted as Dirac’sδin the following sense.

Lemma 8.2. Let f be continuous. Then

j→∞lim Z _∞

−∞

f(t)α_j(t)dt=f(0) Proof.

Z _∞

−∞

f(t)α_j(t)dt−f(0) =

Z _∞

−∞

f(t)−f(0)

α_j(t)dt ≤ Z ∞

−∞

f(t)−f(0)

|α_j(t)|dt = Z 2^−jr

−2^−jr

f(t)−f(0)

|α_j(t)|dt≤ max

|t|≤2^−jr

f(t)−f(0)

Z 2^−jr

−2^−jr

|α_j(t)|dt= max

|t|≤2^−jr

f(t)−f(0) ||ϕ||1

Because f is continuous, the final expression tends to zero as j tends to infinity.

This leads immediately to

Corollary 8.1. Let f be continuous. Then

jlim→∞

Z ∞

−∞

f(t±s)α_j(s)ds =f(t)

So let us be given a signal f ∈ L²(R). In practice we only have samplesf_k = f(k∆t) where ∆t is the sampling period. So the problem is:

given samples f_k, how to compute or estimate c^p ?

4

So let us try to computec^p. c^p_k=hf, ϕ_p,ki=

Z ∞

−∞

f(t)ϕ_p,k(t)dt = 2^p/2 Z ∞

−∞

f(t)ϕ(2^pt−k)dt

=2^p/2 Z _∞

−∞

f(s+ 2^−pk)ϕ(2^ps)ds= 2^−p/2 Z _∞

−∞

f(s+ 2^−pk)α_p(s)ds So puttinga = 2^−pk and using Corollary 8.1 we get

2^p/2c^p₂pa = Z _∞

−∞

f(s+a)α_p(s)ds →f(a) whenp→ ∞. In other words

f(2^−pk)≈2^−p/2c^p_k

when p is sufficiently “big”. So in practice one scales the time appropriately and one chooses ∆t= 2^−p for some p. Then given the samples f_k one simply puts c^p_k:= 2^p/2f_k.