MATH 414 Lecture 28

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

Last Time

Haar Multi-Resolution Analysis (MRA)

• $V_j=\{f\in L^2\mid f\text{is constant on}{2}^{-j}k\le x<2^{-j}(k+1)\mathrm{\forall }k\in \mathbb{\mathbb{Z}}\}$
• $\varphi (x)=\{\begin{array}{ll}1& 0\le x<1\\ 0& \text{otherwise}\end{array}$

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}}\varphi (2^{j}x-k)\right\}}_{k=-\mathrm{\infty }}^{\mathrm{\infty }}$ is an orthonormal basis for $V_j$

Haar Function Decomposition

Two Bases

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

$f_j\in V_j$ can be defined as $f_j(x)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^j\varphi (2^{j}x-k)$

(where)

Haar: $a_k^j=2^j\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\varphi (2^{j}x-k)f(x)\mathrm{d}x$

We know $V_{j-1}\subset V_j$. What is $f_{j-1}:={\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V_{j-1}}{f}_j$?

$f_{j-1}(x)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^{j-1}\varphi (2^{j-1}x-k)$

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}(a_{2k}^j+a_{2k+1}^j)$

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

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V}f=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}⟨f,u_k⟩u_k$

$a_j^{J-1}=2^{j-1}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\varphi (2^{J-1}x-k)f_j(x)\mathrm{d}x$

In this case, $u_k=2^{\frac{J-1}{2}}\varphi (2^{J-1}x-k)$

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

$\begin{array}{rl}\varphi (2^{j-1}x-k)& =\varphi \left(2(2^{j-1}x-k)\right)+\varphi (2(2^{j-1}x-k)-1)\\ \varphi (2^{j-1}x-k)& =\varphi (2^{j}x-2k)+\varphi (2^{j}x-2k-1)\end{array}$

Plugging this back into our integral gives

$\begin{array}{rl}{a}_k^{j-1}& =2^{-1}{2}^j\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}{f}_j(x)(\varphi (2^{j}x-2k)+\varphi (2^{j}x-2k-1))\mathrm{d}x\\ & =\frac{1}{2}(2^j\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}{f}_j(x)\varphi (2^{j}x-2k)\mathrm{d}x+2^j\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}{f}_j(x)\varphi (2^{j}x-2k-1)\mathrm{d}x)\\ & =\frac{1}{2}(a_{2k}^j+a_{2k+1}^j)\end{array}$

quod erat demonstrandum

Example

$f(x)=\{\begin{array}{ll}-1& 0\le x<\frac{1}{4}\\ 4& \frac{1}{4}\le x<\frac{1}{2}\\ 2& \frac{1}{2}\le x<\frac{3}{4}\\ -3& \frac{3}{4}\le x<1\\ 0& \text{otherwise}\end{array}$

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\le -1$ or $k\ge 4$

Hence

• if $k\le -1$, then $a_k^1=0$
• if $k=0$, then $a_0^1=\frac{1}{2}(-1+4)=\frac{3}{2}$
• If $k=1$, then $a_1^1=\frac{1}{2}(2-3)=-\frac{1}{2}$
• if $k\ge 2$, then $a_k^1=0$

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

$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\ne V_{j+1}$

We saw that ,given $f_{j+1}$, we can find $f_j:={\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V_j}\left(f_{j+1}\right)$

We know $w_j:=f_{j+1}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{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}=\{w\in V_{j+1}\mid w\perp f_j\mathrm{\forall }{f}_j\in V_j\}$

What is a basis for $W_j$?

We'll work with $V_1$, $V_0$, $W_0$

$f_1(x)=2\varphi \left(2x\right)$

this means that $a_0^1=2$

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V_0}\left(f_1\right)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^0\varphi (x-k)$

$a_k^0=\frac{a_{2k}+a_{2k+1}}{2}=\{\begin{array}{l}{a}_0^0=2(\frac{1}{2}+\frac{0}{2})=1\\ a_1^0=\frac{a_2+a_3}{2}=0\\ a_k^0=0& k\ne 0\end{array}$

$f_0=\varphi (x)$

$w_0=f_1-f_0=2\varphi \left(2x\right)-\varphi (x)$, BUT $\varphi (x)=\varphi (2x)+\varphi (2x-1)$. Therefore $w_j=2\varphi (2x)-\varphi (2x)-\varphi (2x-1)=\varphi (2x)-\varphi (2x-1)$

Now $w_0\in V_1$ and $\in ̸V_0$.

This is our wavelet $\psi (x)$! (thunderous applause)

$\psi (x)=\{\begin{array}{ll}1& 0\le x<\frac{1}{2}\\ -1& \frac{1}{2}\le x<1\\ 0& \text{otherwise}\end{array}$

We can show that ${\left\{2^{\frac{1}{2}}\psi (2^{j}x-k)\right\}}_{k=-\mathrm{\infty }}^{\mathrm{\infty }}$ is an orthonormal basis for $W_j$.

$w_j\in W_j$, then

$\begin{array}{rl}{w}_j(x)& =\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{b}_k^j\psi (2^{j}x-k)\\ b_k^j& =2^j\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\psi (2^{j}x-k)\mathrm{d}x\end{array}$

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{array}{rl}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{W_{j-1}}\left(f_j\right)& =\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{b}_k^{j-1}\psi (2^{j-1}x-k)\\ b_k^{j-1}& =\frac{1}{2}(a_{2k}^j-a_{2k+1}^j)a_k^{j-1}& =\frac{1}{2}(a_{2k}^j+a_{2k+1}^j)\end{array}$

$b_k^{j-1}$ gives the details, and $a_k^{j-1}$ provides smoothing.

Proof. [omitted].

quod erat demonstrandum