MATH 414 Lecture 38

« previous | Friday, April 25, 2014 | next »

Last Time

Scaling Function

$\phi (x)=\sum _{k}p_{k}\,\phi (2x-k)$

${\hat {\phi }}(\xi )=P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\right)\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)$, where $P(z)={\frac {1}{2}}\,\sum _{k}p_{k}\,z^{k}$

Hence ${\hat {\phi }}(\xi )={\frac {1}{\sqrt {2\pi }}}\,\prod _{r=1}^{\infty }P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2^{r}}}}\right)$

• This means we can start with $p_{k}$'s and get ${\hat {\phi }}(\xi )$ and $\phi (x)={\mathcal {F}}^{-1}\left[{\hat {\phi }}\right]$
• $p_{k}$'s satisfy at least the following properties:
  • $\sum _{k}p_{k-2\ell }\,p_{k}=2\delta _{\ell ,0}$
  • $\sum _{k}p_{k}=2$
  • $\sum _{k}p_{2k}=1$ and $\sum _{k}p_{2k+1}=1$.

Wavelet

${\hat {\psi }}(\xi )=-\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\,P\left(-\mathrm {e} ^{\frac {i\,\xi }{2}}\right)\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)$

${\hat {\psi }}$ is known!

Haar Example

$P(z)={\frac {1}{2}}\,\left(1+z\right)$

${\begin{aligned}v_{N}&=\prod _{r=1}^{N}{\frac {1}{2}}\,\left(1+\mathrm {e} ^{-{\frac {i\,\xi }{2^{r}}}}\right)\\&=\left({\frac {1+\mathrm {e} ^{-{\frac {i\,\xi }{2^{N}}}}}{2}}\right)\,\left(1+\mathrm {e} ^{-{\frac {i\,\xi }{2^{N-1}}}}\right)\dots \left(1+\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\right)\end{aligned}}$

Let $z=\mathrm {e} ^{-{\frac {i\,\xi }{2^{N}}}}$. Then

${\begin{aligned}v_{N}&=\left({\frac {1+z}{2}}\right)\,\left({\frac {1+z}{2}}\right)\,\left({\frac {1+z^{4}}{2}}\right)\dots \left({\frac {1+z^{2^{N-1}}}{2}}\right)\\(1-z)\,v_{N}&={\frac {1}{2^{N}}}\,(1-z^{2n})\\&={\frac {1}{2^{N}}}\,\left(1-\mathrm {e} ^{-i\,\xi }\right)\\v_{N}&={\frac {1}{1-\mathrm {e} ^{-{\frac {i\,\xi }{2^{N}}}}}}\,\left(1-\mathrm {e} ^{-i\,\xi }\right)\,{\frac {1}{2^{N}}}\end{aligned}}$

We take a power series expansion of $\mathrm {e} ^{x}=1+x+{\frac {x^{2}}{2}}+\dots$

${\begin{aligned}1-\mathrm {e} ^{-{\frac {i\,\xi }{2^{N}}}}&=\left({\frac {i\,\xi }{2^{N}}}\right)+{\frac {(\dots )}{2^{2N}}}+\dots \\2^{N}\,\left(1-\mathrm {e} ^{-{\frac {i\,\xi }{2^{N}}}}\right)&=i\,\xi +O(2^{-N})\end{aligned}}$

The limit as $N\to \infty$ gives

$V_{N}=\dots ={\frac {2\sin {\left({\frac {\xi }{2}}\right)}}{\xi }}$

Hence ${\hat {\phi }}(\xi )={\frac {1}{\sqrt {2\pi }}}\,{\frac {2}{\xi }}\,\sin {\left({\frac {\xi }{2}}\right)}={\mathcal {F}}\left[\phi _{haar}\right]$

${\hat {\phi }}(\xi )={\frac {1}{\sqrt {2\pi }}}\,\prod _{r=1}^{\infty }P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2^{r}}}}\right)$, where ${\hat {\phi }}_{N}$ is a partial product.

When ${\hat {\phi }}$ satisfies an iterative relation:

• $\phi _{0}(x)=\phi _{haar}(x)$
• $\phi _{N}(x)=\sum _{k}p_{k}\,\phi _{N-1}(2x-k)$

Theorem. Suppose $P(z)={\frac {1}{2}}\,\sum _{k}p_{k}\,z^{k}$, where the $p_{k}$'s are given. If:

1. $\left|P(z)\right|^{2}+\left|P(-z)\right|^{2}=1$, $\left|z\right|=1$, where $z=\mathrm {e} ^{i\,t}$
2. $P(1)=1$
3. $\left|P\left(\mathrm {e} ^{i\,t}\right)\right|>0$ for $\left|t\right|\leq {\frac {\pi }{2}}$

Then ${\frac {1}{\sqrt {2\pi }}}\,\prod _{r=1}^{N}P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\right)$ converges in $L^{2}$ to a function ${\hat {\phi }}(\xi )$.

Proof.

quod erat demonstrandum

Point:

1. $\phi (x)={\mathcal {F}}^{-1}\left[{\hat {\phi }}(\xi )\right]$ is a scaling function
2. ...

Moments of Wavelet

A moment of a function $\psi (x)$ is an integral of the form:

$M_{k}=\int _{-\infty }^{\infty }x^{k}\,\psi (x)\,\mathrm {d} x$, where $k=0,1,\dots$

Recall that if $M_{0}=0$ and $M_{1}=0$, then for the Daubechies ( $N=2$ ) wavelet (projection of $f(x)$ onto $\psi _{jk}$ component of $W_{j}$ space):

