SOURCE-LINKED INTELLIGENCE

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

arXiv · AI, language, vision and robotics · article · Sep 14, 2026 · UTC

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more gener

Read original source ↗ Open in workspace

recordType

paper

region

Global