FFT¶

The Fast Fourier Transform (FFT) is an algorithm designed to compute the Discrete Fourier Transform (DFT) much more efficiently than the direct method. While the DFT requires $O(N^2)$ operations for $N$ data points, the FFT reduces this computational complexity to $O(N*\log(N)$, making it significantly faster, especially for large datasets. This speed-up is achieved by exploiting symmetries in the DFT calculation, breaking the problem into smaller, manageable parts, and reusing previously computed results. The result is a dramatic reduction in computation time, which has made the FFT essential for applications in signal processing, image analysis, and many other fields requiring fast frequency analysis.

Mathematical defintion¶

The discrete Fourier transform (DFT) takes a sequence of $N$ equally-spaced samples $x_n$ and computes $N$ equally-spaced complex coefficients $X_k$ in the frequency domain. The interval between each frequency bin is simply the sampling frequency divided by the number of samples. The modulus of each complex coefficient $|X_k|$ gives the amplitude spectrum while the argument $\arg(X_k)$ gives the phase of each frequency component.

The inverse discrete Fourier Transform (IDFT), as its name suggests, operates the inverse operation: it takes the complex coefficients in the frequency domain and gives $N$ equally-spaced samples in the dual space.

The finition of the DFT is given by

$$ X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi \frac{k}{N} n}, $$

where $\{x_n\} := x_0, x_1, \ldots, x_{N-1}$ is the vector for which we want to calculate the DFT. This vector can contain complex numbers or a real signal (e.g., audio signals, time series measurements, etc.). The set $\{X_k\} := X_0, X_1, \ldots, X_{N-1}$ is the corresponding complex sequence in the dual space. The numbers $k$ are called wave numbers or angular wave numbers and are linked to the wavelengths $\lambda$ by the corresponding formula:

$$ k = \frac{2\pi}{\lambda} $$

The symbol $\mathcal{F}$ is often used to simplify the notation, so that the DFT is simply noted $X=\mathcal{F}\{x\}$.

The inverse discrete Fourier Transform (IDFT) is given by the following formula,

$$ x_n=\frac{1}{N}\sum^{N-1}_{k=0}X_k\cdot e^{i2\pi\frac{k}{N}n}, $$

and it can be simplified by the notation $\mathcal{F}^{-1}$, so that the IDFT is written $x=\mathcal{F}^{-1}\{X\}$.

Normalization¶

Common normalization factors for the DFT and IDFT can be $1$ and $1/N$, like what we have written above, or $1/\sqrt{N}$ for both. This is so that the FDT and IDFT are unitary, and the application of the IDFT after the DFT does not modify the amplitude of the original signal:

$$ x=\mathcal{F}^{-1}\{\mathcal{F}\{x\}\} $$

But for analysis purposes, other normalization choices can be made. In the case of real valued signals or real valued time series, because the DFT spreads half of the energy symmetrically on the negative frequency domain, it can be handy to use $2/N$ as a normalization factor for the DFT so that the amplitude spectrum $|X_k|$ reflects the amplitude of each sinusoidal component of the signal. And because the DC component of the signal ($k=0$) is unique, we can even go further and scale it individually by $1/N$:

$$ X_k = a_k \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi \frac{k}{N} n}, \quad a_k = \begin{cases} \frac{1}{N} & k = 0 \\ \frac{2}{N} & \forall k > 0 \end{cases} $$

The DC component is then equal to the arithmetic mean of the signal.

It must be noted that if this normalization choice is convenient, it breaks the unitarity of the DFT and IDFT.

Nyquist Frequency¶

Here we show the symmetric property of the DFT around the Nyquist frequency with a simple sine wave at 20Hz with a sampling frequency of 200Hz. The Nyquist frequency is equal to half the sampling frequency, and for real valued signals we can observe a symmetrical spectrum above it.