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 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 2} : 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 = 2^{L}} 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 L \in \mathbb{Z}^+} . (In practice, 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 n = 2N} , 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 = 2^{L-1}} ).
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}_{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{align}}
In the even case,
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} \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{align}}
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 W = \mathrm{e}^{ \frac{2\pi\,i}{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 \begin{align} \mathrm{e}^{-\frac{2\pi\,i}{2N} \cdot 2\ell\,k} &= \overline{W}^{\ell\,k} \end{align}}
In the odd case,
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} \overline{\omega}^{(2\ell+1) \, k} &= \overline{\omega}^k \, \overline{\omega}^{2\ell\,k} \\ &= \overline{\omega}^k \, \overline{W}^{\ell\,k} \end{align}}
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}_{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 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} 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})}