Discrete Fourier Transform

Discrete Fourier Transform (DFT)

The discrete Fourier transform decomposes a finite-length time series $x_1,x_2,\dots ,x_n$ into a sum of complex sinusoids at $n$ equally spaced frequencies. Each coefficient $d({\omega }_j)$ in the decomposition tells how strongly the data oscillates at the corresponding frequency, and is computed as the inner product of the data with the sinusoid:
$d({\omega }_j)=\frac{1}{\sqrt{n}}{\sum }_{t=1}^n{x}_t{e}^{-2\pi it{\omega }_j},j=0,1,\dots ,n-1.$
The frequencies ${\omega }_j=j/n$ are called the Fourier frequencies: they are the only frequencies the DFT can resolve from $n$ equally spaced samples. Using Euler’s formula $e^{-i\theta }=\cos \theta -i\sin \theta$, the same coefficient splits into a real and imaginary part:
$d({\omega }_j)=\frac{1}{\sqrt{n}}({\sum }_{t=1}^n{x}_t\cos (2\pi t{\omega }_j)-i{\sum }_{t=1}^n{x}_t\sin (2\pi t{\omega }_j)),$
so each $d({\omega }_j)$ encodes both the amplitude (through its modulus $|d({\omega }_j)|$) and the phase (through its argument $\arg d({\omega }_j)$) of the frequency-${\omega }_j$ component. The squared modulus $|d({\omega }_j){|}^2$ keeps only the amplitude information and gives the periodogram.

For real-valued data, the coefficients satisfy the symmetry $d({\omega }_j)=\overline{d(1-{\omega }_j)}$, so $|d({\omega }_j){|}^2=|d(1-{\omega }_j){|}^2$ and only the frequencies $\omega \in [0,1/2]$ carry independent information; values above $1/2$ are mirror images of values below. The transform is also fully invertible: $x_t=\frac{1}{\sqrt{n}}{\sum }_{j=0}^{n-1}d({\omega }_j)e^{+2\pi it{\omega }_j}$ recovers the original data exactly, so no information is lost in passing to the frequency domain.

Intuition

The DFT projects a finite time series onto a basis of complex sinusoids and reads off how much of each one is present. Each coefficient $d({\omega }_j)$ answers two questions about the frequency ${\omega }_j$ at once: how much of the data oscillates at this rate (the magnitude), and how the oscillations are aligned in time (the phase). Two signals that differ only by a time shift have identical magnitudes at every frequency but different phases, which is why the periodogram, built from magnitudes alone, suffices for power-spectrum analysis but not for reconstruction.

The restriction to the Fourier grid ${\omega }_j=j/n$ is a finite-sample artifact. With $n$ samples, the lowest non-zero frequency the DFT can see is $1/n$ (one full cycle across the entire record), and the highest is $1/2$ (alternating values $+1,-1,+1,\dots$, the Nyquist limit). Frequencies between Fourier grid points are not directly observed and bleed into neighboring bins, the phenomenon known as spectral leakage. A pure sinusoid whose frequency happens to coincide with a Fourier grid point produces a single clean spike; one that falls between points spreads its energy across nearby bins instead.

Properties

(Linearity) The DFT distributes over linear combinations.

For any series $x_t,y_t$ and scalars $a,b$, the DFT satisfies $\widehat{ax+by}=a\hat{x}+b\hat{y}$. This follows directly from the linearity of the sum that defines $d({\omega }_j)$ and means that decomposing a signal into a known component plus a residual decomposes the DFT additively. The same property is the technical reason behind tools like periodogram regression and the additive time-frequency decomposition.

(Parseval’s Identity) Total energy is preserved between the time and frequency domains.

Squaring and summing on either side gives
${\sum }_{t=1}^n{x}_t^2={\sum }_{j=0}^{n-1}|d({\omega }_j){|}^2,$
the discrete analogue of Plancherel’s theorem. The total variance of the data equals the sum of squared moduli across all Fourier frequencies, which justifies interpreting $|d({\omega }_j){|}^2$ as the contribution of frequency ${\omega }_j$ to total power. The periodogram $P({\omega }_j)=(4/n)|d({\omega }_j){|}^2$ is just a rescaled version of this energy decomposition.

