CS Paper Radar

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

Soumik Dutta, Kunal Dutta

cs.CG cs.LG ·submitted 2026-09-14 08:00 UTC · v1
theory

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.

Comment
57 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

cs.LG cs.ITmath.NAmath.PR+1 ·2026-09-02 ·Piyush Sao
code/data similarity 0.72
Abstract · 41 pages, 6 figures, 4 tables. Reproducibility code: https://github.com/piyush314/random-projection-geometry (pinned as a submodule). Compan…

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to $m=O(\varepsilon^{-2}\log n)$ dimensions preserves pairwise squared distances within relative error $\varepsilon$ with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature $f(D)$ of a squared distance $D$ from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data ($Σ=σ^2 I_d$), we diagonalize this operator in closed form. For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(m/ d)^{k/2}$. This yields three sharp consequences. A rank-$m$ sketch retains at most an $m/d$ fraction of the variance of any feature of one squared distance. If $m\to\infty$ and $m/d\to0$, the expected Kendall correlation is $\frac{2}π\sqrt{m/d}(1+o(1))$; for fixed $q$, nearest- neighbor agreement tends to $1/q$. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when $\log n\ll m\ll d$. After removing scale, Haar-averaged retained covariance-shape information is $(m/d)^2$. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

0.38

Gaussian Approximation of Besov Functions for Logistic Classification on Manifolds

cs.LG stat.MLmath.ST ·2026-10-19 ·Guanhang Lei, Lei Shi, Xiaoming Yuan
similarity 0.68
Abstract

We study Gaussian kernel approximation and regularized logistic classification on a connected compact smooth embedded manifold $X\subset\mathbb R^d$ without boundary and of intrinsic dimension $\varrho$. Two main challenges are to derive a fast oracle inequality without assuming a bounded Bayes function and to construct Gaussian approximants that exploit both the intrinsic dimension and the target's regularity without saturation. We address the first challenge through a Bernstein-type inequality whose constant depends linearly on the supremum norm of the predictor. Combined with localized complexity estimates, this yields an oracle inequality over separable normed function spaces. To address the second challenge, we establish a uniform Sobolev operator expansion and cancel its lower-order bias terms using a signed combination of Gaussian kernel integral operators at different bandwidths. Real interpolation then gives an $L_2(X)$ approximation error of order $γ^α$ for functions in $B^α_{2,\infty}(X)$, where $γ$ is the bandwidth. By constructing the approximants directly on the manifold without ambient extension, we obtain a squared Gaussian RKHS norm bound of order $γ^{-\varrho}$. This construction thus overcomes second-order saturation while retaining norm control governed by the intrinsic dimension. When the marginal distribution has a density $g\in L_p(X)$, these results yield the logistic excess-risk rate $\bigl((\log n)^{\varrho+1}/n\bigr)^{4α(1-1/p)/(4α(1-1/p)+3\varrho)}$. We further show that clipping predictions yields the faster clipped logistic excess-risk rate $\bigl((\log n)^{\varrho+2}/n\bigr)^{2α(1-1/p)/(2α(1-1/p)+\varrho)}$. For bounded densities, its polynomial exponent matches that of the minimax optimal rate for squared-loss regression, and its corresponding excess misclassification risk also matches the minimax optimal rate.

0.49

Random Fourier Features in Near-Linear Time

cs.LG cs.DS ·2026-10-10 ·Sepideh Mahabadi, Sandeep Silwal, Tal Wagner
similarity 0.67
Abstract

Random Fourier features approximate a shift-invariant kernel in $\mathbb{R}^d$, such as the Gaussian kernel $\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 $m$ such features requires $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)$ 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.

0.15

A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings

cs.LG stat.MLmath.PR ·2026-09-16 ·Marcus M. Noack, Maher B. Alghalayini, Mark D. Risser
similarity 0.66
Abstract

Kernel methods, and Gaussian Processes (GPs) in particular, require a Hilbertian distance measure---one whose square is conditionally negative definite (CND)---to guarantee positive semi-definiteness (PSD) of the kernel matrix; a condition that fails for many natural input spaces, including smooth manifolds and spaces of probability distributions. We propose the Sparse Landmark Embedding (SLE) kernel, which eliminates this requirement entirely. Each input is embedded into a sparse feature vector via compactly supported bump functions centered at all |D| training points; applying any standard PSD kernel in this embedding space yields a kernel that is provably PSD for arbitrary distance measures. The compact support automatically controls embedding sparsity, keeping kernel matrices well-conditioned and computationally tractable despite the high ambient dimension. We provide theoretical guarantees on PSD, sparsity, stability, and universal approximation, and show that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification using geodesic and Wasserstein distances.

0.18

The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

cs.DS ·2026-09-18 ·Tung Mai, Anup Rao
theory similarity 0.65
Abstract

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.

0.36

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

cs.CG cs.DSmath.MGmath.PR ·2026-08-13 ·Vishesh Jain
theory similarity 0.64
Abstract · 13 pages; comments welcome!

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ Θ\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.

0.10

Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces

cs.CG math.MG ·2026-10-16 ·Nikita Muravya, Aleksandr Bespalov, Anna Vozianova
theory similarity 0.64
Abstract

A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4/5<\varepsilon<1$, dimension $O((N/k)\log N+kρ_k^4\log N/(\varepsilon-4/5)^2)$ suffices, where $ρ_k$ is the largest ratio, over all points, between the distance to the $k$th closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in $[1,Φ]$, where $Φ\ge5$ is fixed, the worst-case dimension is $Θ(N)$ for $0<\varepsilon<4/5$, lies between $Ω(\sqrt N)$ and $O(\sqrt N\log N)$ for $4/5<\varepsilon<12/13$, and is $Θ(\log N)$ for $\varepsilon>(Φ^2-1)/(Φ^2+1)$. For $Φ>5$, an intermediate range remains without matching bounds. Sign-pattern counting yields the $Ω(\sqrt N)$ lower bound for $4/5<\varepsilon<12/13$, while Hadamard matrices give explicit linear lower bounds for $\varepsilon<4/5$ via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains $N-1$ for every $\varepsilon<1$. Finally, for every fixed $0<\varepsilon<3/5$, we show that the quadratic dependence on the parameter $C$ in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.

0.22

Streaming Algorithms for Gaussian Kernel Density Statistics

cs.DS ·2026-09-09 ·Qin Zhang
similarity 0.63
Abstract · 37 pages

Motivated by data produced by generative systems, \cite{LZ26b} formulates similarity-aware statistics via a weighted similarity graph, replacing equality with similarity in classical frequency-based statistics. Although this framework captures semantic relationships between nonidentical items, under general similarity functions even coarse one-pass approximation can require linear space. We therefore ask whether the geometric structure present in natural vector similarities can overcome this barrier. We answer this question affirmatively for the Gaussian kernel. For fixed-dimensional Euclidean vector streams, we study similarity-aware analogues of classical frequency statistics, including the number of distinct elements and frequency moments, through the diversity index and Gaussian density moments. We give one-pass sublinear-space approximation algorithms that exploit the geometric and analytic properties of the Gaussian kernel, and complement them with lower bounds. Our results show that geometric structure can fundamentally change the streaming complexity of similarity-aware statistical analysis.

0.20