Principle:Dotnet Machinelearning Fast Fourier Transform
| Knowledge Sources | |
|---|---|
| Domains | Signal Processing, Time Series Analysis, Mathematics |
| Last Updated | 2026-02-09 12:00 GMT |
Overview
The Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) in O(n log n) time instead of O(n^2), enabling efficient frequency-domain analysis of time series data for ML.NET's Singular Spectrum Analysis (SSA) forecasting and seasonality detection.
Description
The Discrete Fourier Transform converts a time-domain signal of n samples into its frequency-domain representation, revealing the amplitude and phase of each frequency component present in the signal. The naive DFT computation requires O(n^2) complex multiplications, which becomes prohibitively expensive for signals longer than a few thousand samples.
The FFT exploits the symmetry and periodicity of the complex exponential basis functions (the twiddle factors) to decompose the DFT into a recursive structure of smaller DFTs. The most common variant, the Cooley-Tukey radix-2 algorithm, splits an n-point DFT into two n/2-point DFTs, combines the results with O(n) multiplications, and recurses. This yields an overall complexity of O(n log n).
Intel MKL's DFTI (Discrete Fourier Transform Interface) provides highly optimized FFT implementations that:
- Automatically select the best algorithm variant (radix-2, radix-4, split-radix, Bluestein) based on the transform size
- Use SIMD vectorization for the butterfly operations
- Optimize memory access patterns for cache locality
- Support both in-place and out-of-place computation
- Handle arbitrary transform sizes (not limited to powers of 2)
Usage
In ML.NET, FFT is used for:
- Singular Spectrum Analysis (SSA) forecasting: The trajectory matrix eigendecomposition involves computing autocovariance, which is efficiently performed via FFT-based circular convolution
- Seasonality detection: The power spectrum (squared magnitude of the FFT) reveals periodic components as peaks at specific frequencies
- Signal denoising: Low-pass filtering in the frequency domain removes high-frequency noise before forecasting
Theoretical Basis
Discrete Fourier Transform
For a sequence of n complex numbers x[0], x[1], ..., x[n-1], the DFT produces a sequence X[0], X[1], ..., X[n-1] defined by:
X[k] = SUM_{j=0}^{n-1} x[j] * exp(-2 * pi * i * j * k / n) for k = 0, 1, ..., n-1
where i is the imaginary unit. Each X[k] represents the amplitude and phase of the frequency component at frequency k/n cycles per sample.
The inverse DFT recovers the original signal:
x[j] = (1/n) * SUM_{k=0}^{n-1} X[k] * exp(2 * pi * i * j * k / n) for j = 0, 1, ..., n-1
Cooley-Tukey Decomposition
Let W_n = exp(-2 * pi * i / n) be the primitive n-th root of unity. The DFT can be written as:
X[k] = SUM_{j=0}^{n-1} x[j] * W_n^{jk}
When n is even, split into even-indexed and odd-indexed terms:
X[k] = SUM_{m=0}^{n/2-1} x[2m] * W_n^{2mk} + W_n^k * SUM_{m=0}^{n/2-1} x[2m+1] * W_n^{2mk}
Since W_n^{2mk} = W_{n/2}^{mk}, this becomes:
X[k] = E[k] + W_n^k * O[k]
where E and O are n/2-point DFTs of the even and odd subsequences. The key insight is that both E and O are periodic with period n/2, so:
X[k + n/2] = E[k] - W_n^k * O[k]
This butterfly operation combines two half-size DFTs into the full DFT with only n/2 complex multiplications per recursion level, and there are log_2(n) levels.
Complexity Analysis
The recurrence relation for the number of operations is:
T(n) = 2 * T(n/2) + O(n)
By the Master Theorem, this resolves to T(n) = O(n log n). For a signal of 1,000,000 samples, the FFT requires approximately 20,000,000 operations compared to 1,000,000,000,000 for the naive DFT -- a speedup factor of 50,000.
Application to SSA Forecasting
Singular Spectrum Analysis constructs a trajectory matrix from a time series by embedding the series into a matrix of lagged windows. The eigendecomposition of this matrix's autocovariance requires computing:
C[tau] = SUM_{t=0}^{N-tau-1} x[t] * x[t + tau]
for all lags tau. This is a cross-correlation, which can be computed as:
- Compute X = FFT(x)
- Compute S = X * conj(X) (element-wise)
- Compute C = IFFT(S) (inverse FFT)
This yields all N autocovariance values in O(N log N) time instead of O(N^2).
Split-Complex vs. Interleaved Format
MKL's DFTI supports two storage formats for complex data:
- Interleaved: Real and imaginary parts alternate in a single array: [Re0, Im0, Re1, Im1, ...]
- Split-complex: Real and imaginary parts are stored in separate arrays: Re = [Re0, Re1, ...], Im = [Im0, Im1, ...]
The ML.NET MKL proxy uses split-complex format because it simplifies P/Invoke marshalling (two float arrays instead of one interleaved buffer that requires custom struct marshalling) and allows independent processing of real and imaginary components.