(Orthogonality of Sinusoids) Cosines and sines at distinct Fourier frequencies are orthogonal under the discrete inner product.

For $j\ne k$ in $\{1,\dots ,\lfloor n/2\rfloor \}$,
${\sum }_{t=1}^n\cos (2\pi t{\omega }_j)\cos (2\pi t{\omega }_k)={\sum }_{t=1}^n\sin (2\pi t{\omega }_j)\sin (2\pi t{\omega }_k)=0,$
and the cross-terms ${\sum }_t\cos (2\pi t{\omega }_j)\sin (2\pi t{\omega }_k)$ vanish for all $j,k$. The orthogonality is what makes the DFT coefficients independent: estimating the amplitude at one Fourier frequency does not affect the estimates at the others, mirroring the behavior of an orthogonal regression design with sinusoidal predictors.

(Computational Cost) The naive DFT is $O(n^2)$; the FFT brings it down to $O(n\log n)$.

A direct computation of $d({\omega }_j)$ at all $n$ Fourier frequencies requires $n^2$ complex multiplications. The Fast Fourier Transform (FFT) algorithm exploits redundancies in the sinusoidal basis to compute the same set of coefficients in $O(n\log n)$ when $n$ is a power of two (and in close to that for general $n$). The speedup is what makes spectral analysis practical on long records: without it, a length-$10^6$ series would require $10^{12}$ multiplications instead of about $2\times 10^7$. All standard implementations (NumPy fft.fft, R fft, MATLAB fft) use FFT internally.

Examples

DFT of a length-4 series

Compute $d({\omega }_j)$ for $x_1=2,x_2=3,x_3=1,x_4=4$.

Solution ${\omega }_j=0,1/4,1/2,3/4$.

The Fourier frequencies are

For $j=0$: every exponential equals $1$, so $d(0)=\frac{1}{2}(2+3+1+4)=5$, the rescaled sample mean.

For $j=1$: the exponential $e^{-i\pi t/2}$ takes values $-i,-1,i,1$ for $t=1,2,3,4$, giving
$d(1/4)=\frac{1}{2}(2(-i)+3(-1)+1(i)+4(1))=\frac{1}{2}(1-i)=0.5-0.5i.$

For $j=2$: $e^{-i\pi t}$ takes values $-1,1,-1,1$, so $d(1/2)=\frac{1}{2}(-2+3-1+4)=2$.

By the real-data symmetry, $d(3/4)=\overline{d(1/4)}=0.5+0.5i$. The squared moduli are $|d(0){|}^2=25$, $|d(1/4){|}^2=0.5$, $|d(1/2){|}^2=4$, with periodogram values $P(j/n)=(4/n)|d{|}^2=25,0.5,4$ at $j=0,1,2$.

DFT of a pure cosine

For $x_t=\cos (2\pi {\omega }_{0}t)$ with ${\omega }_0=k/n$ on the Fourier grid, where does the energy concentrate?

Solution $\cos \theta =\frac{1}{2}(e^{i\theta }+e^{-i\theta })$, $d({\omega }_j)=\frac{1}{2\sqrt{n}}{\sum }_{t=1}^n(e^{2\pi i({\omega }_0-{\omega }_j)t}+e^{-2\pi i({\omega }_0+{\omega }_j)t}).$ By the orthogonality of sinusoids on the Fourier grid, the first sum equals $n$ when ${\omega }_j={\omega }_0$ and zero otherwise; the second contributes only at ${\omega }_j=-{\omega }_0$, which on the Fourier grid maps to $1-{\omega }_0$. So $d({\omega }_j)=\sqrt{n}/2$ at ${\omega }_j\in \{{\omega }_0,1-{\omega }_0\}$ and zero elsewhere: a clean two-spike signature, no leakage. If ${\omega }_0$ is not on the grid (say ${\omega }_0=(k+0.5)/n$), the energy spreads across neighboring bins instead, and the spike fades into a broader peak. That is leakage.

Using