MATH 414 Lecture 22

« previous | Friday, March 7, 2014 | next »

Discrete Fourier Transform

Find / approximate

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 c_k = \frac{1}{2\pi} \, \int_{0}^{2\pi} f(t) \, \mathrm{e}^{-i \, \k \, t} \,\mathrm{d}t}

given

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_j = f \left( \frac{2\pi\,j}{n} \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} is the number of samples, and $f$ is $2\pi$-periodic

Use trapezoial rule:

$c_{k}\approx {\frac {1}{n}}\,\sum _{j=0}^{n-1}y_{i}\,{\overline {\omega }}^{j\,k}$, where $\omega =\mathrm {e} ^{\frac {2\pi \,i}{n}}$

${\hat {y}}_{k}:=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}$

$c_{k}\approx {\frac {{\hat {y}}_{j}}{n}}$

We claim $y_{j}={\frac {1}{n}}\,\sum _{k=0}^{n-1}{\hat {y}}_{k}\,\omega ^{j\,k}$

Lemma. $1+z+z^{2}+\dots +z^{n-1}={\begin{cases}n&z=1\\{\frac {z^{n}-1}{z-1}}&z\neq 1\end{cases}}$

Proof.

quod erat demonstrandum

Let $z=\mathrm {e} ^{\frac {2\pi \,i\,\ell }{n}}$.

If $\ell \neq 0$, then $z\neq 1$.

Hence $\mathrm {e} ^{\frac {2\pi \,i\,\ell }{n}}=1$ if and only if $\ell$ is a multiple of $n$

but in the range $\left[-(n-1),n-1\right]$, only $\ell =0$ is a multiple of $n$.

Therefore $\sum _{k=0}^{n-1}\left(\mathrm {e} ^{\frac {2\pi \,i\,\ell }{n}}\right)^{k}={\begin{cases}n&\ell =0\\0&\ell \neq 0\end{cases}}$

Theorem. $y_{j}={\frac {1}{n}}\,\sum _{k=0}^{n-1}{\hat {y}}_{k}\,\omega ^{j\,k}$

Proof. Let $Y_{j}={\frac {1}{n}}\,\sum _{k=0}^{n-1}{\hat {y}}_{k}\,\omega ^{j\,k}$ (don't know it's equal to $y_{j}$, but we'll show it.)

Put in ${\hat {y}}_{k}=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}$

${\begin{aligned}Y_{j}&={\frac {1}{n}}\,\sum _{k=0}^{n-1}\left(\sum _{\ell =0}^{n-1}y_{\ell }\,{\overline {\omega }}^{\ell \,k}\right)\,\omega ^{j\,k}\\&={\frac {1}{n}}\,\sum _{\ell =0}^{n-1}y_{\ell }\left(\sum _{k=0}^{n-1}{\overline {\omega }}^{\ell \,k}\,\omega ^{j\,k}\right)\\&={\frac {1}{n}}\,\sum _{\ell =0}^{n-1}y_{\ell }\,\sum _{k=0}^{n-1}z^{k}\\&={\frac {1}{n}}\,\sum _{\ell =0}^{n-1}y_{\ell }\,{\begin{pmatrix}n&z=1\\0&z\neq 1\end{pmatrix}}\\&={\frac {1}{n}}\,n\,y_{j}\\&=y_{j}\end{aligned}}$

BUT $z=\mathrm {e} ^{\frac {2\pi \,i\,(\ell -j)}{n}}$

$-(n-1)\leq \ell -j\leq n-1$

Therefore $z=0$ if $j\neq \ell$ and 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 z = 1} if 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 j = \ell} .

quod erat demonstrandum

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 S_n} is a 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} -periodic sequence: 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 \in S_n} implies 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_j = y_{j+n}}