MATH 414 Lecture 35

« previous | Wednesday, April 16, 2014 | next »

Wavelet Review

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\{ 2^{ \frac{j}{2} } \, \phi(2^j \, x - k) \right\}_{k \in \mathbb{Z}}} is an orthonormal basis 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 V_j} $\left\{2^{\frac {j}{2}}\,\psi (2^{j}\,x-k)\right\}_{k\in \mathbb {Z} }$ is an orthonormal basis for $W_{j}$

$V_{j}=V_{j-1}\oplus W_{j-1}$

Decomposition and Reconstruction

For $f_{j}\in V_{j}$, $f_{j}={\begin{cases}\sum _{k=-\infty }^{\infty }a_{k}^{j}\,\phi (2^{j}\,x-k)\\\underbrace {\sum _{k=-\infty }^{\infty }a_{k}^{j-1}\,\phi (2^{j-1}\,x-k)} _{f_{j-1}}+\underbrace {\sum _{k=-\infty }^{\infty }b_{k}^{j-1}\psi (2^{j-1}\,x-k)} _{w_{j-1}}\end{cases}}$

Projecting an arbitrary function $f$ into function $f_{j}\in V_{j}$ involves sampling.

$f_{j}$ can then be decomposed into $f_{j-1}$ and $w_{j-1}$, and so on down to $f_{0}$, $w_{0}$, $w_{1}$, …

Inversely, $f_{0}$ and $w_{0}$ can be used to reconstruct $f_{1}$, $f_{1}$ and $w_{1}$ reconstruct $f_{2}$, and so on up to $f_{j}$

Questions:

1. How do we get from $a_{k}^{j}$'s to $a_{k}^{j-1}$'s and $b_{k}^{j-1}$'s?
2. How do we get from $a_{k}^{j-1}$'s and $b_{k}^{j-1}$'s back to $a_{k}^{j}$'s

Decomposition

${\begin{aligned}p_{k}&=2\,\int _{-\infty }^{\infty }\phi (2x-k)\,\phi (x)\,\mathrm {d} x\\q_{k}&=2\,\int _{-\infty }^{\infty }\phi (2x-k)\,\psi (x)\,\mathrm {d} x\end{aligned}}$

${\begin{aligned}w_{j-1}=\mathrm {proj} _{W_{j-1}}(f_{j})&=\sum _{k\in \mathbb {Z} }b_{k}^{j-1}\,\psi (2^{j-1}\,x-k)\\&=\sum _{k\in \mathbb {Z} }{\frac {b_{k}^{j-1}}{2^{\frac {j-1}{2}}}}\,\underbrace {2^{\frac {j-1}{2}}\,\psi (2^{j-1}\,x-k)} _{\mbox{orthonormal}}\\{\frac {b_{k}^{j-1}}{2^{\frac {j-1}{2}}}}&=\left(\int _{-\infty }^{\infty }f_{j}(x)\,\psi (2^{j-1}\,x-k)\,\mathrm {d} x\right)\,2^{\frac {j-1}{2}}\\&=\left\langle f_{j},\psi _{j-1,k}\right\rangle \\b_{k}^{j-1}=2^{j-1}\,\int _{-\infty }^{\infty }f_{j}(x)\,\psi (2^{j-1}\,x-k)\,\mathrm {d} x\end{aligned}}$

We already have $f_{j}=\sum _{\ell \in \mathbb {Z} }a_{\ell }^{j}\,\phi (2^{j}\,x-\ell )$, so

${\begin{aligned}b_{k}^{j-1}&=2^{j-1}\,\int _{-\infty }^{\infty }\psi (2^{j-1}\,x-k)\,f_{j}(x)\,\mathrm {d} x\\&=2^{j-1}\,\int _{-\infty }^{\infty }\psi (2^{j-1}\,x-k)\,\left(\sum _{\ell \in \mathbb {Z} }a_{\ell }^{j}\,\phi (2^{j}\,x-\ell )\right)\\&=2^{j-1}\,\sum _{\ell \in \mathbb {Z} }a_{\ell }^{j}\,\int _{-\infty }^{\infty }\psi (2^{j-1}\,x-k)\,\phi (2^{j}\,x-\ell )\,\mathrm {d} x\end{aligned}}$

Let $u=2^{j-1}\,x-k$, then $2^{j}\,x=2u+2k$, and $\mathrm {d} u=2^{j-1}\,\mathrm {d} x$

Also recall $q_{m}=2\int _{-\infty }^{\infty }\psi (x)\,\phi (2x-m)\,\mathrm {d} x$.

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} b_k^{j-1} &= 2^{j-1} \, \sum_{\ell \in \mathbb{Z}} a_{\ell}^j \, \underbrace{\int_{-\infty}^\infty \psi(u) \, \phi(2u + 2k - \ell) \,\mathrm{d}x}_2 \\ &= \frac{1}{2} \, \sum_{\ell \in \mathbb{Z}} a_{\ell}^j \, q_{\ell - 2k} \\ \end{align}}

Therefore, we are 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 \begin{align} a_k^{j-1} &= \frac{1}{2} \, \sum_{\ell \in \mathbb{Z}} a_{\ell}^j \, p_{2k-\ell} \\ b_k^{j-1} &= \frac{1}{2} \, \sum_{\ell \in \mathbb{Z}} a_{\ell}^j \, q_{2k-\ell} \end{align}}

If we 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 \lambda} be a filter sequence, we have

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_k^{j-1} = \left( \lambda * a^j \right)_{2k}}

Therefore, we can downsample:

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_k^{j-1} = D \, L(a^j)}

Note that this does not depend on 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 j} !!

Likewise, 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 b_k^{j-1} = D \, H(a^j)}

Projection

We are interested in 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_k^j} that are projections of 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)} onto 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 V_j} . Therefore (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 u = 2^j \, x - 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 \begin{align} a_k^j &= 2^j \, \int_{-\infty}^{\infty} f(x) \, \phi(2^j \, x - k) \\ &= \int_{-\infty}^{\infty} f(2^{-j} \, u + 2^{-j} \, k) \, \phi(u) \,\mathrm{d}u \end{align}}

"All" interesting wavelets have support contained in some finite interval 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[ a,b \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 a_k^j = \int_{a}^{b} f(2^{-j} \, u + 2^{-j} \, u) \, \phi(u) \,\mathrm{d}u}

If 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 j} is large, then 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 2^{-j} \, a \le 2^{-j} \, u \le 2^{-j} \, b} , where 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 2^{-j} \, a} 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 2^{-j} \, b} are small.

Since 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 L^2} is continuous, 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(2^{-j} \, u + 2^{-j} \, k) \approx f(2^{-j} \, k)} for small 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 2^{-j} \, u} . Now what happens next is crucial:

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_k^j \approx f(2^{-j} \, k) \, \underbrace{\int_{a}^{b} \phi(u) \,\mathrm{d}u}_1}

(the integral equality to 1 is the case in most MRAs)

This means 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 a_k^j \approx f(2^{-j} \, k)} is just a sampling of 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} at 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 2^{-j} \, k} .

The Wavelet Crime

Given samples at any level 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 j} , we can decompose 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_j} into component parts 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^{j-1}} , 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 b^{j-1}} by using the same downsampling and convolution filters