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 ${\hat {f}}$ is a subset of $\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 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 V_{j-1}} is given by

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 \mathrm{proj}_{V_{j-1}}{(f_j)} = \sum_{k=-\infty}^{\infty} a_k^{j-1} \, \phi(2^{j-1} \, x - k)}

Prove that 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 a_k^{j-1} = \frac{1}{2} \, \left( a_{2k}^j + a_{2k+1}^j \right)} .

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} 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 - 2 k) + \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{align}}

Fast Fourier Transform

Given data 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 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}}