aiqbench analysis
This research advances the efficiency of Gaussian kernel computations by establishing tight bounds for Random Fourier Features on arbitrary submanifolds, significantly reducing dependency on ambient dimension. The work also demonstrates a preservation of topological structures like persistent homology under these embeddings, offering new theoretical guarantees for manifold learning algorithms. By optimizing feature counts while maintaining relative error, this study directly addresses computational bottlenecks in high-dimensional kernel methods used in machine learning pipelines.
Low-Dimensional Embeddings for Gaussian Kernels on Manifolds
arXiv:2609.15179v1 Announce Type: cross 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=\Omega((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}\delta)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilon\delta))))$, RFFs suffice, with probability $1-\delta$, 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.
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=\Omega((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}\delta)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilon\delta))))$, RFFs suffice, with probability $1-\delta$, 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.
Computational Geometry (cs.CG); Machine Learning (cs.LG)
arXiv:2609.15179 [cs.CG]
(or arXiv:2609.15179v1 [cs.CG] for this version)
https://doi.org/10.48550/arXiv.2609.15179 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 291 words
Related coverage
SPHERE-JEPA: Spherical Prediction with Homogeneous Embeddings
arXiv · Oct 6, 2026
Random features for Grassmannian kernel approximation with bounded rank-one projections
arXiv · Aug 6, 2026
Knowledge Manifold: A Riemannian Geometric Framework for Semantic Mapping and Geodesic Analysis of Scientific Literature
arXiv · Jun 12, 2026
Nonlinear Dimensionality Reduction Techniques for Bayesian Optimization
arXiv · Sep 14, 2026