CS Paper Radar

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

Piyush Sao

cs.LG cs.ITmath.NAmath.PRmath.ST ·submitted 2026-09-02 06:12 UTC · v1
code/data

Abstract

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.

Comment
41 pages, 6 figures, 4 tables. Reproducibility code: https://github.com/piyush314/random-projection-geometry (pinned as a submodule). Companion paper on nearest-neighbor graphs to follow

Closest papers

Nearest neighbours by meaning across the whole index.

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

cs.CG cs.LG ·2026-09-14 ·Soumik Dutta, Kunal Dutta
theory similarity 0.72
Abstract · 57 pages, 3 figures

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.

0.22

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

cs.CG cs.DSmath.MGmath.PR ·2026-08-13 ·Vishesh Jain
theory similarity 0.67
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

Beyond Gaussian Worlds: Latent Geometry Matters for JEPAs

cs.LG ·2026-09-18 ·Léo Nicollier, Enric Meinhardt-Llopis, Marc Pic, Pablo Musé, Gabriele Facciolo
similarity 0.66
Abstract

Recent Joint-Embedding Predictive Architectures (JEPAs) prevent representation collapse by constraining learned representations to follow a prescribed target distribution, such as an isotropic Gaussian or the uniform distribution on a hypersphere. Klindt et al. (2026) showed that, under their Euclidean assumptions, matching a Gaussian target can recover Gaussian latent variables up to a linear transformation, and that the Gaussian is the unique distribution with this guarantee. We extend their analysis to latent variables supported on embedded Riemannian manifolds and derive conditions on the latent geometry and positive-pair dynamics under which alignment and exact distribution matching guarantee linear recovery. In particular, when the latent variables are uniformly distributed on a sphere and the representations are matched to the same spherical distribution, every optimal representation recovers the latent state up to an orthogonal transformation. This shows that Gaussian uniqueness is not a universal property of distribution-matched JEPAs: non-Euclidean latent geometries can admit other linearly recoverable distributions. We further derive an approximate-recovery bound that is strictly tighter for the spherical world than for the Gaussian world. Experiments on Gaussian, spherical, and toroidal latent spaces show that geometrically compatible targets yield better linear recovery when optimization succeeds, whereas mismatched targets distort the latent structure. This advantage persists in high-dimensional Clifford-torus worlds.

0.48

Deterministic Johnson--Lindenstrauss Projections from Pisot $β$-Transformations for Zero-Knowledge Private Routing

cs.IT eess.SP ·2026-08-13 ·I. Dey, I. Cherkaoui
theory similarity 0.65
Abstract

Zero-knowledge (ZK) proofs certify that a message belongs to an allowed semantic class without revealing the message, but the certificate compares a high-dimensional embedding against class centroids, so its cost grows with the embedding dimension $d$. A Johnson--Lindenstrauss (JL) projection lowers $d$ to $m\ll d$ while preserving pairwise distances, yet a random JL matrix must be committed and its sampling proved inside the circuit, which is costly and a leakage risk. We construct a public deterministic projection from the standardized orbit of a Pisot $β$-transformation, analyzed through the spectral gap of the $β$-map, the geometric decay of its correlations, rather than equidistribution. We prove that the induced squared-norm estimator is unbiased up to a term decaying geometrically with a sampling gap, and that its variance is $V_0/m$ with a constant $V_0$ that is dimension-free in experiment and, under one stated concentration hypothesis, in theory. A single public seed preserving all pairwise centroid distances therefore exists and is found by search. Against six standard projections, including the chaotic-sequence matrix of Yu \emph{et al.}, the construction matches statistical quality to within measurement noise, and it is the only one simultaneously free of in-circuit randomness and exactly reproducible in a fixed finite field at a per-step cost $\log_2β$ rather than $2^{k}$.

0.04

Sketching in Regression: Sketchy in Practice?

cs.DS math.STstat.CO ·2026-11-02 ·Somarddha Das, Soupayan Das Gupta, Koustav Goswami
similarity 0.65
Abstract

The Johnson-Lindenstrauss (JL) lemma and its extensions provide tools for solving the $L_2$ regression problem in high-dimensional settings with $n>d$, by transforming a subspace of $\mathbb{R}^{n}$ to a subspace of $\mathbb{R}^{m}$, (where $m<n$) while approximately preserving the norms of elements of the subspace. In this paper, we study the theoretical guarantees made by various JL-based subspace embeddings critically and concretely to gauge their practical applicability. We derive concrete versions of results on subspace embeddings in the literature to establish lower bounds on the reduced dimension as well as to concretely analyze the complexity of the Fast JL, OSNAP Transforms among other embeddings. These analyses suggest that guaranteeing substantial computational savings while maintaining the accuracy of the sketched solution requires data dimensions larger than those typically encountered in practice. We also see that, for practically necessary accuracy requirements or for sparsity requirements for computational gain, existing theoretical guarantees lead to substantially large reduced dimensions. This leads to very stringent data requirements for establishing guarantees of any kind.

0.19

Towards a mathematical theory of superposition

cs.IT stat.MLcs.LGmath.CO ·2026-08-27 ·Michael I. Ivanitskiy, John Jasper, Emily J. King, Dustin G. Mixon
theory similarity 0.65
Abstract

We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector \(x\) of active features is encoded through an overcomplete dictionary \(W\), and feature recovery is performed by applying \(\operatorname{ReLU}(W^\top W x+b)\) with an appropriate bias vector \(b\). We prove several recovery theorems for this model. In the random-support setting, we establish high-probability support recovery for nearly tight, low-coherence dictionaries, with guarantees when the expected sparsity is up to order \(d/\log n\). In the worst-case support setting, we give a sharp and computable criterion for which sparsity levels permit support recovery. We apply this criterion to Gaussian random matrices and equiangular tight frames. For real equiangular tight frames with \(n>d+1\), we determine the exact recovery threshold in terms of the coherence. The proof of this result for real equiangular tight frames relies on a novel characterization---which should be of independent interest to frame theorists---of the distribution of signs in the Gram matrix.

0.47

Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space

cs.CG cs.CCcs.LG ·2026-10-14 ·Ditbul Ban, Younghun Roh, Julian Shun, Vihan Lakshman
similarity 0.64
Abstract · 55 pages

Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions $d \le 3$. In arbitrary dimensions, we give a randomized algorithm that returns a $(1 \pm \varepsilon)$-approximation with probability at least $1-δ$ in time $O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right)$ for $n$ points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless $\mathrm{NP} = \mathrm{RP}$, admit no FPRAS even on this restricted domain.

0.24

Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

cs.LG stat.MLmath.OC ·2026-11-01 ·Anish Senapati, Jose Blanchet
similarity 0.63
Abstract · 37 pages, 4 figures

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the $K$ nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension $d\ge2$. In particular, for $d>4$, the population risk of our modified problem can be shown to have equivalent convergence rates as the original least square convex regression estimator of $\widetilde O(n^{-2/d})$ using neighborhoods sizes (i.e. $K=K_n$) of order $\widetilde O(n^{2(d-1)/(2d-1)})$ for general convex functions and $\widetilde O(n^{(d+1)/(d+2)})$ for strongly convex functions. To corroborate our theory, we implement iterative optimization methods to compare the prediction accuracy of the KNN relaxation with those of the full estimator across synthetic convex benchmarks. Our experiments demonstrate that KNN prediction risk approaches the full-estimator prediction risk at neighborhood sizes matching the theoretical scale.

0.35