cs.LGNov 12, 2026

Helgason-Fourier Random Features for Scalable Hyperbolic Latent Variables

Authors: Koshi Watanabe, Daichi Mochihashi, Hideitsu Hino, Takahiro Ogawa, Miki Haseyama

Organizations: Hokkaido University · The Institute of Statistical Mathematics · Waseda University

Abstract

Hyperbolic geometry is well suited to embedding hierarchical data, capturing tree-like structure faithfully even in the low dimensions where Euclidean dimensionality reduction is severely constrained. We introduce Random Helgason--Fourier Features (RHFF), an explicit finite-dimensional feature map for kernels on hyperbolic space. We characterize the spectral density from which RHFF frequencies are drawn, allowing kernels such as the Matérn family to be specified directly in the frequency domain. We also prove a uniform approximation error bound for RHFF. Building on this representation, we develop a hyperbolic latent variable model called RHFF-LVM, which requires no numerical quadrature, variational bounds or auxiliary variables unlike previous hyperbolic GP-LVMs. Our RHFF-LVM recovers the metric of a synthetic tree more faithfully than all baselines and attains the best mean rank, driven by large gains on tree-structured atlases at Q ⁣= ⁣2Q\!=\!2. Furthermore, it fits 5×1055\times10^{5} points in 505505 seconds, making it the first non-parametric hyperbolic LVM to reach this scale.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 14, 2026

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

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 dd-dimensional Euclidean ball in RN{\mathbb R}^N, t=Ω((d/ε2)log⁡(dR/ε))t=Ω((d/\varepsilon^2)\log(dR/\varepsilon)) features suffice to preserve all pairwise Gaussian kernel distances within a (1±ε)(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 M⊂RN\mathcal M\subset{\mathbb R}^N of intrinsic dimension dd. We show that t=O((d/ε2)log⁡(vol⁡(M)2N2d/(vol⁡(B1d(0))2rch⁡(M)2dε2d+1δ)))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((d2/ε2)(log⁡N+log⁡(1/(εδ))))O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ)))), RFFs suffice, with probability 1−δ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/ε21/\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±ε⋆)(1\pm\varepsilon_\star)-interleaved, where ε⋆\varepsilon_\star accounts for both distance distortion and kernel-weight approximation.
Aug 4, 2026

Random features for Grassmannian kernel approximation with bounded rank-one projections

We propose a family of random feature maps for scalable kernel machines on low-dimensional subspaces, ie on the Grassmannian manifold. Such representations are useful when data classes or clusters are well described by the span of a few samples. Classical Grassmannian kernels, including the projection and Binet-Cauchy kernels, require full Gram matrices, which leads to prohibitive computational and memory costs for large high-dimensional subspace datasets. We address this limitation using random features based on rank-one projections of subspace projection matrices followed by bounded non-linear transforms, either periodic or binary, to control the resulting distributions. We show that inner products in the random feature space approximate well-defined rotation-invariant Grassmannian kernels that depend only on the principal angles between subspaces. When the number of features is sufficiently large relative to the intrinsic subspace dimension, the approximation holds uniformly over all fixed-dimensional subspaces with high probability. For periodic transforms, the approximated kernel has a closed-form expression with tunable behaviour between inverse Binet-Cauchy and Gaussian-type regimes. Binary transforms yield compact one-bit subspace features, although no closed-form kernel is known. Structured rank-one projections based on randomised fast Fourier transforms further reduce computation without sacrificing practical accuracy. Experiments on synthetic data and ETH-80 classification tasks show that these features accurately preserve Grassmannian geometry while reducing computation, memory, and storage. Rank-one embeddings therefore provide a practical and scalable alternative to classical Grassmannian kernels.
Oct 10, 2026

Random Fourier Features in Near-Linear Time

Random Fourier features approximate a shift-invariant kernel in Rd\mathbb{R}^d, such as the Gaussian kernel exp⁡(−12∥x−y∥22)\exp(-\tfrac12\|x-y\|_2^2), using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating mm such features requires O(md)O(md) time. A long line of work on structured random features has accelerated this computation for the Gaussian kernel and other radial kernels, albeit with weaker concentration guarantees. We close this gap by showing a random feature map that can be computed in near-linear time O((d+m)log⁡d)O((d+m)\log d) and yields near-subgaussian concentration. We obtain it through a new and tighter analysis of the Fastfood feature map of Le, Sarlós and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.