Before revision: We show how to obliviously embed into the reproducing kernel Hilbert spaceassociated with Gaussian kernels, so that distance in this space (the kernel distance) only has (1+\varepsilon)-relative error . This only holds in comparing any point sets at a kernel distance at least \alpha ; this parameter only shows up as a poly-logarithmic factor of the dimension of an intermediate embedding, but not in the final embedding. The main insight is to effectively modify the well-traveled random Fourier features to be slightly biased and have higher variance, but so they can be defined as a convolution over the function space. This result provides the first guaranteed algorithmic results for LSH of kernel distance on point sets and low-dimensional shapes and distributions, and for relative error bounds on the kernel two-sample test .
After revision: We show how to obliviously embed into the reproducing kernel Hilbert spaceassociated with Gaussian kernels, so that distance in this space (the kernel distance) only has (1+\varepsilon)-relative error , but with a small additive \alpha term. In the first variants the dependence on 1/\alpha is logarithmic, but has a separate exponential dependence on the original dimension d. In the second variant, the dependence on 1/\alpha is still sub-polynomial, but the dependence on d is linear .