MATH 414 Lecture 25

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

Fast Fourier Transform

Developed by Cooley (CS) and Tukey (STAT/MATH) ca. 1965 at Bell Labs.

Discrete Fourier Transform involves multiplication of 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 \times n} matrix, around 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 4n^2} real multiplications.

DFT for powers of $2$: $n=2^{L}$ for $L\in \mathbb {Z} ^{+}$. (In practice, we have $n=2N$, where $N=2^{L-1}$).

${\begin{aligned}{\mathcal {F}}_{2N}\left[y_{0},\ldots ,y_{2N-1}\right]&=\sum _{j=0}^{2N-1}y_{j}\,{\overline {\omega }}^{j\,k}\\&=\sum _{{\mbox{even}}\ j}y_{j}\,{\overline {\omega }}^{j\,k}+\sum _{{\mbox{odd}}\ j}y_{j}\,{\overline {\omega }}^{j\,k}\\&=\sum _{\ell =0}^{N_{1}}y_{2\ell }\,{\overline {\omega }}^{2\ell \,k}+\sum _{\ell =0}^{N-1}y_{2\ell +1}\,{\overline {\omega }}^{(2\ell +1)\,k}\end{aligned}}$

In the even case,

${\begin{aligned}{\overline {\omega }}^{2\ell \,k}&=\mathrm {e} ^{-{\frac {2\pi \,i}{n}}\cdot 2\ell \,k}\\&=\mathrm {e} ^{-{\frac {2\pi \,i}{2N}}\cdot 2\ell \,k}\\&=\mathrm {e} ^{-{\frac {2\pi \,i}{N}}\,\ell \,k}\end{aligned}}$

Let $W=\mathrm {e} ^{\frac {2\pi \,i}{N}}$. Then

${\begin{aligned}\mathrm {e} ^{-{\frac {2\pi \,i}{2N}}\cdot 2\ell \,k}&={\overline {W}}^{\ell \,k}\end{aligned}}$

In the odd case,

${\begin{aligned}{\overline {\omega }}^{(2\ell +1)\,k}&={\overline {\omega }}^{k}\,{\overline {\omega }}^{2\ell \,k}\\&={\overline {\omega }}^{k}\,{\overline {W}}^{\ell \,k}\end{aligned}}$

Hence

${\mathcal {F}}_{2N}\left[y_{0},\ldots ,y_{2N-1}\right]_{k}={\mathcal {F}}_{N}\left[y_{0},y_{2},y_{4},\ldots ,y_{2N-2}\right]+{\overline {\omega }}^{k}\,{\mathcal {F}}_{N}\left[y_{1},y_{3},y_{5},\ldots ,y_{2N-1}\right]$

Complexity Analysis

Suppose that it takes $K_{L}$ recursive levels 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 F_{2^L}} , 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 L = \log[2]{n}}

We get a recurrence relation

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

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 K \sim L \, 2^{L} \in O(n \log{n})}