What is Random Fourier Features?
Random Fourier Features (RFF) are randomized explicit feature maps whose inner products approximate a shift-invariant positive-definite kernel by Monte Carlo sampling from its spectral distribution.
Quick Facts
| Created | Introduced by Ali Rahimi and Benjamin Recht in 2007 |
|---|---|
| Specification | Official Specification |
How It Works
Use Bochner's theorem to build explicit features
Bochner's theorem represents a continuous shift-invariant positive-definite kernel as the Fourier transform of a nonnegative measure. Sampling frequencies omega from the normalized spectral measure and phases b uniformly yields features such as z_j(x) = sqrt(2/D) cos(omega_j^T x + b_j).
The original Random Features paper gives convergence bounds for radial kernels. For k(x,y) = exp(-gamma ||x-y||^2), frequencies are Gaussian with coordinate variance 2 gamma; confusing gamma, length scale, and standard deviation changes the represented kernel.
Trade kernel-matrix cost for feature dimension
With D random features and input width d, transforming n dense samples costs roughly O(ndD) and stores a d by D map plus transformed rows. A linear learner can then use streaming, mini-batches, and ordinary inference on unseen samples without retaining all training points.
A larger D usually reduces Monte Carlo kernel error but increases compute and memory. The useful value depends on data geometry, regularization, and the downstream objective; validating only average pairwise error can hide failures on rare classes or decision-boundary pairs.
Version the random map as part of the model
Training and inference must use identical sampled frequencies, phases, feature ordering, input normalization, and kernel parameters. Store them with the model artifact; a seed alone may not reproduce values across random-number generators, language runtimes, or library versions.
Compare RFF with the exact kernel on a representative subset and with other approximations such as Nyström sampling. Report kernel error, task quality, latency, memory, seed variability, and drift behavior. RFF does not directly cover every non-stationary, string, graph, or learned kernel.
Key Characteristics
- Produces explicit finite-dimensional features for shift-invariant kernels
- Samples frequencies from the kernel's spectral distribution
- Replaces an all-pairs kernel matrix with a reusable randomized map
- Trades feature dimension and compute against Monte Carlo approximation error
- Supports new samples when the fitted random map is frozen
- Requires versioned preprocessing, kernel parameters, weights, phases, and seed
Common Use Cases
- Scaling RBF-kernel classification or regression with linear solvers
- Approximating kernel similarities in streaming or online systems
- Reducing MMD or HSIC computation with audited explicit features
- Creating nonlinear features for large tabular or signal datasets
- Benchmarking kernel approximation quality against exact and Nyström baselines
Example
Loading code...Frequently Asked Questions
What kernel do Random Fourier Features approximate?
Classical RFF approximates continuous shift-invariant positive-definite kernels. The frequency distribution must match the target kernel's spectral measure; Gaussian frequencies with the correct variance produce the usual RBF-kernel map.
How many Random Fourier Features are enough?
There is no universal count. Increase the dimension until kernel error and downstream metrics stabilize on representative validation slices, while measuring latency and memory. Repeat across seeds because one random map can hide substantial variance.
How are Random Fourier Features different from Random Projection?
Random Projection approximately preserves geometry of the observed vectors under a projection distribution. RFF samples a kernel's spectral measure so feature inner products approximate that specific shift-invariant kernel. Their guarantees and tuning targets differ.
Can Random Fourier Features transform unseen samples?
Yes, if inference reuses the exact fitted frequencies, phases, preprocessing, and kernel parameters. Resampling features creates a different coordinate system and invalidates model weights trained on the previous map.
Are Random Fourier Features always faster than exact kernels?
No. Small datasets, low query volume, large feature counts, expensive input dimensions, or optimized exact solvers can reverse the tradeoff. Benchmark end-to-end training, inference, memory, and accepted task quality.