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 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 \phi} 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 \psi} produces

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 \begin{align} \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{align}}

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 \begin{align} 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{align}}

If we use superscript indexing to represent the space to which the coefficients 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 a} belong, we arrive at the theorem.

quod erat demonstrandum

Discrete Signals

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 \left\{ x_k \right\}_{k=\infty}^\infty}

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 \left( \ldots, x_{-3}, x_{-2}, x_{-1}, x_0, x_1, x_2, x_3, \ldots \right)}

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 \sum_{k=-\infty}^\infty x_k^2 < \infty} . This implies 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 \in \ell^2} (finite energy)

Convolution

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 \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 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 : \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}}