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

$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}\,{\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}$

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 \approx \frac{\hat{y}_j}{n}}

We claim 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 = \frac{1}{n} \, \sum_{k=0}^{n-1} \hat{y}_k \, \omega^{j\,k}}

Lemma. 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 1 + z + z^2 + \dots + z^{n-1} = \begin{cases} n & z = 1 \\ \frac{z^n-1}{z-1} & z \ne 1 \end{cases}}

Proof.

quod erat demonstrandum

Let 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 = \mathrm{e}^{\frac{2\pi\,i\,\ell}{n}}} .

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 \ell \ne 0} , then 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 \ne 1} .

Hence 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{e}^{\frac{2\pi\,i\,\ell}{n}} = 1} if and only if $\ell$ is a multiple 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 n}

but in the range 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[ -(n-1), n-1 \right]} , only 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 \ell = 0} is a multiple 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 n} .

Therefore 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 \sum_{k=0}^{n-1} \left( \mathrm{e}^{ \frac{2\pi\,i\,\ell}{n}} \right)^k = \begin{cases} n & \ell = 0 \\ 0 & \ell \ne 0 \end{cases}}

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

Proof. Let 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 = \frac{1}{n} \, \sum_{k=0}^{n-1} \hat{y}_k \, \omega^{j\,k} } (don't know it's equal to 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} , but we'll show it.)

Put in 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{y}_k = \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j\,k}}

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} 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 \ne 1\end{pmatrix} \\ &= \frac{1}{n} \, n \, y_j \\ &= y_j \end{align}}

BUT $z=\mathrm {e} ^{\frac {2\pi \,i\,(\ell -j)}{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 -(n-1) \le \ell-j \le n-1}

Therefore 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 = 0} 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 \ne \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

$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}}