 Random Fourier features

Random Fourier features approximate a continuous translation-invariant positive-semidefinite kernel $k(x,y)=\kappa (x-y)$ on ${\mathbb{R}}^d$ with $\kappa (0)=1$. Its spectral probability distribution gives frequencies $\omega$ satisfying $\kappa (x-y)=\mathbb{E}\cos (\omega \cdot (x-y))$.

Draw $m$ independent and identically distributed random variables ${\omega }_j$ from this distribution and independent $b_j$ from the continuous uniform distribution on $[0,2\pi ]$. Define the feature mapAveraging the product of two cosines over $b_j$ leaves one half of $\cos ({\omega }_j\cdot (x-y))$, so $\mathbb{E}[z(x{)}^{T}z(y)]=k(x,y)$. Every realized approximate kernel matrix is positive semidefinite because it is a Gram matrix. Increasing $m$ averages more sampled features; it does not make the finite approximation identically equal to the original positive-semidefinite kernel.^[ref]

For a positive-semidefinite kernel with positive diagonal constant $\kappa (0)=c$, normalize by $c$ and multiply $z$ by $\sqrt{c}$. The identically zero case needs no random features.