魏智德-On The Relative Error of Random Fourier...

The method of random Fourier features (RFF), proposed in a seminal result by Rahimi and Recht (NIPS’07), is a powerful technique to find approximate low dimensional representations of points in (high-dimensional) kernel space, for shift-invariant kernels. While RFF has been analyzed under various notions of error guarantee, the ability to preserve the kernel distance with relative error is less un