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 products, permitting a linear learning method to approximate a kernel method without storing the whole pairwise kernel matrix.[ref]
For suitable normalized kernels, features use frequencies sampled from the kernel's spectral distribution and uniform phases. Their expected inner product recovers the 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.
New to topics? Read the docs here!