= Benjamin Recht
{c}
<Benjamin Recht> coauthored the 2007 <Random Fourier feature> construction with <Ali Rahimi>. Randomly sampled features approximate a shift-invariant <positive-definite kernel> by ordinary <inner product>[inner products], permitting a linear learning method to approximate a <kernel method> without storing the whole <Gram matrix>[pairwise kernel matrix].<Random Features for Large-Scale Kernel Machines by Ali Rahimi and Benjamin Recht>[§3]{ref}
For suitable normalized <positive-semidefinite kernel>[kernels], features $z_j(x)=\sqrt{2/D}\cos(\omega_j^Tx+b_j)$ use <frequency>[frequencies] sampled from the <positive-semidefinite kernel>[kernel]'s spectral distribution and uniform phases. Their expected <inner product> recovers the <positive-semidefinite kernel>[kernel]; finitely many features introduce an <approximation error>. The number of features controls a computational and statistical tradeoff rather than an exact identity for every finite sample.
Back to article page
