The GaussianSketch for Almost Relative Error Kernel Distance

Abstract

We introduce two versions of a new sketch for approximately embedding the Gaussian kernel into Euclidean inner product space. These work by truncating infinite expansions of the Gaussian kernel, and carefully invoking the RecursiveTensorSketch [Ahle et al. SODA 2020]. After providing concentration and approximation properties of these sketches, we use them to approximate the kernel distance between points sets. These sketches yield almost $(1+\epsilon )$-relative error, but with a small additive $\alpha$ term. In the first variants the dependence on $1/\alpha$ is poly-logarithmic, but has higher degree of polynomial dependence on the original dimension $d$. In the second variant, the dependence on $1/\alpha$ is still poly-logarithmic, but the dependence on $d$ is linear.

References in corpus (10)

• Equivalence of distance-based and RKHS-based statistics in hypothesis testing
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• A Gentle Introduction to the Kernel Distance
• On the optimal estimation of probability measures in weak and strong topologies
• Locality-sensitive hashing of curves
• B-tests: Low Variance Kernel Two-Sample Tests
• Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off
• Relative Error Embeddings for the Gaussian Kernel Distance
• Comparing Distributions and Shapes using the Kernel Distance