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}}$

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

We already 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 f_j = \sum_{\ell \in \mathbb{Z}} a_{\ell}^j \, \phi(2^j \, x - \ell)} , so

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

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-1} \, x - k} , 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} \, x = 2u + 2k} , 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 \mathrm{d}u = 2^{j-1} \,\mathrm{d}x}

Also recall 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 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