${\begin{aligned}b_{k}^{j-1}&=\left\langle f,\psi _{jk}\right\rangle =\left\langle f(x),\psi \left(2^{j}\,x-k\right)\right\rangle \\&=\int _{-\infty }^{\infty }f(x)\,\psi \left(2^{j}\,x-k\right)\,\mathrm {d} x\\&=\int _{-\infty }^{\infty }f\left(2^{-j}\,k+2^{-j}\,u\right)\,\psi (u)\,\mathrm {d} u\end{aligned}}$

We can take the Taylor series expansion of $f$ centered at $2^{-j}\,u$

$f\left(2^{-j}\,k+2^{-j}\,u\right)=f\left(2^{-j}\,k\right)+f'\left(2^{-j}\,k\right)\,2^{-j}\,u+{\frac {f''\left(2^{-j}\,k\right)}{2}}\,\left(2^{-j}\,u\right)^{2}+\dots$

... and plug it into the inner product projection for $b_{k}^{j-1}$ above:

${\begin{aligned}b_{k}^{j-1}&=f\left(2^{-j}\,k\right)\,\int _{-\infty }^{\infty }\psi (x)\,\mathrm {d} x+f'\left(2^{-j}\,k\right)\,2^{-j}\,u\,\int _{-\infty }^{\infty }u\,\psi (x)\,\mathrm {d} x+f''\left(2^{-j}\,k\right)\,2^{-2j}\,\int _{-\infty }^{\infty }u^{2}\,\psi (x)\,\mathrm {d} x+\dots \\&\approx {\frac {f''\left(2^{-j}\,k\right)\,2^{-2j}}{2}}\,M_{2}\end{aligned}}$

If $j$ is much greater than 1 and $f$ is smooth, then $b_{k}^{j-1}$ is small.

If $f'$ is discontinuous in $k\leq u<k+1$, then coefficients can become large.

Hence we can detect singularities (discontinuities) in $f'$ because $b_{k}^{j-1}$ will be relatively large near $x_{sing}=2^{-j}\,k$

If $M_{k}=0$ for $k=0,\ldots ,N-1$, then for smooth $f$,

$b_{k}^{j-1}\approx {\frac {f^{(N)}\left(2^{-j}\,k\right)}{N!}}\,2^{-N\,j}\,M_{N}+\dots$

$\psi (\xi )=-\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\,P\left(-\mathrm {e} ^{\frac {i\,\xi }{2}}\right)\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)$

$M_{k}=\int _{-\infty }^{\infty }x^{k}\,\psi (x)\,\mathrm {d} x={\sqrt {2\pi }}i^{k}{\frac {\mathrm {d} ^{k}\,{\hat {\psi }}}{\mathrm {d} \xi ^{k}}}$

Vanishing Moments

Demand: $P(z)=\left({\frac {1+z}{2}}\right)^{N}\,{\tilde {P}}(z)$, ${\tilde {P}}(-1)\neq 0$

${\hat {\psi }}(\xi )=\sin ^{N}\left({\frac {\xi }{4}}\right)\,F\left(\mathrm {e} ^{\frac {i\,\xi }{2}}\right)\sim \xi ^{N}\,F(\dots )$

$\left.{\frac {\mathrm {d} ^{k}{\hat {\psi }}}{\mathrm {d} \xi ^{k}}}\right|_{\xi =0}=0$ implies $M_{k}=0$

Require: $P(z)={\frac {1}{2}}\,\left(p_{0}+p_{1}\,z+p_{2}\,z^{2}+p_{3}\,z^{3}\right)$

$P(z)={\frac {\left(1+z\right)^{2}}{2}}\,\left(a\,z+b\right)$, where ${\tilde {P}}(z)=a\,z+b$

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} \hat{\psi}(\xi) &= -\mathrm{e}^{-\frac{i\,\xi}{2}} \, \left( \frac{1-\mathrm{e}^{ \frac{i\,\xi}{2} }}{2} \right)^2 \, \hat{\phi} \left( \frac{\xi}{2} \right) \\ &= (-i)^2 \, \sin^2 \left( \frac{\xi}{4} \right) \, \hat{\phi} \left( \frac{\xi}{2} \right) \\ &= \sin^2 \left( \frac{\xi}{4} \right) \, \tilde{P} \left( -\mathrm{e}^{ \frac{i \, \i}{2}} \right) \, \hat{\phi} \left( \frac{\xi}{2} \right) \\ &= \dots \end{align}}

Going back to conditions on $P(z)$...

$P(1)=\left({\frac {2}{2}}\right)^{2}\,(a+b)=a+b=1$, hence $P(z)=\left({\frac {1+z}{2}}\right)^{2}\left(b\,z+1-b\right)$

Satisfy: $\left|P(z)\right|^{2}+\left|P(-z)\right|^{2}=1$, where $z=\mathrm {e} ^{i\,\theta }$.

$\cos ^{4}\left({\frac {\theta }{2}}\right)\,\left|b\,\mathrm {e} ^{i\,\theta }+1-b\right|^{2}+\sin ^{4}\left({\frac {\theta }{2}}\right)\,\left|-b\,\mathrm {e} ^{i\,\theta }+1-b\right|^{2}=1$

Use trig identities until you're sick in the face... What you get when all is said and done is:

${\begin{aligned}a^{2}+\left(1-a\right)^{2}&=4\\2a^{2}-2a+1&=4\\a^{2}-a-3&=0\\a&={\frac {1\pm {\sqrt {3}}}{4}}\end{aligned}}$

$a$ and $b$ form the $p_{k}$'s for the Daubechies wavelet