Gaussian kernel distances preserved with low-dimensional random features
Low-Dimensional Embeddings for Gaussian Kernels on Manifolds
Computational GeometryMachine Learning
Summary
Calculating how similar lots of points are using Gaussian kernels can take a long time, especially when the data lives in a high-dimensional space. The authors extend previous work by showing that if the points come from a lower-dimensional curved space (a manifold), then a small number of random features can still approximate all similarities accurately. Their new math proves this works efficiently even when considering the shape and size of the curved space, not just its dimension. They also show that certain topological properties of the data remain stable after this transformation.
What this means in practice
- •For machine learning engineers: Improve scalability of kernel-based methods on data with low-dimensional manifold structure by using fewer random features without losing accuracy.
- •For computational topology teams: Preserve topological features of data during dimensionality reduction using random features, enabling efficient shape analysis.
A theory result. No direct application yet.
Authors
Soumik Dutta, Kunal Dutta
Abstract
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 general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.