MATH 414 Lecture 28

« previous | Friday, March 28, 2014 | next »

Last Time

Haar Multi-Resolution Analysis (MRA)

• $V_{j}=\left\{f\in L^{2}~\mid ~f\ {\mbox{is constant on}}\ 2^{-j}\,k\leq x<2^{-j}\,\left(k+1\right)\quad \forall k\in \mathbb {Z} \right\}$
• $\phi (x)={\begin{cases}1&0\leq x<1\\0&{\mbox{otherwise}}\end{cases}}$

Properties

Nesting

$\dots \subset V_{j-1}\subset V_{j}\subset V_{j+1}\subset \dots$

Note: $V_{0}$, $V_{1}$ — there are functions in $V_{1}$ that are not in $V_{0}$.

Scaling

$f(x)\in V_{j}$ if and only if $f\left(2^{-j}\,x\right)\in V_{0}$

Orthonormal Basis

$\left\{2^{\frac {j}{2}}\,\phi \left(2^{j}\,x-k\right)\right\}_{k=-\infty }^{\infty }$ is an orthonormal basis for $V_{j}$

Haar Function Decomposition

Two Bases

$V_{j}$, $\left\{\phi \left(2^{j}\,x-k\right)\right\}_{k=-\infty }^{\infty }$ is orthogonal

$f_{j}\in V_{j}$ can be defined as $f_{j}(x)=\sum _{k=-\infty }^{\infty }a_{k}^{j}\,\phi \left(2^{j}\,x-k\right)$

(where)

Haar: $a_{k}^{j}=2^{j}\,\int _{-\infty }^{\infty }\phi \left(2^{j}\,x-k\right)\,f(x)\,\mathrm {d} x$

We know $V_{j-1}\subset V_{j}$. What is $f_{j-1}:=\mathrm {proj} _{V_{j-1}}{f_{j}}$?

$f_{j-1}(x)=\sum _{k=-\infty }^{\infty }a_{k}^{j-1}\,\phi \left(2^{j-1}\,x-k\right)$

Question: How are the $a_{k}^{j}$'s and $a_{k}^{j-1}$'s related?

Theorem. $a_{k}^{j-1}$ is the average of its "double" term and the odd that follows it:

$a_{k}^{j-1}={\frac {1}{2}}\,\left(a_{2k}^{j}+a_{2k+1}^{j}\right)$

Proof. In the arbitary sense, projection in any vector space is given by:

$\mathrm {proj} _{V}{f}=\sum _{k=-\infty }^{\infty }\left\langle f,u_{k}\right\rangle \,u_{k}$

$a_{j}^{J-1}=2^{j-1}\,\int _{-\infty }^{\infty }\phi \left(2^{J-1}\,x-k\right)\,f_{j}(x)\,\mathrm {d} x$

In this case, $u_{k}=2^{\frac {J-1}{2}}\,\phi \left(2^{J-1}\,x-k\right)$

Recall the scaling relation: $\phi (x)=\phi (2x)+\phi (2x-1)$

${\begin{aligned}\phi \left(2^{j-1}\,x-k\right)&=\phi \left(2\,\left(2^{j-1}\,x-k\right)\right)+\phi \left(2\,\left(2^{j-1}\,x-k\right)-1\right)\\\phi \left(2^{j-1}\,x-k\right)&=\phi \left(2^{j}\,x-2\,k\right)+\phi \left(2^{j}\,x-2\,k-1\right)\end{aligned}}$

Plugging this back into our integral gives

${\begin{aligned}a_{k}^{j-1}&=2^{-1}\,2^{j}\,\int _{-\infty }^{\infty }f_{j}(x)\,\left(\phi \left(2^{j}\,x-2k\right)+\phi \left(2^{j}\,x-2k-1\right)\right)\,\mathrm {d} x\\&={\frac {1}{2}}\left(2^{j}\,\int _{-\infty }^{\infty }f_{j}(x)\,\phi \left(2^{j}\,x-2k\right)\,\mathrm {d} x+2^{j}\,\int _{-\infty }^{\infty }f_{j}(x)\,\phi \left(2^{j}\,x-2k-1\right)\,\mathrm {d} x\right)\\&={\frac {1}{2}}\,\left(a_{2k}^{j}+a_{2k+1}^{j}\right)\end{aligned}}$

quod erat demonstrandum

Example

$f(x)={\begin{cases}-1&0\leq x<{\frac {1}{4}}\\4&{\frac {1}{4}}\leq x<{\frac {1}{2}}\\2&{\frac {1}{2}}\leq x<{\frac {3}{4}}\\-3&{\frac {3}{4}}\leq x<1\\0&{\mbox{otherwise}}\end{cases}}$

