MATH 414 Lecture 23

« previous | Monday, March 17, 2014 | next »

Discrete Fourier Transform

Recall 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 c_k = \frac{1}{2\pi} \, \int_0^{2\pi} f(t) \, \mathrm{e}^{-i \, k \, t} \,\mathrm{d}t \approx \frac{1}{n} \, \sum_{j=0}^{n-1} f \left( \frac{2\pi}{n} \, j \right) \, \mathrm{e}^{-\frac{2\pi}{n} \, i \, j \, k}}

For simplicity, we write

• 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}{n} \, j \right)}
• $\omega =\mathrm {e} ^{{\frac {2\pi }{n}}\,i}$
• ${\overline {\omega }}=\mathrm {e} ^{-{\frac {2\pi }{n}}\,i}$
• ${\hat {y}}_{k}=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}$ (this is the fourier transform)

Then $c_{k}={\frac {1}{n}}\,{\hat {y}}_{k}$

${\begin{aligned}{\mathcal {F}}_{n}\left[y\right]_{k}&=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}\\{\mathcal {F}}_{n}^{-1}\left[{\hat {y}}\right]_{j}&={\frac {1}{n}}\sum _{k=0}^{n-1}{\hat {y}}_{k}\,\omega ^{j\,k}\end{aligned}}$

Properties

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} \hat{y}_{k+n} &= \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j \, \left( k+n \right)} \\ &= \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j\,k} \, \cancel{\overline{\omega}^{j\,n}} \\ &= \hat{y}_k \end{align}}

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 \hat{y}_{k+n} = \hat{y}_k} 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 \hat{y}_k} is 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. What about 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}

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+n} &= \frac{1}{n} \, \sum_{j=0}^{n-1} \hat{y_k} \, \omega^{k \, \left( j+n \right)} &= y_j \end{align}}

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 y_j} is 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

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 S_n} be the set of all 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 sequences 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 = \left\{ \ldots, x_{-3}, x_{-2}, x_{-1}, x_0, x_1, x_2, x_3, \ldots \right\}} with 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 x_{\ell} = x_{\ell + n}} is an 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.

We take a "template sample" that is 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} "positions" wide. The entire sequence is nothing more than this template repeated indefinitely in ether direction.

... -9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9 ...
...  a  b  c  d  e  a  b  c  d  e  a  b  c  d  e  a  b  c  d ...
...  `-----------'  `-----------'  `-----------'  `--------- ...

Suppose 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 \in S_n} , 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 y_{j+n} = y_j} 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 \hat{y}_{k+n} = \hat{y}_k}

Therefore the discrete fourier transform 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}_n : S_n \to S_n} is linear:

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} \mathcal{F}_n \left[ y + z \right] &= \mathcal{F}_n \left[ y \right] + \mathcal{F}_n \left[ z \right] \\ \mathcal{F}_n \left[ \alpha \, y \right] &= \alpha \, \mathcal{F}_n \left[ y \right] \end{align}}

The inverse discrete fourier transform 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}_n^{-1} \left[ \hat{y} \right]_j} is also linear.

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 \mathcal{F}_n} 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 \mathcal{F}_n^{-1}} are linear transformations from 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} 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 S_n} .

Shifts

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 ( \ldots, y_{-1}, y_0, y_1, y_2, \ldots ) \in S_n} , then 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_j := y_{j+1}} (left translation 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 y} by one unit)

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}_n \left[ z \right]_k = \omega^k \, \mathcal{F} \left[ y \right]_k} (or equivalently 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{z}_k = \omega^k \, \hat{y}_k} .

We saw a similar behavior in continuous fourier transforms: multiplications in the time domain 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} translate to multiplications by a phase change constant in the frequency domain 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}} .

Connection with Fourier Transforms

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

Suppose 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 f(t) = 0} 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 t \not\in \left[ a,b \right]} , 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 f(a) = f(b)} .

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 \hat{f}(\lambda) = \frac{1}{\sqrt{2\pi}} \, \int_{a}^{b} f(t) \, \mathrm{e}^{-i \, \lambda \, t} \,\mathrm{d}t} .

Perform a change of variables. 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 \theta = \frac{2\pi \, (t-a}{b-a}} . 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 \theta(a) = 0} 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 \theta(b) = 2\pi} with 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{d}\theta = \frac{2\pi}{b-a}\,\mathrm{d}t} .

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 \hat{f}(\lambda) = \frac{b-a}{\sqrt{2\pi} \cdot 2\pi} \, \int_{0}^{2\pi} f \left( a + \frac{b-a}{2\pi} \, \theta \right) \, \mathrm{e}^{-i \, \lambda \left( \frac{b-a}{2\pi} \, \theta + a \right)} \,\mathrm{d}\theta}

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 F(\theta) = f \left( a + \frac{b-a}{2\pi} \, \theta \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 \hat{f}(\lambda) = \frac{ \mathrm{e}^{-i\,\lambda\,a}}{\sqrt{2\pi} \cdot 2\pi} \, \left( b-a \right) \, \int_0^{2\pi} F(\theta) \, \mathrm{e}^{-i\,\lambda\,\frac{b-a}{2\pi}\,\theta} \,\mathrm{d}\theta}

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 \eta = \frac{b-a}{2\pi} \, \lambda}

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} \left( \frac{2\pi}{b-a} \, \eta \right) = \mathrm{e}^{-i\,\lambda\,a} \, \left( \frac{b-a}{2\pi} \right) \, \frac{1}{\sqrt{2\pi}} \, \int_{0}^{2\pi} F(\theta) \, \mathrm{e}^{i \, \eta \, \theta} \,\mathrm{d}\theta}

Replace 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 \eta} 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 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 \hat{f} \left( \frac{2\pi}{b-a} \, k \right) = \left( \frac{b-a}{2\pi} \right) \, \frac{1}{\sqrt{2\pi}} \, \int_{0}^{2\pi} F(\theta) \, \mathrm{e}^{i \, k \, \theta} \,\mathrm{d}\theta}

Something is wrong with the following

Observe that the integral factor is the Fourier Series Coefficient. 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 c_k = \hat{f} \left( \frac{2\pi}{b-a} \, k \right)} . We have 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{1}{n} \hat{y}_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} \hat{y}_k = \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j\,k} &= \sum_{j=0}^{n-1} F \left( \frac{2\pi}{n} \, j \right) \, \overline{\omega}^{j\,k} \\ &= \sum_{j=0}^{n-1} f \left( a + \frac{b-a}{2\pi} \cdot \frac{2\pi}{n} \, j \right) \, \overline{\omega}^{j\,k} \\ &= \sum_{j=0}^{n-1} f \left( a + \frac{b-a}{n} \,j \right) \, \overline{\omega}^{j\,k} \\ &= y_j \end{align}}

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 y_j} is a sample 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 f(t)} at 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 t_j = a + \frac{b-a}{n} \, j} . The spacing between samples is 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 T = \frac{b-a}{n}} , and the Nyquist frequency is 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 T^{-1}} .

The professor realized the mistake here and promised to fix it next lecture

After some manipulation, we come up with a function with two parameters:

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 \Delta \lambda = \frac{2\pi}{b-a}} 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 T = \frac{b-a}{n}} .