= Random Fourier features
{c}
{wiki}
= Random Fourier feature
{c}
{synonym}
<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 map>
$$
z(x)=\sqrt{\frac2m}\big(\cos(\omega_1\cdot x+b_1),\ldots,\cos(\omega_m\cdot x+b_m)\big).
$$
Averaging the product of two cosines over $b_j$ leaves one half of $\cos(\omega_j\cdot(x-y))$, so $\mathbb E[z(x)^Tz(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>.<Random Features for Large-Scale Kernel Machines by Ali Rahimi and Benjamin Recht>[§3, random Fourier features]{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.
Back to article page
