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

arXiv:2609.02155 · cs.LG, cs.IT, cs.NA, math.IT, math.NA, math.PR, math.ST, stat.TH · Submitted 2026-09-02 · Read on arXiv

cs.LG, cs.IT, cs.NA, math.IT, math.NA, math.PR, math.ST, stat.TH

Submitted: 2026-09-02

Updated: 2026-09-02

Comments: 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

Code: https://github.com/piyush314/random-projection-geometry

License: http://creativecommons.org/licenses/by/4.0/

The gist: The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(epsilon-2 n) dimensions preserves pairwise squared distances within relative error epsilon with high

Terminology

Abstract

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(epsilon-2 n) dimensions preserves pairwise squared distances within relative error epsilon 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 (Σ=σ squared I d), we diagonalize this operator in closed form. For fixed k with m,d-m to infinity, its k th singular value satisfies k about(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 infinity and m/d to0, the expected Kendall correlation is π 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 n m d. After removing scale, Haar-averaged retained covariance-shape information is (m/d) squared. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

Sources

Related papers