Random Fourier Gaussian Features

Worked Example: Finite Approximation

Consider the Gaussian kernel evaluation exp(-(x-y)²/(2ℓ²)) with Length scale ℓ=1, evaluated at points x=0 and y=1. Using a finite number of frequency pairs (m=4) generated by a deterministic seed (Seed=1), we can approximate this kernel value.

1. The exact Gaussian kernel for x=0 and y=1 with ℓ=1 is exp(-1/2) ≈ 0.6065306597126334.
2. For each of the 4 pairs, we draw two standard uniform random variables to generate standard normal Z via the Box-Muller transform: Z = Math.sqrt(-2 * Math.log1p(-u)) * Math.cos(2 * Math.PI * v).
3. We scale each Z by 1/ℓ to get the frequency ω.
4. The feature vectors for x and y are [cos(ωx), sin(ωx)] / √4 and [cos(ωy), sin(ωy)] / √4 respectively across all frequencies.
5. With the exact same sequence of seeded frequencies, the calculated inner product yields approximately 0.5885852002698289.

The approximation relies on the expectation over frequencies; one realization can error negatively or positively. In this particular finite-sample draw, the signed approximation error (inner product minus exact kernel) is roughly -0.0179.

Experiment: Visualizing Kernel Approximation

Open the Random Fourier Gaussian Features module to explore how the finite-sample features approximate the exact Radial Basis Function (RBF) curve.

1. Keep the default Seed at 1, Length scale at 1, Point x at 0, and Point y at 1. Note the mismatch between the amber approximation curve and the blue exact curve.
2. Increase the Frequency pairs to 8. The amber curve more closely hugs the true kernel curve because higher dimensionality reduces the variance of the approximation.
3. Change the Seed to 7 or 42. Notice how the shape of the approximation curve changes randomly with each new set of sampled frequencies, sometimes overestimating and sometimes underestimating the exact kernel at specific points.
4. Adjust the Length scale to 0.5. The kernel curve becomes narrower, and the frequencies adapt accordingly.
5. Set Point x to 0 and Point y to 0. Observe that the exact kernel and approximation are identically 1.0 (with 0 error), as cos(0) = 1.

Limitations and Assumptions

This module demonstrates the unbiased estimator of the Gaussian kernel using Random Fourier Features. However, there are significant practical limitations:

• Finite Sample Variance: The feature inner product is unbiased in expectation, but any single realization (especially with small m) can significantly deviate. It can even yield negative off-diagonal entries, although the entire Gram matrix constructed over a dataset will remain Positive Semi-Definite (PSD).
• Dimensionality Scaling: To achieve tightly bounded errors (often exponentially small with respect to dimensions in theory), one often needs a feature dimension (2m) that is still moderately large, mitigating some scaling benefits if precision is prioritized over memory.
• Fixed Seed and No Training: The visual curve is a single fixed-seed realization. It is an explanatory diagram, not an optimized learned kernel. In practical setups, m represents the scalar feature dimension. Here, the implementation explicitly uses m independently for a 2m total dimension, without random phase addition.

References

The concept and mathematical proofs for accelerating kernel machines via random frequencies are based on the seminal paper by Ali Rahimi and Benjamin Recht.

• Random Features for Large-Scale Kernel Machines (Rahimi & Recht, 2007)— Introduces the "Kitchen Sinks" methodology showing how to use Bochner's theorem to map data to a randomized low-dimensional feature space where standard inner products approximate shift-invariant kernels.