RandomFourierFeatures

Random Fourier Features is a technique used in machine learning to approximate shift‑invariant kernel functions, most notably the Gaussian kernel, by mapping input data into a randomized low‑dimensional feature space. The method, introduced by Rahimi and Recht, relies on Bochner’s theorem, which states that any positive‑definite, shift‑invariant kernel can be expressed as the Fourier transform of a probability distribution. By sampling random frequencies from this distribution and applying sinusoidal transformations, the mapping yields explicit features that can be fed into linear models. In practice, one generates a weight matrix of random frequencies drawn from a normal distribution scaled by the kernel’s bandwidth, multiplies it with the input vector, applies cosine and sine functions, and scales the result. This random projection approximates the kernel's inner product with high probability, enabling efficient training of models that would otherwise require an expensive kernel matrix.

The key advantages of Random Fourier Features are computational speed and memory efficiency. Training time scales linearly with the number of features and the number of samples, avoiding the cubic scaling of traditional kernel methods. The approach also permits the use of stochastic gradient descent and online learning techniques. However, the approximation introduces variance that depends on the number of random features; using more features reduces error but increases computation. Additionally, the method is limited to shift‑invariant kernels and may underperform when the target function exhibits non‑stationary behavior. Despite these limitations, Random Fourier Features remain popular in large‑scale kernel learning, approximate Gaussian process regression, and as a building block in deep learning architectures such as random feature neural networks.