Random Fourier Features for the Gaussian Kernel: Exact Variance Formulas for the Two Standard Feature Maps, Why Their Difference Vanishes for Distant Points, and a Test on 9,568 Power-Plant Records

Random Fourier features approximate a shift-invariant kernel by an inner product of D random cosine features, which turns kernel ridge regression into linear ridge regression. Two feature maps are in common use: √(2/D) cos(wᵀx+b) with a random phase, and paired cos and sin features with D/2 frequencies. For the Gaussian kernel I derive the exact variance of each kernel estimate at a fixed budget of D real features: (1−k²+k⁴/2)/D for the phase map and (1−k²)²/D for the paired map, where k is the true kernel value. The paired map is never worse, and the gap k²(1−k²/2)/D is large for nearby points but disappears as k → 0. A Monte Carlo check with 20,000 draws matches both formulas at five distances. On the UCI combined-cycle power-plant data (9,568 hourly records), the chosen kernel is narrow: 92.3% of point pairs have k<0.1. As predicted, the two maps then give the same kernel-matrix error (predicted ratio 1.005, observed 0.980 to 1.018 across seven values of D), and that error falls as D^(−1/2), with error ×√D between 9.05 and 9.38. Exact kernel ridge regression on 7,654 training points gives a test RMSE of 3.752 MW against 4.589 MW for linear regression. With 4,000 random features the RMSE is 3.860 to 3.867 MW, 2.9% to 3.1% above the exact fit.