MATH 414 Lecture 32

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

End Exam 2 content

Exam Review

Sampling Theorem

given band-limited $f(t)$, the support of $\hat{f}$ is a subset of $[-\mathrm{\Omega },\mathrm{\Omega }]$.

• $\mathrm{\Omega }$ is the angular frequency (in radians / sec)
• $\frac{\mathrm{\Omega }}{2\pi }$ is the natural frequency, the highest frequency in the singal (in hertz)
• In the theorem below, $\frac{\pi }{\mathrm{\Omega }}$ is the sampling interval (in seconds; time between samples)
• $\frac{\omega }{\pi }$ (twice the natural frequency) is the Nyquist rate

Theorem. $\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}f\left(\frac{j\pi }{\mathrm{\Omega }}\right)\frac{\sin (\mathrm{\Omega }t-j\pi )}{\mathrm{\Omega }t-j\pi }$

Proof. [omitted]

quod erat demonstrandum

Sampling at anything lower than the nyquist frequency results in lost information (not enough to see the full ups and downs of the waves)

Discrete Fourier Transforms of Periodic Sequnecs

Given two $n$-periodic sequences $y,z\in S_n$, show that ${\hat{z}}_k=w^k{\hat{y}}_k$, where $w={\mathrm{e}}^{\frac{2\pi i}{n}}$

$\begin{array}{rl}{\hat{y}}_k& =\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{w}}\\ {\hat{z}}_k& =\sum _{j=0}^{n-1}{z}_j\stackrel{jk}{\bar{w}}\\ & =\sum _{j=0}^{n-1}{y}_{k+1}\stackrel{jk}{\bar{w}}\\ & =\sum _{\ell =1}^n{y}_{\ell }\stackrel{(\ell -1)k}{\bar{w}}\\ & =\stackrel{-k}{\bar{w}}\sum _{\ell =1}^n{y}_{\ell }\stackrel{\ell k}{\bar{w}}\\ & =w^k\sum _{\ell =1}^n{y}_{\ell }\stackrel{\ell k}{\bar{w}}\\ & =w^k(\sum _{\ell =1}^{n-1}{y}_{\ell }\stackrel{\ell k}{\bar{w}}+y_n\stackrel{nk}{\bar{w}})\\ & =w^k(\sum _{\ell =1}^{n-1}{y}_{\ell }\stackrel{\ell k}{\bar{w}}+y_0\cdot 1)\\ & =w^k\sum _{\ell =0}^{n-1}{y}_{\ell }\stackrel{\ell k}{\bar{w}}\\ & =w^k{\hat{y}}_k\end{array}$

Proof of Haar Decomposition

Given $f_j=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^j\varphi (2^{j}x-k)$, the projection of $f_j$ onto $V_{j-1}$ is given by

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V_{j-1}}(f_j)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_k^{j-1}\varphi (2^{j-1}x-k)$

Prove that $a_k^{j-1}=\frac{1}{2}(a_{2k}^j+a_{2k+1}^j)$.

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

Fast Fourier Transform

Given data $y=\{y_0,y_1,y_2,\dots ,y_{2N-1}\}$, where $N=2^{L-1}$ for $L\in \mathbb{\mathbb{N}}$.

${{ℱ}}_{2N}\left[y\right]={{ℱ}}_N{[y_0,y_2,\dots ,y_{2N-2}]}_k+\stackrel{k}{\stackrel{‾}{W}}{{ℱ}}_N[y_1,y_3,\dots ,y_{2N-1}]$

How many multiplications does it take to compute ${{ℱ}}_{2N}$?

• $K_L=2K_{L-1}+2^L$
• $K_L\sim N\log N$