Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
Abstract
The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(ε−2log n) dimensions preserves pairwise squared distances within relative error ε 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 Id), we diagonalize this operator in closed form. For fixed k with m,d−m→∞, its kth singular value satisfies ℓk≈(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→∞ and m/d→0, the expected Kendall correlation is 2/π√(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≪ m≪ 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.
Related
- Stable and efficient covariance estimation for sample L-moments using Hájek projections
- The 2-Norm Distance on the Reflexive Lattice Generated by a Double Triangle Lattice of Projections
- Tests for Categorical Data Beyond Pearson: A Distance Covariance and Energy Distance Approach
- High-Dimensional Two-Sample Covariance Testing with Null-Preserving Transformations
- Repairing covariance functions on metric trees through a Hausdorff-type distance
BibTeX
@misc{sao2026exact,
title = {{Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models}},
author = {Piyush Sao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02155},
eprint = {2609.02155},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02155},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
AU - Piyush Sao
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02155
UR - https://arxiv.org/abs/2609.02155
AB - The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(ε^−2log n) dimensions preserves pairwise squared distances within relative error ε 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→∞, its kth singular value satisfies ℓ_k≈(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→∞ and m/d→0, the expected Kendall correlation is 2/π√(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≪ m≪ 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.
ER -