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

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(varepsilon-2log 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 (Sigma=σ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 frac2π√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 nll mll 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.