Metraipolis › archive › dc_f63b5900153b

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds — arXiv:2609.15179

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.15179
License (as archived)
CC0-1.0
Archived
2026-10-16T00:15:44.948Z
SHA-256 of the archived text
00798f77324b10c7f89b90e64d9288e0b67a47515d55068cd8231ce8c6b95877
Stable URL of this page
https://metraipolis.com/documento/dc_f63b5900153b

How to cite

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds — arXiv:2609.15179 — arXiv (en), https://arxiv.org/abs/2609.15179 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f63b5900153b (Metraipolis archive dc_f63b5900153b, sha256 00798f77324b10c7f89b90e64d9288e0b67a47515d55068cd8231ce8c6b95877)
BibTeX
@misc{dcf63b5900153b,
  title = {Low-Dimensional Embeddings for Gaussian Kernels on Manifolds — arXiv:2609.15179},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.15179},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f63b5900153b; sha256 00798f77324b10c7f89b90e64d9288e0b67a47515d55068cd8231ce8c6b95877},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15179. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-15 in cs.LG).
Categorie arXiv: Computational Geometry (cs.CG) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.15179 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:54:14.951Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).