# Discrete Fourier Transform DFT allows changing sequences (images/audio) from spatial/time domain to frequency domain (i.e. the magnitude spectrum) by decomposing the function into a series of sine and cosine functions. $ \begin{aligned} X_{k} &=\sum_{n=0}^{N-1} x_{n} \cdot e^{-\frac{\partial r}{N} \ln } \\ &=\sum_{n=0}^{N-1} x_{n} \cdot\left[\cos \left(\frac{2 \pi}{N} k n\right)-i \cdot \sin \left(\frac{2 \pi}{N} k n\right)\right] \end{aligned} $ The imaginary component allows for incorporating signals with phase shifts. Fourier Transform is equivalent to changing the basis of the function to infinite dimensions of sine and cosine functions, similar to [[Taylor Expansion]] which changes the basis to polynomials. However, Fourier Transform is global whereas Taylor expansion approximates a function around a specific point. ![[DFT.jpg]] ## Fast Fourier Transform (FFT) FFT is a divide and conquer algorithm to compute Discrete Fourier Transform (DFT). If N is the number of dimensions in our input (time steps, sequence length etc.), FFT brings down complexity of computing DFT from $N^2$ to $N\log N$. It was discovered by Cooley and Tukey in 1965. Often hailed as the most important numerical algorithm. We can write DFT as a matrix multiplication. If ${x}=\left[\begin{array}{c}x[0] \\ x[1] \\ \vdots \\ x[N-1]\end{array}\right]$ and ${X}=\left[\begin{array}{c}X[0] \\ X[1] \\ \vdots \\ X[N-1]\end{array}\right]$, then ${X}={W}{x}$ where, ${W}=\left[\begin{array}{cccc}w_N^0 & w_N^0 & \cdots & w_N^0 \\ w_M^0 & w_N^1 & \cdots & w_N^{N-1} \\ \vdots & & & w_N^{(N-1)^2} \\ w_N^0 & w_N^{N-1} & \cdots & w_N^{(N)}\end{array}\right], \quad w_N=e^{\frac{2 \pi i}{N}}$ The FFT algorithm factors $W$ into a product of sparse matrices termed "butterfly matrices" (see [[Butterfly Factorization]]). Take vectors $x$, use [Bit-reversal permutation](https://en.wikipedia.org/wiki/Bit-reversal_permutation) matrix $P$ to create permuted vectors $v$, then multiply with $\log_{2} N$ butterfly matrices to get the final $X$. In other words, FFT decompose the dense $W$ matrix with $N^2$ entries as $ {W}=\left(\prod_{k=1}^{\log _2 N} {B}_k\right) {P} $ where each butterfly matrix has only at max $N$ entries that are not 0 or 1. Therefore FFT has time complexity of $N\log_{2}N$. --- ## References 1. Interpretation of FFT as conversion from "coefficient representation" of polynomials to "value representation" of polynomials: https://www.youtube.com/watch?v=h7apO7q16V0