MATH 414 Lecture 32

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

End Exam 2 content

Exam Review

Sampling Theorem

given band-limited 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(t)} , the support 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 \hat{f}} is a subset 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 \left[ -\Omega, \Omega \right]} .

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

Theorem. $\sum _{j=-\infty }^{\infty }f\left({\frac {j\,\pi }{\Omega }}\right)\,{\frac {\sin {\left(\Omega \,t-j\,\pi \right)}}{\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{aligned}{\hat {y}}_{k}&=\sum _{j=0}^{n-1}y_{j}\,{\overline {w}}^{j\,k}\\{\hat {z}}_{k}&=\sum _{j=0}^{n-1}z_{j}\,{\overline {w}}^{j\,k}\\&=\sum _{j=0}^{n-1}y_{k+1}\,{\overline {w}}^{j\,k}\\&=\sum _{\ell =1}^{n}y_{\ell }\,{\overline {w}}^{(\ell -1)\,k}\\&={\overline {w}}^{-k}\,\sum _{\ell =1}^{n}y_{\ell }\,{\overline {w}}^{\ell \,k}\\&=w^{k}\,\sum _{\ell =1}^{n}\,y_{\ell }\,{\overline {w}}^{\ell \,k}\\&=w^{k}\,\left(\sum _{\ell =1}^{n-1}\,y_{\ell }\,{\overline {w}}^{\ell \,k}+y_{n}\,{\overline {w}}^{n\,k}\right)\\&=w^{k}\,\left(\sum _{\ell =1}^{n-1}\,y_{\ell }\,{\overline {w}}^{\ell \,k}+y_{0}\cdot 1\right)\\&=w^{k}\,\sum _{\ell =0}^{n-1}\,y_{\ell }\,{\overline {w}}^{\ell \,k}\\&=w^{k}\,{\hat {y}}_{k}\end{aligned}}$

Proof of Haar Decomposition

Given $f_{j}=\sum _{k=-\infty }^{\infty }a_{k}^{j}\,\phi (2^{j}\,x-k)$, the projection of $f_{j}$ onto $V_{j-1}$ is given by

$\mathrm {proj} _{V_{j-1}}{(f_{j})}=\sum _{k=-\infty }^{\infty }a_{k}^{j-1}\,\phi (2^{j-1}\,x-k)$

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

${\begin{aligned}a_{k}^{j-1}&=2^{j-1}\,\int _{-\infty }^{\infty }f_{j}(x)\,\phi (2^{j-1}\,x-k)\,\mathrm {d} x\\\phi (2^{j-1}\,x-k)&=\phi (2(2^{j-1}\,x-k))+\phi (2(2^{j-1}\,x-k)-1)\\&=\phi (2^{j}\,x-2k)+\phi (2^{j}\,x-2k-1)\\&=2^{j-1}\,\int _{-\infty }^{\infty }f_{j}(x)\,\phi (2^{j}\,x-2k)\,\mathrm {d} x+2^{j-1}\,\int _{-\infty }^{\infty }f_{j}(x)\,\phi (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}\,\left(a_{2k}^{j}+a_{2k+1}^{j}\right)\end{aligned}}$

Fast Fourier Transform

Given data $y=\left\{y_{0},y_{1},y_{2},\ldots ,y_{2N-1}\right\}$, 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 N = 2^{L-1}} 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 L \in \mathbb{N}} .

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 \mathcal{F}_{2N}\left[ y \right] = \mathcal{F}_{N}\left[ y_0, y_2, \ldots, y_{2N-2} \right]_k + \overline{W}^k \, \mathcal{F}_N \left[ y_1, y_3, \ldots, y_{2N-1} \right]}

How many multiplications does it take to compute 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 \mathcal{F}_{2N}} ?

• 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_L = 2K_{L-1} + 2^L}
• 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_L \sim N \, \log{N}}