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(ε⁻² log n) dimensions preserves pairwise squared distances within relative error ε with high probability. This dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline, leaving the key geometric information in the fluctuations around it. When these fluctuations are much smaller than the baseline, the JL bound becomes uninformative about the retained geometry. We prove a stronger separation. An independent Gaussian replacement map assigns each indexed input point an independent Gaussian output. This map can satisfy the JL bound even though its replacement cloud shares no information with the original data. Thus, satisfying the JL bound need not certify retained geometry. We next ask how well any decoder can recover a feature f(D) of a squared distance D from a linear sketch of the data. Under squared-error loss, the conditional expectation is optimal. Recovery therefore becomes a linear operator, and its singular values quantify how much of each feature survives. For isotropic Gaussian data (Σ = σ²I_d), we diagonalize this operator in closed form. For fixed k with m, d − m → ∞, its k-th singular value satisfies ℓ_k ≈ (m/d)^(k/2). We obtain three sharp consequences. A rank-m sketch retains at most an m/d fraction of the variance of any feature of one squared distance. In the thin-compression regime m → ∞ with m/d → 0, the expected Kendall correlation is (2/π)√(m/d)(1 + o(1)). For fixed q, nearest-neighbor agreement tends to chance, 1/q. A single projection can nevertheless satisfy the JL bound while its mean Kendall correlation vanishes when log n ≪ m ≪ d. Covariance shape contracts faster: after removing overall scale, its Haar-averaged retained information is (m/d)². Thus the JL bound does not quantify the geometry available for comparison or inference.