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 $w_{j}=2\phi (2x)-\phi (2x)-\phi (2x-1)=\phi (2x)-\phi (2x-1)$

Now $w_{0}\in V_{1}$ and $\not \in V_{0}$.

This is our wavelet $\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 $W_{j}$.

$w_{j}\in W_{j}$, then

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

where $b_{k}^{j}$ is the level.

Theorem. $V_{j-1}\subset V_{j}$, $V_{j}=V_{j-1}\oplus ^{\perp }W_{j-1}$

If $f_{j}\in V_{j}$, then

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

$b_{k}^{j-1}$ gives the details, and $a_{k}^{j-1}$ provides smoothing.

Proof. [omitted].

quod erat demonstrandum