MATH 414 Lecture 22

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

Discrete Fourier Transform

Find / approximate

Failed to parse (unknown function "\k"): {\displaystyle c_k = \frac{1}{2\pi} \, \int_{0}^{2\pi} f(t) \, \mathrm{e}^{-i \, \k \, t} \,\mathrm{d}t}

given

$y_j=f\left(\frac{2\pi j}{n}\right)$

where $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\stackrel{jk}{\bar{\omega }}$, where $\omega ={\mathrm{e}}^{\frac{2\pi i}{n}}$

${\hat{y}}_k:=\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{\omega }}$

$c_k\approx \frac{{\hat{y}}_j}{n}$

We claim $y_j=\frac{1}{n}\sum _{k=0}^{n-1}{\hat{y}}_k{\omega }^{jk}$

Lemma. $1+z+z^2+\dots +z^{n-1}=\{\begin{array}{ll}n& z=1\\ \frac{z^n-1}{z-1}& z\ne 1\end{array}$

Proof.

quod erat demonstrandum

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

If $\ell \ne 0$, then $z\ne 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 $[-(n-1),n-1]$, 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{array}{ll}n& \ell =0\\ 0& \ell \ne 0\end{array}$

Theorem. $y_j=\frac{1}{n}\sum _{k=0}^{n-1}{\hat{y}}_k{\omega }^{jk}$

Proof. Let $Y_j=\frac{1}{n}\sum _{k=0}^{n-1}{\hat{y}}_k{\omega }^{jk}$ (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\stackrel{jk}{\bar{\omega }}$

$\begin{array}{rl}{Y}_j& =\frac{1}{n}\sum _{k=0}^{n-1}\left(\sum _{\ell =0}^{n-1}{y}_{\ell }\stackrel{\ell k}{\bar{\omega }}\right){\omega }^{jk}\\ & =\frac{1}{n}\sum _{\ell =0}^{n-1}{y}_{\ell }\left(\sum _{k=0}^{n-1}\stackrel{\ell k}{\bar{\omega }}{\omega }^{jk}\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 }\left(\begin{array}{cc}n& z=1\\ 0& z\ne 1\end{array}\right)\\ & =\frac{1}{n}n{y}_j\\ & =y_j\end{array}$

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

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

Therefore $z=0$ if $j\ne \ell$ and $z=1$ if $j=\ell$.

quod erat demonstrandum

$S_n$ is a $n$-periodic sequence: $y\in S_n$ implies $y_j=y_{j+n}$