The RBF kernel exp(−‖x − x′‖2/(2σ2)) is the average of cos(ωT(x − x′)) over random frequencies ω ~ N(0, I/σ2), so M = 2T features [sin(Ωx), cos(Ωx)]/√T (17.59)–(17.60) give an unbiased estimate of it whose error shrinks like 1/√M. Top: ridge regression on the random features (red) against exact kernel ridge regression (white) on the noisy sinc data. Bottom left: the estimated kernel k̂(x, 0) against the exact one, with the exact ±2 standard deviation band. Bottom right: the relative Gram-matrix error against M for i.i.d., orthogonal and positive features on a cloud of 50 points in D dimensions.
Data: 100 points of sinc(x) = sin(πx)/(πx) plus N(0, 0.12) noise on [−1.5, 1.5] (the data of Figure 17.22). Both fits use the ridge penalty λ = 0.01 and no bias; the random-feature fit is computed in its dual form Φ*ΦT(ΦΦT + λI)−1y, equal to the primal ridge fit by the push-through identity (17.102). Orthogonal features draw D × D blocks of orthonormal directions with chi-distributed lengths; in one dimension they have the same law as i.i.d. features. Positive features use exp(−‖x‖2/σ2) exp(Ωx)/√M, the version that estimates the RBF kernel (see the notes on (17.61)). The cloud: 50 points 0.35 N(0, I), bandwidth 1, five draws averaged per point.
code/ch17_kernel_methods.py (rff_omega, random_features, rff_variance, krr_fit, fig_17_S1).