MATH 414 Lecture 29

« previous | Monday, March 31, 2014 | next »

Chapter 4 Exercise 5

$f(x)=\sum _{k=-\infty }^{\infty }a_{k}\,\phi (2x-k)\in V_{1}$

Show that if $f\in W_{0}=V_{0}^{\perp }$ , then $a_{2\ell +1}=-a_{2\ell }$ for all $\ell$ .

$f(x)=\sum _{k}a_{2\ell }\,\psi (x-\ell )$

Given $f\in V_{1}$ and $f\perp V_{0}$ ,

$\left\langle f,g\right\rangle =0$ for all $g\in V_{0}$ .

$f\perp a$ any basis for $V_{0}$ , and in particular, for $\phi (x-k)$

for all $k$ , $\left\langle f,\phi (x-k)\right\rangle =0$

$\phi (x-k)=\phi (2x-2k)+\phi (2x-2k+1)$

Haar Wavelet Decomposition

Theorem 4.12. Given $f_{j}=\sum _{k=-\infty }^{\infty }a_{k}^{j}\,\phi (2^{j}\,x-k)$ ,

{\begin{aligned}f_{j-1}&=\sum _{k=-\infty }^{\infty }a_{k}^{j-1}\,\phi (2^{j-1}\,x-k)\\w_{j-1}&=f_{j}-f_{j-1}=\sum _{k=-\infty }^{\infty }b_{k}^{j-1}\,\psi (2^{j-1}\,x-k)\end{aligned}}

Where

{\begin{aligned}a_{k}^{j-1}&={\frac {1}{2}}\,\left(a_{2k}^{j}+a_{2k+1}^{j}\right)\\b_{k}^{j-1}&={\frac {1}{2}}\,\left(a_{2k}^{j}-a_{2k+1}^{j}\right)\end{aligned}}

Proof. $f_{j}:=\sum _{k\in \mathbb {Z} }a_{k}\,\phi \left(2^{j}\,x-k\right)\in V_{j}$ , $f_{j-1}\in V_{j-1}$ , and $w_{j-1}\in W_{j-1}$ . By definition, we have $f_{j}=f_{j-1}+w_{j-1}$ .

We have the following relations between $\phi \left(x\right)$ and $\psi \left(x\right)$ :

{\begin{aligned}\phi \left(2x\right)&={\frac {1}{2}}\,\left(\phi \left(x\right)+\psi \left(x\right)\right)\\\phi \left(2x-1\right)&={\frac {1}{2}}\,\left(\phi \left(x\right)-\psi \left(x\right)\right)\end{aligned}}

In general,

{\begin{aligned}\phi \left(2^{j}\,x\right)&={\frac {1}{2}}\,\left(\phi \left(2^{j-1}\,x\right)+\psi \left(2^{j-1}\,x\right)\right)\\\phi \left(2^{j}\,x-1\right)&={\frac {1}{2}}\,\left(\phi \left(2^{j-1}\,x\right)-\psi \left(2^{j-1}\,x\right)\right)\end{aligned}}

Hence splitting the even and odd terms of $f_{j}(x)$ above yields,

f_{j}(x)=\sum _{k\in \mathbb {Z} }a_{2k}\,\phi \left(2^{j}\,x-2k\right)+\sum _{k\in \mathbb {Z} }a_{2k+1}\,\phi \left(2^{j}\,x-2k-1\right)

Substituting the prior function evaluations into our relation for $\phi$ and $\psi$ produces

{\begin{aligned}\phi \left(2^{j}\,x-2k\right)&={\frac {1}{2}}\,\left(\phi \left(2^{j-1}\,x-k\right)+\psi \left(2^{j-1}\,x-k\right)\right)\\\phi \left(2^{j}\,x-2k-1\right)&={\frac {1}{2}}\,\left(\phi \left(2^{j-1}\,x-k\right)-\psi \left(2^{j-1}\,x-k\right)\right)\end{aligned}}

Hence

{\begin{aligned}f_{j}(x)&=\sum _{k\in \mathbb {Z} }a_{2k}\,\left({\frac {1}{2}}\,\left(\phi \left(2^{j-1}\,x-k\right)+\psi \left(2^{j-1}\,x-k\right)\right)\right)+\sum _{k\in \mathbb {Z} }a_{2k+1}\,\left({\frac {1}{2}}\,\left(\phi \left(2^{j-1}\,x-k\right)-\psi \left(2^{j-1}\,x-k\right)\right)\right)\\&=\sum _{k\in \mathbb {Z} }{\frac {a_{2k}}{2}}\,\phi \left(2^{j-1}\,x-k\right)+{\frac {a_{2k}}{2}}\,\psi \left(2^{j-1}\,x-k\right)+{\frac {a_{2k+1}}{2}}\,\phi \left(2^{j-1}\,x-k\right)-{\frac {a_{2k+1}}{2}}\,\psi \left(2^{j-1}\,x-k\right)\\&=\sum _{k\in \mathbb {Z} }\left({\frac {a_{2k}+a_{2k+1}}{2}}\right)\,\phi \left(2^{j-1}\,x-k\right)+\left({\frac {a_{2k}-a_{2k+1}}{2}}\right)\,\psi \left(2^{j-1}\,x-k\right)\end{aligned}}

If we use superscript indexing to represent the space to which the coefficients $a$ belong, we arrive at the theorem.

quod erat demonstrandum

Discrete Signals

$\left\{x_{k}\right\}_{k=\infty }^{\infty }$

$\left(\ldots ,x_{-3},x_{-2},x_{-1},x_{0},x_{1},x_{2},x_{3},\ldots \right)$

such that $\sum _{k=-\infty }^{\infty }x_{k}^{2}<\infty$ . This implies $x\in \ell ^{2}$ (finite energy)

Convolution

$\left(x*y\right)_{k}=\sum _{m=-\infty }^{\infty }x_{k-m}\,y_{m}=\sum _{m=-\infty }^{\infty }x_{m}\,y_{k-m}$

Shift-/Time-Invariant Filters

A linear transformation $F:\ell ^{2}\to \ell ^{2}$ is shift-/time-invariant if and only if there is an $f\in \ell ^{2}$ such that $F(x)=f*x$ .

Examples

$F(x)_{k}={\frac {1}{2}}\left(x_{k}+x_{k+1}\right)$

We want to write $F(x)_{k}$ as $F(x)_{k}=f*x_{k}=\sum _{m=-\infty }^{\infty }f_{m}\,x_{k-m}={\frac {1}{2}}\,x_{k}+{\frac {1}{2}}\,x_{k+1}$ with all other $x_{k-m}$ terms equal to zero.