MATH 414 Lecture 29

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

Chapter 4 Exercise 5

$f(x)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k\varphi (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$,

$⟨f,g⟩=0$ for all $g\in V_0$.

$f\perp a$ any basis for $V_0$, and in particular, for $\varphi (x-k)$

for all $k$, $⟨f,\varphi (x-k)⟩=0$

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

Haar Wavelet Decomposition

Theorem 4.12. Given $f_j=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^j\varphi (2^{j}x-k)$,

$\begin{array}{rl}{f}_{j-1}& =\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^{j-1}\varphi (2^{j-1}x-k)\\ w_{j-1}& =f_j-f_{j-1}=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{b}_k^{j-1}\psi (2^{j-1}x-k)\end{array}$

Where

$\begin{array}{rl}{a}_k^{j-1}& =\frac{1}{2}(a_{2k}^j+a_{2k+1}^j)\\ b_k^{j-1}& =\frac{1}{2}(a_{2k}^j-a_{2k+1}^j)\end{array}$

Proof. $f_j:=\sum _{k\in \mathbb{\mathbb{Z}}}{a}_k\varphi (2^{j}x-k)\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 $\varphi \left(x\right)$ and $\psi \left(x\right)$:

$\begin{array}{rl}\varphi \left(2x\right)& =\frac{1}{2}(\varphi \left(x\right)+\psi \left(x\right))\\ \varphi (2x-1)& =\frac{1}{2}(\varphi \left(x\right)-\psi \left(x\right))\end{array}$

In general,

$\begin{array}{rl}\varphi \left(2^{j}x\right)& =\frac{1}{2}(\varphi \left(2^{j-1}x\right)+\psi \left(2^{j-1}x\right))\\ \varphi (2^{j}x-1)& =\frac{1}{2}(\varphi \left(2^{j-1}x\right)-\psi \left(2^{j-1}x\right))\end{array}$

Hence splitting the even and odd terms of $f_j(x)$ above yields,

$f_j(x)=\sum _{k\in \mathbb{\mathbb{Z}}}{a}_{2k}\varphi (2^{j}x-2k)+\sum _{k\in \mathbb{\mathbb{Z}}}{a}_{2k+1}\varphi (2^{j}x-2k-1)$

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

$\begin{array}{rl}\varphi (2^{j}x-2k)& =\frac{1}{2}(\varphi (2^{j-1}x-k)+\psi (2^{j-1}x-k))\\ \varphi (2^{j}x-2k-1)& =\frac{1}{2}(\varphi (2^{j-1}x-k)-\psi (2^{j-1}x-k))\end{array}$

Hence

$\begin{array}{rl}{f}_j(x)& =\sum _{k\in \mathbb{\mathbb{Z}}}{a}_{2k}\left(\frac{1}{2}(\varphi (2^{j-1}x-k)+\psi (2^{j-1}x-k))\right)+\sum _{k\in \mathbb{\mathbb{Z}}}{a}_{2k+1}\left(\frac{1}{2}(\varphi (2^{j-1}x-k)-\psi (2^{j-1}x-k))\right)\\ & =\sum _{k\in \mathbb{\mathbb{Z}}}\frac{a_{2k}}{2}\varphi (2^{j-1}x-k)+\frac{a_{2k}}{2}\psi (2^{j-1}x-k)+\frac{a_{2k+1}}{2}\varphi (2^{j-1}x-k)-\frac{a_{2k+1}}{2}\psi (2^{j-1}x-k)\\ & =\sum _{k\in \mathbb{\mathbb{Z}}}\left(\frac{a_{2k}+a_{2k+1}}{2}\right)\varphi (2^{j-1}x-k)+\left(\frac{a_{2k}-a_{2k+1}}{2}\right)\psi (2^{j-1}x-k)\end{array}$

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=\mathrm{\infty }}^{\mathrm{\infty }}$

$(\dots ,x_{-3},x_{-2},x_{-1},x_0,x_1,x_2,x_3,\dots )$

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

Convolution

${(x*y)}_k=\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}{x}_{k-m}{y}_m=\sum _{m=-\mathrm{\infty }}^{\mathrm{\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}(x_k+x_{k+1})$

We want to write $F(x{)}_k$ as $F(x{)}_k=f*x_k=\sum _{m=-\mathrm{\infty }}^{\mathrm{\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.

We're left with $f_{-1}{k}_{x+1}+f_0{x}_k=\frac{1}{2}(x_{k+1}+x_k)$. Hence $f_{-1}=f_0=\frac{1}{2}$.

Let $\ell =f$ and $L=F$: this is a low-pass filter.

Downsampling

$D$ is an operator that discards odd $k$

$DL(a^j)=a^{j-1}$