MATH 414 Lecture 28

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

Last Time

Haar Multi-Resolution Analysis (MRA)

• 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\{ f \in L^2 ~\mid~ f\ \mbox{is constant on}\ 2^{-j}\,k \le 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

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 \dots \subset V_{j-1} \subset V_j \subset V_{j+1} \subset \dots}

Note: 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_0} , 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_1} — there are functions in 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_1} that are not in $V_{0}$.

Scaling

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) \in V_j} if and only 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 \left( 2^{-j} \, x \right) \in V_0}

Orthonormal Basis

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 \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 V_j}

Haar Function Decomposition

Two Bases

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} , 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\{ \phi \left( 2^j \, x - k \right) \right\}_{k=-\infty}^\infty} is orthogonal

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} 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$
• 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_1^2 = 4}
• $a_{2}^{2}=2$
• $a_{3}^{2}=-3$
• 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^2 = 0} for $k\leq -1$ or 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 k \ge 4}

Hence

• if $k\leq -1$, 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 a_k^1 = 0}
• 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 k = 0} , 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 a_0^1 = \frac{1}{2} \, \left( -1 + 4 \right) = \frac{3}{2}}
• If $k=1$, 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 a_1^1 = \frac{1}{2} \, \left( 2-3 \right) = -\frac{1}{2}}
• 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 k \ge 2} , 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 a_k^1 = 0}

Then the function 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} is given by 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 = \frac{3}{2} \, \phi \left( 2x \right) - \frac{1}{2} \, \phi \left( 2x-1 \right)}

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_1} is just the projection 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_2} onto the space 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_1}

Wavelet Spaces

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

We saw that ,given 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+1}} , we can find 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 := \mathrm{proj}_{V_j}{ \left( f_{j+1} \right) }}

We know 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 := f_{j+1} - \mathrm{proj}_{V_j}{ \left( f_{j+1} \right) }} is orthogonal to 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} (it cannot possibly be in 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} unless 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 = 0} )

What is 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} is an open secret... it stands for "wavelet"

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

We'll work 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 V_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 V_0} , 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}

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_1(x) = 2 \, \phi \left( 2x \right)}

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_0^1 = 2}

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

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_0 = \phi(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 w_0 = f_1 - f_0 = 2 \phi \left( 2x \right) - \phi(x)} , BUT 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 \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)

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) = \begin{cases} 1 & 0 \le x < \frac{1}{2} \\ -1 & \frac{1}{2} \le x < 1 \\ 0 & \mbox{otherwise} \end{cases}}

We can show 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 \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