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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \in \ell^2} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x) = f * x} .

Examples

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)_k = \frac{1}{2} \left( x_k + x_{k+1} \right)}

We want to write Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x)_k} as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{k-m}} terms equal to zero.

We're left with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{-1} \, k_{x+1} + f_0 x_k = \frac{1}{2} \, \left( x_{k+1} + x_k \right)} . Hence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{-1} = f_0 = \frac{1}{2}} .

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell = f} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L = F} : this is a low-pass filter.

Downsampling

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} is an operator that discards odd Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D \, L(a^j) = a^{j-1}}