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:

$\varphi (x)=\sum _{k\in \mathbb{\mathbb{Z}}}{p}_k\varphi (2x-k)$

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

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

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

Proof. Use the scaling relation and follow the definitions.

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

$\begin{array}{rlrl}{ℱ}[\varphi (x)](\xi )=\hat{\varphi }(\xi )& =\sum _{k\in \mathbb{\mathbb{Z}}}{p}_k{ℱ}[\varphi (2x-k)](\xi )& & \text{where}{ℱ}[\varphi (2x-k)](\xi )=\frac{1}{2}{\mathrm{e}}^{-\frac{i\xi k}{2}}\hat{\varphi }\left(\frac{\xi }{2}\right)\\ & =\sum _{k\in \mathbb{\mathbb{Z}}}{p}_k\left(\frac{1}{2}{\mathrm{e}}^{-\frac{i\xi k}{2}}\hat{\varphi }\left(\frac{\xi }{2}\right)\right)\\ & =\hat{\varphi }\left(\frac{\xi }{2}\right)\frac{1}{2}\sum _{k\in \mathbb{\mathbb{Z}}}{p}_k{\mathrm{e}}^{-\frac{i\xi k}{2}}& & \text{let}P(z)=\frac{1}{2}\sum _{k\in \mathbb{\mathbb{Z}}}{p}_k{z}^k\\ & =\hat{\varphi }\left(\frac{\xi }{2}\right)P\left({\mathrm{e}}^{-\frac{i\xi }{2}}\right)\end{array}$

quod erat demonstrandum

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

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

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

$\begin{array}{rl}\hat{\varphi }(\xi )& =\hat{\varphi }\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{\varphi }\left(\frac{\xi }{2^N}\right)\prod _{r=1}^{N}P\left({\mathrm{e}}^{-\frac{i\xi }{2^r}}\right)\end{array}$

Taking the limit as $N$ tends to infinity gives

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

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

$\begin{array}{rl}\hat{\varphi }(0)& =\frac{1}{\sqrt{2\pi }}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\varphi (x){\mathrm{e}}^{-i(0)x}\mathrm{d}x\\ & =\frac{1}{\sqrt{2\pi }}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\varphi (x)\mathrm{d}x\\ & =\frac{1}{\sqrt{2\pi }}\end{array}$

Therefore

$\hat{\varphi }(\xi )=\frac{1}{\sqrt{2\pi }}\prod _{r=1}^{\mathrm{\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 $\varphi (x)$:

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

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

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

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

---

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

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

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

$\begin{array}{rl}{ℱ}[\psi (x)](\xi )& =\sum _{k\in \mathbb{\mathbb{Z}}}(-1{)}^k\overline{p_{1-k}}{ℱ}[\varphi (2x-k)](\xi )\\ & =\sum _{k\in \mathbb{\mathbb{Z}}}(-1{)}^k\overline{p_{1-k}}\left(\frac{1}{2}{\mathrm{e}}^{-\frac{i\xi k}{2}}\hat{\varphi }\left(\frac{\xi }{2}\right)\right)\\ & =\hat{\varphi }\left(\frac{\xi }{2}\right)\frac{1}{2}\sum _{k\in \mathbb{\mathbb{Z}}}(-1{)}^k\overline{p_{1-k}}{\mathrm{e}}^{-\frac{i\xi k}{2}}& & \ell =1-k\\ & =\hat{\varphi }\left(\frac{\xi }{2}\right)(-\frac{1}{2}\sum _{\ell \in \mathbb{\mathbb{Z}}}(-1{)}^{\ell }\overline{p_{\ell }}{\mathrm{e}}^{-\frac{i\xi (1-\ell )}{2}})\\ & =\hat{\varphi }\left(\frac{\xi }{2}\right)(-{\mathrm{e}}^{-\frac{i\xi }{2}}\frac{1}{2}\sum _{\ell \in \mathbb{\mathbb{Z}}}(-1{)}^{\ell }\overline{p_{\ell }}{\mathrm{e}}^{\frac{i\xi \ell }{2}})& & \text{let}z={\mathrm{e}}^{-\frac{i\xi }{2}}\\ & =\hat{\varphi }\left(\frac{\xi }{2}\right)(-z\frac{1}{2}\sum _{\ell \in \mathbb{\mathbb{Z}}}(-1{)}^{\ell }\overline{p_{\ell }}\stackrel{\ell }{\bar{z}})\\ & =-z\hat{\varphi }\left(\frac{\xi }{2}\right)(\frac{1}{2}\sum _{\ell \in \mathbb{\mathbb{Z}}}\overline{p_{\ell }}(-\bar{z}{)}^{\ell })\\ & =-z\hat{\varphi }\left(\frac{\xi }{2}\right)\overline{P(-z)}\end{array}$

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

$\begin{array}{rl}\hat{\psi }(\xi )& =-z\hat{\varphi }\left(\frac{\xi }{2}\right)(\frac{1}{2}\sum _{\ell \in \mathbb{\mathbb{Z}}}{p}_{\ell }(-\bar{z}{)}^{\ell })\\ & =-z\hat{\varphi }\left(\frac{\xi }{2}\right)P(-\bar{z})\end{array}$

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{\mathbb{Z}}}{p}_k{z}^k$ above, if $P(z)$ satisfies the following conditions

1. $P(1)=1$ (since sum of all $p_k$'s is 2)
2. ${|P(z)|}^2+{|P(-z)|}^2=1$ for all $\left|z\right|=1$
3. $\left|P\left({\mathrm{e}}^{it}\right)\right|>0$ for all $\left|t\right|\le \frac{\pi }{2}$

Then

$\hat{\varphi }(\xi )=\frac{1}{\sqrt{2\pi }}\prod _{r=1}^{\mathrm{\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{\mathbb{Z}}}(-1{)}^k{p}_k=\sum _{k\in \mathbb{\mathbb{Z}}}{p}_{2z}-\sum _{k\in \mathbb{\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{\mathbb{Z}}}{p}_{k-2\ell }{p}_k=2{\delta }_{\ell ,0}$
• $\sum _{k\in \mathbb{\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{array}{rl}P(z)& =\frac{1}{2}\sum _{k\in \mathbb{\mathbb{Z}}}{p}_k{z}^k\\ & =\frac{1}{2}\sum _{k=0}^{2N-1}{p}_k{z}^k\\ & =\frac{1}{2}(p_0+p_{1}z+p_2{z}^2+\dots +p_{2N-1}{z}^{2N-1})\end{array}$

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=\underset{\mathbb{ℝ}}{\int }{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{array}{rl}P(z)& =\frac{1}{2}(p_0+p_{1}z+p_2{z}^2+\dots +p_{2N-1}{z}^{2N-1})\\ & ={\left(\frac{z+1}{2}\right)}^N\tilde{P}(z)\end{array}$

Where $\tilde{P}(-1)\ne 0$ and $\tilde{P}$ has degree $N-1$.

Matlab Example

Suppose we wanted to find a wavelet decomposition for $f(t)=4t^2+t-1$

This is a degree 2 polynomial, so in order to have no $b^j$'s, we need a Daubechies wavelet with $N$ vanishing moments such that $N-1=2$: $N=3$:

$f(t)$ and $db4$ level 1 decomposition approximation $f_1(x)=\sum _{k\in \mathbb{\mathbb{Z}}}{a}_k^1\varphi (2k-1)$.