What's $f_{1}$?

• $j=1$
• $a_{0}^{2}=-1$
• $a_{1}^{2}=4$
• $a_{2}^{2}=2$
• $a_{3}^{2}=-3$
• $a_{k}^{2}=0$ for $k\leq -1$ or $k\geq 4$

Hence

• if $k\leq -1$, then $a_{k}^{1}=0$
• if $k=0$, then $a_{0}^{1}={\frac {1}{2}}\,\left(-1+4\right)={\frac {3}{2}}$
• If $k=1$, then $a_{1}^{1}={\frac {1}{2}}\,\left(2-3\right)=-{\frac {1}{2}}$
• if $k\geq 2$, then $a_{k}^{1}=0$

Then the function $f_{2}$ is given by $f_{2}={\frac {3}{2}}\,\phi \left(2x\right)-{\frac {1}{2}}\,\phi \left(2x-1\right)$

$f_{1}$ is just the projection of $f_{2}$ onto the space $V_{1}$

Wavelet Spaces

$V_{j}\subset V_{j+1}$ and $V_{j}\neq V_{j+1}$

We saw that ,given $f_{j+1}$, we can find $f_{j}:=\mathrm {proj} _{V_{j}}{\left(f_{j+1}\right)}$

We know $w_{j}:=f_{j+1}-\mathrm {proj} _{V_{j}}{\left(f_{j+1}\right)}$ is orthogonal to $V_{j}$ (it cannot possibly be in $V_{j}$ unless $w_{j}=0$)

What is $w_{j}$?

$w$ is an open secret... it stands for "wavelet"

Let $W_{j}=V_{j}^{\perp }\cap V_{j+1}=\left\{w\in V_{j+1}~\mid ~w\perp f_{j}\quad \forall f_{j}\in V_{j}\right\}$

What is a basis for $W_{j}$?

We'll work with $V_{1}$, $V_{0}$, $W_{0}$

$f_{1}(x)=2\,\phi \left(2x\right)$

this means that $a_{0}^{1}=2$

$\mathrm {proj} _{V_{0}}{\left(f_{1}\right)}=\sum _{k=-\infty }^{\infty }a_{k}^{0}\,\phi \left(x-k\right)$

$a_{k}^{0}={\frac {a_{2k}+a_{2k+1}}{2}}={\begin{cases}a_{0}^{0}=2\,\left({\frac {1}{2}}+{\frac {0}{2}}\right)=1\\a_{1}^{0}={\frac {a_{2}+a_{3}}{2}}=0\\a_{k}^{0}=0&k\neq 0\end{cases}}$

$f_{0}=\phi (x)$

$w_{0}=f_{1}-f_{0}=2\phi \left(2x\right)-\phi (x)$, BUT $\phi (x)=\phi (2x)+\phi (2x-1)$. Therefore 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 w_j = 2 \phi(2x) - \phi(2x) - \phi(2x-1) = \phi(2x) - \phi(2x-1)}

Now 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 w_0 \in V_1} 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 \not\in V_0} .

This is our wavelet 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(x)} ! (thunderous applause)

$\psi (x)={\begin{cases}1&0\leq x<{\frac {1}{2}}\\-1&{\frac {1}{2}}\leq x<1\\0&{\mbox{otherwise}}\end{cases}}$

We can show that $\left\{2^{\frac {1}{2}}\,\psi \left(2^{j}\,x-k\right)\right\}_{k=-\infty }^{\infty }$ 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 W_j} .

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 w_j \in W_j} , 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 \begin{align} w_j (x) &= \sum_{k=-\infty}^\infty b_k^j \, \psi \left( 2^j \, x - k \right) \\ b_k^j &= 2^j \, \int_{-\infty}^{\infty} \psi \left( 2^j \, x - k \right) \,\mathrm{d}x \end{align}}

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 b_k^j} is the level.

Theorem. 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-1} \subset V_j} , 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 = V_{j-1} \oplus^\perp W_{j-1}}

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 f_j \in V_j} , 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 \begin{align} \mathrm{proj}_{W_{j-1}}{ \left( f_j \right) } &= \sum_{k = -\infty}^\infty b_k^{j-1} \, \psi \left( 2^{j-1} \, x - k \right) \\ b_k^{j-1} &= \frac{1}{2} \, \left( a_{2k}^j - a_{2k+1}^j \right) a_k^{j-1} &= \frac{1}{2} \, \left( a_{2k}^j + a_{2k+1}^j \right) \end{align}}

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}} gives the details, 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 a_k^{j-1}} provides smoothing.

Proof. [omitted].

quod erat demonstrandum