Innuo

The NIPS paper Random Fourier Features for Large-scale Kernel Machines , by Rahimi and Recht presents a method for randomized feature mapping where dot products in the transformed feature space approximate (a certain class of) positive definite (p.d.) kernels in the original space. We know that for any p.d. kernel there exists a deterministic map that has the aforementioned property but it may be infinite dimensional. The paper presents results indicating that with the randomized map we  can get away with only a "small" number of features (at least for a classification setting). Before applying the method to density estimation let us review the relevant section of the paper briefly. Bochner's Theorem and Random Fourier Features Assume that we have data in $R^d$ and a continuous p.d. kernel $K(x,y)$ defined for every pair of points $x,y \in R^d$. Assume further that the kernel is shift-invariant, i.e., $K(x,y) = K(x-y) \triangleq K(\delta)$ and that the kernel is...