MATH 414 Lecture 39

« previous | Monday, April 28, 2014 | next »

MRA in terms of Fourier Transforms

Gives (yet another) way to construct MRA $V_{j}$ spaces, scaling function, and wavelet function: by finding Fourier transforms that depend on a special polynomial $P(z)$ .

Scaling Function

Recall the scaling relation:

\phi (x)=\sum _{k\in \mathbb {Z} }p_{k}\,\phi (2x-k)

Theorem 5.19. The Fourier Transform of a MRA scaling function $\phi (x)$ is given by:

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

where $P(z)=\sum _{k\in \mathbb {Z} }p_{k}\,z^{k}$

Proof. Use the scaling relation and follow the definitions.

Evaluating the Fourier Transform of $\phi (x)=\sum _{k\in \mathbb {Z} }p_{k}\,\phi (2x-k)$ (with a change of variables $u=2x-k$ ) gives

${\begin{aligned}{\mathcal {F}}\left[\phi (x)\right](\xi )={\hat {\phi }}(\xi )&=\sum _{k\in \mathbb {Z} }p_{k}\,{\mathcal {F}}\left[\phi (2x-k)\right](\xi )&&{\mbox{where}}\ {\mathcal {F}}\left[\phi (2x-k)\right](\xi )={\frac {1}{2}}\,\mathrm {e} ^{-{\frac {i\,\xi \,k}{2}}}\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\\&=\sum _{k\in \mathbb {Z} }p_{k}\,\left({\frac {1}{2}}\,\mathrm {e} ^{-{\frac {i\,\xi \,k}{2}}}\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\right)\\&={\hat {\phi }}\left({\frac {\xi }{2}}\right)\,{\frac {1}{2}}\,\sum _{k\in \mathbb {Z} }p_{k}\,\mathrm {e} ^{-{\frac {i\,\xi \,k}{2}}}&&{\mbox{let}}\ P(z)={\frac {1}{2}}\,\sum _{k\in \mathbb {Z} }p_{k}\,z^{k}\\&={\hat {\phi }}\left({\frac {\xi }{2}}\right)\,P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\right)\end{aligned}}$

quod erat demonstrandum

Corollary. If $\phi (x)$ satisfies the normalization condition: $\int _{-\infty }^{\infty }\phi (x)\,\mathrm {d} x=1$ , then

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

Proof. Evaluating the recursive function (from the theorem above) $N$ times gives

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

Taking the limit as $N$ tends to infinity gives

${\begin{aligned}{\hat {\phi }}(\xi )&=\lim _{N\to \infty }{\hat {\phi }}\left({\frac {\xi }{2^{N}}}\right)\,\prod _{r=1}^{N}P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2^{r}}}}\right)\\&={\hat {\phi }}(0)\,\prod _{r=1}^{\infty }P\left(\mathrm {e} ^{-{\frac {i\,\xi }{2^{r}}}}\right)\end{aligned}}$

...and we know what ${\hat {\phi }}(0)$ is:

${\begin{aligned}{\hat {\phi }}(0)&={\frac {1}{\sqrt {2\pi }}}\,\int _{-\infty }^{\infty }\phi (x)\,\mathrm {e} ^{-i\,(0)\,x}\,\mathrm {d} x\\&={\frac {1}{\sqrt {2\pi }}}\,\int _{-\infty }^{\infty }\phi (x)\,\mathrm {d} x\\&={\frac {1}{\sqrt {2\pi }}}\end{aligned}}$

Therefore

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

quod erat demonstrandum

Wavelet Function

We can do a similar thing for the wavelet function $\psi (x)$ given its definition in terms of $\phi (x)$ :

\psi (x)=\sum _{k\in \mathbb {Z} }(-1)^{k}\,{\overline {p_{1-k}}}\,\phi (2x-k)

Theorem. The Fourier Transform of a MRA wavelet function $\psi (x)$ is given by:

{\hat {\psi }}(\xi )=-z\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\,{\overline {P\left(-z\right)}}

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

Moreover, assuming $p_{k}\in \mathbb {R}$ for all $k\in \mathbb {Z}$ , the above is equivalent to

{\hat {\psi }}(\xi )=-z\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\,P\left(-{\bar {z}}\right)

Proof. Since $\psi (x)=\sum _{k\in \mathbb {Z} }(-1)^{k}\,{\overline {p_{1-k}}}\,\phi (2x-k)$ , the Fourier transform of $\psi (x)$ is:

${\begin{aligned}{\mathcal {F}}\left[\psi (x)\right](\xi )&=\sum _{k\in \mathbb {Z} }(-1)^{k}\,{\overline {p_{1-k}}}\,{\mathcal {F}}\left[\phi (2x-k)\right](\xi )\\&=\sum _{k\in \mathbb {Z} }(-1)^{k}\,{\overline {p_{1-k}}}\,\left({\frac {1}{2}}\,\mathrm {e} ^{-{\frac {i\,\xi \,k}{2}}}\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\right)\\&={\hat {\phi }}\left({\frac {\xi }{2}}\right)\,{\frac {1}{2}}\,\sum _{k\in \mathbb {Z} }(-1)^{k}\,{\overline {p_{1-k}}}\,\mathrm {e} ^{-{\frac {i\,\xi \,k}{2}}}&&\ell =1-k\\&={\hat {\phi }}\left({\frac {\xi }{2}}\right)\,\left(-{\frac {1}{2}}\,\sum _{\ell \in \mathbb {Z} }(-1)^{\ell }\,{\overline {p_{\ell }}}\,\mathrm {e} ^{-{\frac {i\,\xi \,(1-\ell )}{2}}}\right)\\&={\hat {\phi }}\left({\frac {\xi }{2}}\right)\,\left(-\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\,{\frac {1}{2}}\,\sum _{\ell \in \mathbb {Z} }(-1)^{\ell }\,{\overline {p_{\ell }}}\,\mathrm {e} ^{\frac {i\,\xi \,\ell }{2}}\right)&&{\mbox{let}}\ z=\mathrm {e} ^{-{\frac {i\,\xi }{2}}}\\&={\hat {\phi }}\left({\frac {\xi }{2}}\right)\,\left(-z\,{\frac {1}{2}}\,\sum _{\ell \in \mathbb {Z} }(-1)^{\ell }\,{\overline {p_{\ell }}}\,{\overline {z}}^{\ell }\right)\\&=-z\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\,\left({\frac {1}{2}}\,\sum _{\ell \in \mathbb {Z} }{\overline {p_{\ell }}}\,(-{\overline {z}})^{\ell }\right)\\&=-z\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\,{\overline {P(-z)}}\end{aligned}}$

If $p_{k}$ is real, then ${\overline {p_{\ell }}}=p_{\ell }$ , so

${\begin{aligned}{\hat {\psi }}(\xi )&=-z\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\,\left({\frac {1}{2}}\,\sum _{\ell \in \mathbb {Z} }p_{\ell }\,(-{\overline {z}})^{\ell }\right)\\&=-z\,{\hat {\phi }}\left({\frac {\xi }{2}}\right)\,P(-{\overline {z}})\end{aligned}}$

quod erat demonstrandum

Restrictions on $P(x)$

The $P(z)$ polynomial used above must satisfy a couple of conditions. These conditions directly correspond to the conditions we placed on the $p_{k}$ coefficients.

Theorem 5.23. Given the definition of $P(z)={\frac {1}{2}}\,\sum _{k\in \mathbb {Z} }p_{k}\,z^{k}$ above, if $P(z)$ satisfies the following conditions

$P(1)=1$ (since sum of all $p_{k}$ 's is 2)
$\left|P(z)\right|^{2}+\left|P(-z)\right|^{2}=1$ for all $\left|z\right|=1$
$\left|P\left(\mathrm {e} ^{i\,t}\right)\right|>0$ for all $\left|t\right|\leq {\frac {\pi }{2}}$

Then

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

is the Fourier transform of a scaling function.

Proof.

quod erat demonstrandum

Consequently, $P(-1)=0$ since

$\sum _{k\in \mathbb {Z} }(-1)^{k}\,p_{k}=\sum _{k\in \mathbb {Z} }p_{2z}-\sum _{k\in \mathbb {Z} }p_{2z+1}=1-1=0$

Note: Conditions 1 & 2 correspond to the following conditions on the

p_{k}

's:

$\sum _{k\in \mathbb {Z} }p_{k-2\ell }\,p_{k}{=}2\delta _{\ell ,0}$
$\sum _{k\in \mathbb {Z} }p_{k}{=}2$

Daubechies Wavelet

Defined based on number $N$ of vanishing moments. This is what makes this wavelet/MRA unique.

$p_{k}=0$ if $k<0$ or $k>2N-1$ . This shall be used to construct $\psi _{N}(x)$ .

What's really important is

${\begin{aligned}P(z)&={\frac {1}{2}}\sum _{k\in \mathbb {Z} }p_{k}\,z^{k}\\&={\frac {1}{2}}\,\sum _{k=0}^{2N-1}p_{k}\,z^{k}\\&={\frac {1}{2}}\,\left(p_{0}+p_{1}\,z+p_{2}\,z^{2}+\dots +p_{2N-1}\,z^{2N-1}\right)\end{aligned}}$

This is just a polynomial of degree $2N-1$ .

In regards to vanishing moments, recall that the $k$ ^th moment $M_{k}$ is given by

M_{k}=\int _{\mathbb {R} }x^{k}\,\psi (x)\,\mathrm {d} x

The $\psi _{N}(x)$ is defined to have $N$ vanishing moments: $M_{0}=M_{1}=\dots =M_{N-1}=0$

In terms of the polynomial above, we factor as follows

${\begin{aligned}P(z)&={\frac {1}{2}}\,\left(p_{0}+p_{1}\,z+p_{2}\,z^{2}+\dots +p_{2N-1}\,z^{2N-1}\right)\\&=\left({\frac {z+1}{2}}\right)^{N}\,{\tilde {P}}(z)\end{aligned}}$