216. Fourier

A frequency-domain representation of a time series. Decompose the series into a sum of sines and cosines at different frequencies. Useful for finding dominant cycles that aren’t obvious in the time-domain view.

216.0.1. Discrete Fourier Transform (DFT)

For a series ${𝑦}_0,{𝑦}_1,\dots ,{𝑦}_{𝑁-1}$ of length $𝑁$:

The output ${𝑌}_{𝑘}$ is a complex number. Its magnitude $|{𝑌}_{𝑘}|$ measures how much the frequency $𝑘/𝑁$ (cycles per time unit) is present in the signal. The phase $arg\left({𝑌}_{𝑘}\right)$ tells you where the cycle peaks.

The inverse DFT recovers the original series:

216.0.2. Frequencies and periods

For a series sampled at one observation per unit time, the DFT covers frequencies $𝑘/𝑁$ for $𝑘=0,1,\dots ,𝑁-1$:

• $𝑘=0$: DC component (mean of the series)
• $𝑘=1$: one cycle over the entire window — period $𝑁$
• $𝑘=2$: two cycles over the window — period $𝑁/2$
• …
• $𝑘=𝑁/2$: Nyquist frequency — period 2 (highest detectable cycle)
• $𝑘>𝑁/2$: redundant (mirror of lower frequencies; this is aliasing)

So you only look at the first $𝑁/2$ frequencies for a real-valued series. The period corresponding to bin $𝑘$ is $𝑁/𝑘$.

216.0.3. FFT — the fast version

The Fast Fourier Transform (Cooley-Tukey 1965) computes the DFT in $𝑂\left(𝑁log𝑁\right)$ rather than the naive $𝑂\left({𝑁}^2\right)$. It’s the standard implementation in every numerical library (NumPy fft.fft, MATLAB fft, etc.).

Use FFT in practice; conceptually it computes exactly the DFT above.

216.0.4. What you can do with the Fourier transform

216.0.4.1. 1. Find dominant cycles

Plot $|{𝑌}_{𝑘}{|}^2$ (the power spectrum) vs frequency. Peaks indicate dominant cycles. Example uses:

• Found a peak at $𝑘=12$ in 144 months of data → period 12 → annual cycle.
• Found a peak at $𝑘=1$ in 365 days → period 365 → annual cycle (in daily data).
• Multiple peaks → multiple seasonalities (e.g., daily data has both weekly and yearly peaks).

This is the core of [periodogram.typ](periodogram.typ).

216.0.4.2. 2. Filter (frequency-domain)

Remove specific frequencies:

• Low-pass filter: keep low frequencies, drop high → smooths the series.
• High-pass filter: keep high, drop low → removes trend, isolates noise/cycles.
• Band-pass filter: keep a specific range → isolate one cycle.

Procedure: FFT → zero out unwanted frequency bins → inverse FFT.

216.0.4.3. 3. Forecast with Fourier features

Add sin(2 pi k t \/ m) and cos(2 pi k t \/ m) as regressors in a linear forecasting model, where $𝑚$ is the period. A handful of harmonics ($𝑘=1,2,3$) captures most of a smooth seasonal pattern.

This is how Prophet (Facebook) and many modern forecasting libraries handle seasonality without a fixed seasonal index.

216.0.4.4. 4. Spectral density estimation

Smoothed version of the periodogram → see [periodogram.typ](periodogram.typ).

216.0.5. Limitations

• Stationarity assumption: standard FFT assumes the series is stationary. For series with changing frequency content (e.g., a chirp), use short-time Fourier transform (STFT) or wavelets.
• Boundary effects: a finite series treated as periodic introduces artifacts at the edges. Apply a windowing function (Hann, Hamming) before FFT to reduce these.
• Resolution: frequency resolution is $1/𝑁$ — you can only distinguish cycles at multiples of this. Low frequencies need long series.

216.0.6. Connection to seasonality

If your series has a known seasonal period $𝑚$, you’d expect a peak in the spectrum at $𝑘=𝑁/𝑚$. Conversely, unknown periodicities are discovered via the spectrum — perhaps weekly + monthly + yearly all show up in the same series. Fourier analysis is the natural tool for this.

import numpy as np
Y = np.fft.fft(y)
power = np.abs(Y[:N//2])**2  # only first half (positive frequencies)
freq = np.arange(N//2) / N    # cycles per month
period = 1 / np.where(freq > 0, freq, np.inf)  # months per cycle