PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Piyush Sao

arXiv:2609.02155v1cs.LGcs.ITmath.NAmath.PRmath.ST

TL;DR

The paper asks whether JL guarantees capture the geometry needed for distance recovery, neighbor comparison, and covariance inference when high-dimensional distances concentrate. It introduces conditional-expectation decoding and analyzes its singular values for Gaussian sketches, finding that JL compliance can coexist with weak or absent task-relevant information. The resulting laws quantify how compression affects these different geometric targets.

  • Problem

    Concentrated high-dimensional distances are dominated by a baseline, so the JL bound may not certify the smaller fluctuations that determine comparisons or departures from sphericity.

  • Method

    The paper models recovery of squared-distance features from linear sketches using the optimal conditional-expectation decoder and analyzes the resulting operator for Gaussian data.

  • Results

    JL compliance does not force data-dependent geometry: an independent replacement map can satisfy the bound, while distance variance, ranking correlation, and covariance-shape retention follow distinct compression scales.

  • Takeaways & Limitations

    The rank ratio m/d provides a quantitative scale for compression, reranking, metric correction, and the use of additional independent sketches in the Gaussian benchmark.

  • Takeaways & Limitations

    The fixed-q ranking law does not resolve growing-neighborhood statistics, which require theory for shared-query dependence and non-Gaussian score limits.

Abstract

from arXiv · show

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.

1. Introduction

The paper argues that JL distance preservation can be too coarse to certify task-relevant geometry in concentrated high-dimensional data, and develops recovery limits based on explicit decoding. It shows that even an independent replacement map can satisfy the JL bound, while distance, ranking, and shape information obey distinct compression laws.

  • Motivation: m = O(ε^-2 log n) preserves every pairwise squared distance within relative error ε, but concentration makes this guarantee insensitive to smaller distance fluctuations.The baseline dominates pairwise distances, while centered fluctuations carry comparative geometry.
  • Recovery framework: The paper models feature recovery through an explicit conditional-expectation decoder, whose singular values quantify how much of a squared-distance feature survives a rank-m sketch.This operator-based formulation separates retained information from the JL pairwise-error certificate.
  • Recovery targets: The paper studies three distinct recovery targets—distance values, nearest-neighbor rankings, and covariance shape—rather than treating geometry as a single quantity.The resulting Gaussian limits use different scales for variance, sign correlation, and diffuse shape.
  • The scale problem: ε E D can exceed sd(D), so the JL bound may hold without certifying which of two distances is smaller.Resolving typical fluctuations requires ε comparable to the inverse square root of the effective squared-eigenvalue rank; in isotropic data this leads to m = O(d log n).
  • Conclusion: The JL certificate and retained information are separate: rankings can lose correlation and replacement outputs can be independent even when the bound holds.The paper uses these results to motivate quantitative decisions about compression, reranking, metric correction, and additional sketches.

4. Recovery as an Operator Problem

The paper reframes geometric recovery as an operator problem: conditional expectation is the optimal decoder, and the resulting operator quantifies which distance features survive a linear sketch. For isotropic Gaussian data, rotational invariance and independence reduce the full sketch to a scalar observed energy channel.

  • Motivation: The JL bound can hold even when mapped points contain no information about the original geometry.An independent replacement cloud has zero recoverable variance for every feature, whereas a linear sketch yields nonzero recovery.
  • Recovery formulation: Conditional expectation is the optimal squared-error decoder for any square-integrable feature of a squared distance.It orthogonally projects the feature onto functions of the sketch and separates recovered variance from residual variance.
  • Recovery formulation: The recovery operator maps centered distance features to their conditional expectations given the centered sketch, and its operator norm bounds recoverable variance.The norm also equals squared HGR maximal correlation, while the singular system resolves recovery feature by feature.
  • Gaussian channel: For isotropic covariance, row orthonormalization reduces a rank-r sketch to projection onto an r-dimensional subspace, whose law depends only on r.The Gaussian midpoint and orthogonal components are independent, so the conditional law of the distance given the full sketch depends only on the retained energy U.
  • Gaussian channel: The squared distance channel is D = 2σ2T with T = U + V, where U and V are independent gamma components and U/T is beta distributed.Given U, the rest of the sketch provides no further information about D.
  • Recovery laws: Distance-value recovery has variance scale m/d, neighbor sign statistics inherit correlation scale sqrt(m/d), and diffuse covariance shape contracts at order (m/d)2.These are distinct recovery quantities despite sharing the rank ratio as their governing parameter.

5. Exact Solution of the Gaussian Distance Operator

The Gaussian distance operator has an exact spectral solution based on the beta–gamma channel and generalized Laguerre functions. Its maximal correlation and singular spectrum impose sharp limits on distance-feature recovery, while mutual information and rescaling clarify other aspects of retained geometry.

  • 5.1 The operator norm: r/d is the operator norm and maximal correlation for any rank-r linear observation of the isotropic Gaussian distance.Ordinary linear correlation already attains this value, so nonlinear transformations cannot improve it.
  • 5.1 The operator norm: A rank-r sketch retains at most an r/d fraction of the variance of every square-integrable feature of one squared distance.This ceiling applies to thresholds, quantiles, clipped distances, and other scalar features.
  • 5.2 The Laguerre spectrum: The singular system consists of generalized Laguerre functions, with each mode representing an increasingly nonlinear fluctuation component of the total energy.The first nonconstant mode is centered total energy; advancing from mode k to k + 1 incurs an additional factor of approximately sqrt(r/d).
  • 5.3 Mutual information: The mutual information between the Gaussian distance and its sketch satisfies I(D; O) = r/(2d) + O(r2/d2 + 1/d) when r/d → 0.More generally, the exact expression is obtained from gamma entropies when r/d → α < 1 and d − r → ∞.
  • 5.3 Distance identities: Rescaling a projected distance preserves the common baseline but gives fluctuation noise of relative order r−1/2 instead of d−1/2.Thus baseline-relative distance preservation need not preserve the finer fluctuation scale used for comparisons.
  • 5.3 Distance identities: The JL event is compatible with maximal dependence and with zero dependence between a distance and the observed output.This separates the JL guarantee from the amount or mode of geometry recoverable by a decoder.

6. Distance Recovery Beyond Isotropy

Beyond isotropy, distance-value recovery remains governed by retained squared covariance directions, while nonlinear feature recovery can exceed that limit under unequal spectral retention. Balanced projections reconcile the two quantities, and flat spectra recover the isotropic identity.

  • Anisotropy: Under anisotropy, αm(Σ) and ρ²HGR(D; O) can differ because nonlinear features may exploit unequal retention across independent spectral blocks.Observing one block completely while discarding another permits nonlinear reweighting of block contributions.
  • Distance-value recovery: αm(Σ) is the largest fraction of Var(D) recoverable by a rank-m map, attained by retaining the top-m eigenspace of Σ.The conditional-expectation decoder attains the corresponding mean-square bound.
  • Nonlinear excess: A two-dimensional construction demonstrates that HGR(D; O) can exceed αm(Σ), so distance-value limits do not universally bound every nonlinear feature.The example uses quadratic features with a reported linear correlation of 4/5 ≈ 0.8944.
  • Balanced regime: Equal fractional retention across spectral blocks eliminates nonlinear excess, although unequal eigenvalues alone do not force it.Witsenhausen tensorization supplies the upper bound, while a centered linear witness attains it in the balanced regime.
  • Flat spectrum: For flat-spectrum covariance Σ = λP, retaining rank s within the support gives ρ²HGR = s/r, and an optimal rank-at-most-m map uses s = min{m, r}.In this setting, ρ²HGR = αm(Σ).

7. Rankings Under Random Projection

Random projections preserve ranking only on a scale set by the rank ratio m/d: pairwise agreement follows a Beta–arcsine law, while fixed-size nearest-neighbor agreement approaches chance under thin projections. A single map can nevertheless satisfy JL while rankings collapse.

  • Ranking scale: m/d is the squared correlation mean between original and projected shared-query distance contrasts.For isotropic Gaussians, the projected contrast is obtained from a rescaled rank-m projector.
  • Pairwise order agreement: 2/π√(m/d)(1+o(1)) is the expected Kendall correlation when m →∞ and m/d →0.The result follows by averaging Sheppard’s sign-agreement formula over the Beta-distributed conditional correlation.
  • Pairwise order agreement: Figure 4 compares the exact Beta–arcsine pairwise-order law, its asymptote, and Monte Carlo simulations at d = 200 with 120,000 samples per marker.The exact law is derived by conditioning on the contrast vector and averaging the Gaussian sign formula.
  • Nearest-neighbor agreement: 1/q is the limiting nearest-neighbor agreement for fixed q when m →∞ and m/d →0.More generally, the expected normalized top-k overlap tends to k/q.
  • JL versus rankings: The JL guarantee does not constrain ranking correlation, despite pairwise distance preservation on the same sample.This establishes coexistence of the JL event and ranking collapse for one projection.
  • JL versus rankings: log n ≪ m ≪ d permits one sampled linear map to satisfy the fixed-ε JL bound while its sample mean Kendall correlation tends to zero.Conditional concentration controls the ranking statistic, while a separate JL event holds with m ≥ Cε^-2 log(n/δ).

8. Covariance-Shape Information

The paper measures local covariance information through Fisher information after removing nuisance scale, finding distinct contraction laws for mean, scale, and diffuse shape under Haar projections.

  • Local information framework: Fisher information quantifies local statistical distinguishability, while efficient information removes variation explained by a nuisance parameter through score-space projection.The shape analysis treats overall log-scale as nuisance and projects it out before measuring covariance-shape information.
  • Mean and scale: m/d is the Haar-averaged retained fraction for mean and log-scale directions.For a scalar mean direction, the retained fraction is Beta-distributed with mean m/d; the log-scale and mean rows are summarized by the same contraction factor.
  • Diffuse shape: Diffuse shape loses information twice because projection discards coordinates and reduces contrast within retained coordinates.The paper connects this mechanism to the quadratic order (m/d)^2 for diffuse covariance shape.
  • Spike exception: A sufficiently large spectral spike can remain visible after compression, so the diffuse-shape rate does not apply to finite-rank spikes without an additional model.The detection threshold depends on the population spectrum, sample size, and statistical task.

9. General Maps: Rank, Spectrum, and Precision

The paper separates rank loss, reversible spectral distortion, and noise instability for known linear maps. Its Gaussian results show that rank limits recovery, while singular values govern unwhitened metrics and noisy inversion.

  • Rank: A fixed rank-r map limits recovery of every squared-distance feature to at most an r/d fraction of its variance.Row orthonormalization reduces the observation to r retained coordinates of a rotated standard Gaussian.
  • Spectrum: An invertible map permits exact distance recovery when the decoder uses (TT⊤)^−1, but the output Euclidean metric can still distort distances.This distinguishes reversibility from direct use of the mapped norm.
  • Spectrum: The unwhitened squared-norm estimate is governed by the nonzero singular-value spectrum through a Kantorovich bound.The relevant spectral range is represented by positive singular-value quantities bounded between minimum and maximum values.
  • Precision: When s_i ≪ ε, the recovered fraction in singular direction i is negligible under additive Gaussian noise, even if the map is invertible.Invertibility alone therefore does not imply stable noisy inversion or metric preservation.
  • Gaussian-map examples: A square i.i.d. Gaussian map has centered-distance correlation tending to 1/2, whereas row orthonormalization restores the Haar value.Figure 6 compares one-stage Haar and i.i.d. Gaussian maps using a chi-square representation at d = 200.

10. Ensembles

The ensemble analysis shows how independent sketches expand recoverable rank and how averaging reduces distortion. Joint decoding reaches a rank-based ceiling, while averaging has an exact finite-dimensional correlation law.

  • Ensemble ceiling: Stacking k sketches produces a map of rank at most p = min{km, d}, so joint recovery cannot exceed the corresponding rank ceiling.For independent Gaussian blocks with the optimal joint decoder, the isotropic ceiling is attained.
  • Averaging decoder: km/(km + d + 2) is the exact correlation law for the averaging decoder’s independent-sketch distance estimate.The d + 2 term is the finite-dimensional correction from the independent multiplicative chi-square fluctuation.
  • Ensemble ceiling: Independent sketches add rank but never exceed the rank-km ceiling.Before km reaches d, additional sketches expand available rank; afterward, they only reduce averaging distortion.
  • Averaging decoder: Simple averaging has the correct scaling and approaches the joint ceiling when km ≪ d or km ≫ d.Its largest constant-factor gap occurs near km ≈ d.
  • Decoder choice: Metric correction or inversion removes reversible spectral distortion and reaches the isotropic ceiling once the stacked rank is sufficient.The paper distinguishes adding rank from reducing distortion through decoding.

11. Numerical Validation

Numerical checks validate the paper’s exact identities, asymptotic limits, and coexistence results, while discussion sections connect them to reranking, compression, and open extensions.

  • JL–Kendall coexistence: At n = 100, d = 8192, m = 1024, and ε = 0.2, 30 of 30 Haar trials, 30 of 30 Gaussian-map trials, and 28 of 30 replacement trials satisfied the JL bound.The experiment tests whether the JL bound distinguishes a shared projection from an independent replacement cloud.
  • Validation checks: Exact-moment and quadrature calculations agree with reference values to displayed precision, while Monte Carlo estimates fall within two standard errors.The validation distinguishes limiting quantities from finite-sample deterministic equivalents.
  • Finite-sample behavior: At m = 20, finite-dimensional nearest-neighbor agreement was 0.137020 versus the Gaussian score limit 0.138325.The m^-1/2 Berry–Esseen remainder can exceed the first-order signal, making finite-dimensional simulation informative.
  • JL–Kendall coexistence: The JL–Kendall coexistence event occurred with empirical frequency 0.990 for maximum sample distortion at most 15% and mean Kendall correlation magnitude at most 0.1.Its Wilson 95% interval was [0.9710, 0.9966].
  • Implications and limits: The practical implications are reranking coarse candidates, aligning compression with the task, and using independent sketches to trade rank against distortion.Transfer beyond exact Gaussian laws requires care; growing neighborhoods, hubness, density estimates, and non-Gaussian universality remain open.

Appendix A. Gaussian Chains and Hard-Edge Precision

The appendix analyzes Gaussian chains and precision limits, separating rank effects, multiplicative norm fluctuations, hard-edge singular values, and additive-noise recovery.

  • Gaussian chains: A single Gaussian stage of width m has finite correlation m/(m + d + 2), while its deterministic equivalent is (1/m + 1/d)^-1.The finite ratio of moments is md/(m + d + 1).
  • Gaussian chains: A square Gaussian stage contributes χ2 norm fluctuations, whereas a square orthogonal stage does not distort Euclidean distance.For L Gaussian stages of width n, r2 ∼ n/(L + 1).
  • Gaussian chains: Concatenating k independent m-row sketches gives 1/r2 ∼ 1/d + 1/(km), so independent sketches increase combined rank up to the ambient dimension.Sequential composition differs from parallel concatenation, and the chain equivalence is specific to the stated Gaussian-stage ensembles.
  • Hard-edge precision: Under additive Gaussian noise with ε ≈ 2^-b, recovering every direction requires b ≳ log2 d, while the average unrecovered fraction is approximately 2^-b.Floating-point roundoff is not itself isotropic additive noise.
  • Moment matching: Exact first-two-moment matching requires m ≥ d/2, and this lower bound is sharp when d is even.The replacement construction at m = d/2 matches both moments exactly.
  • JL versus moments: The replacement map satisfies the JL bound through concentration rather than moment matching, while Chebyshev control alone requires min{m, d} = Ω(n^2/(ε^2δ)).The logarithmic dimension arises from sub-exponential concentration, imposing a different obstruction from exact moment matching.

B.3 Proof of theorem 5.1

The proof reduces isotropic Gaussian distance recovery to a beta–gamma conditional-expectation channel and derives variance, MMSE, and feature-recovery consequences from its operator structure.

  • Channel reduction: After row orthonormalization, the sketch is informationally equivalent to observing U = ||ΠZ||^2 while the full normalized distance is T = ||Z||^2.The residual V = T − U is independent of U, and the full sketch contains no more information about T than U.
  • Recovery limits: The variance fraction recovered from any distance feature is bounded by r/d.The variance and MMSE corollaries follow from the maximal-correlation bound.
  • Operator diagonalization: The recovery operator has generalized Laguerre singular functions with singular values ℓk = [(r/2)k/(d/2)k]1/2.Parseval’s identity yields the corresponding variance decomposition.
  • Recovery limits: For isotropic Gaussian data, Var(E[D | O]) = 8 tr(B^2), where B is the conditional-mean covariance contribution.The corresponding MMSE is Var(D) − Var(E[D | O]).
  • Feature recovery: The same retained-variance ratio applies to the contrast S = a^T b, whose conditional variance is 12 tr(B^2).The independent Gaussian factors remain conditionally independent after observation.

B.7 Proof of theorem 6.3

The proof of theorem 6.3 decomposes anisotropic Gaussian observations into independent spectral blocks and uses beta–gamma channels, tensorization, and ranking limits.

  • Anisotropic recovery: For distance estimation, the blockwise beta–gamma channels have maximal correlations, and tensorization bounds the full observation through the retained block contributions.The sufficient statistics are the projected block energies.
  • Anisotropic recovery: When every block has equal spectral retention ratio θ, the upper and lower recovery bounds coincide.The flat-support case is the one-block specialization.
  • Ranking limits: Kendall correlation equals twice the pairwise sign-agreement probability minus one, and averaging the arcsine law yields the theorem’s correlation scale.Exchangeability converts pairwise sign agreements into expected Kendall τ.
  • Ranking limits: Projected and original rankings are formed from independent score components, with the projected score contributing correlation scale √α.Common shifts do not affect rankings, and the limiting scores are Gaussian mixtures.
  • Nearest-neighbor overlap: For fixed q, top-k overlap follows from a multivariate Berry–Esseen approximation with error Oq(m^-1/2 + r^-1/2).The proof applies the bound separately to the retained and discarded coordinate sums.

B.11 Proof of theorem 8.1

The proof derives recovery limits from Gaussian quadratic-form identities, rank and covariance calculations, and concentration arguments for projected sketches and neighborhoods.

  • Rank and whitening: Whitening reduces the sketch to a row-space projector, giving effective rank r and the corresponding rank-controlled recovery bound.The argument uses the singular value decomposition and Gaussian quadratic-form identities.
  • Single-sketch recovery: m/(m + d + 2) is the stated correlation for a single projected-direction construction.The identity follows from the covariance and variance of Gaussian norms.
  • Effective rank: md/(m + d + 1) is the ratio of expected trace moments, while r2 = (1 + oP(1)) md/(m + d) follows by concentration.For multiple layers, the leading recursion adds 1/nℓ per layer.
  • Ensembles: km/(km + d + 2) is the correlation for stacked independent Gaussian blocks, with rank at most min{km, d}.Dividing by the HGR ceiling min{km, d}/d yields the theorem’s ratio.
  • Neighborhoods: Fixed-q nearest-neighbor overlap is coupled to independent uniform k-subsets, whose expected normalized overlap is k/q.The nonasymptotic coupling decomposes distances into independent coordinate blocks and controls the gap between order statistics.

Appendix D. Classical Deterministic Ordinal-Capacity Bounds

The appendix establishes deterministic limits on how many pairwise-distance orderings low-dimensional Euclidean embeddings can realize, then records related open questions and reproducibility resources.

  • Counting bound: O(n4) degree-two comparison polynomials in mn variables yield an exponential sign-pattern bound on realizable distance orders.Warren’s bound gives exp(O(mn log n)) realizable patterns.
  • Universal realization: n −2 is a universal upper bound for realizing every strict total ordering of pairwise distances.Whether every ordering is realizable in n −3 dimensions remains open after a February 2026 correction.
  • Deterministic capacity: Θ(n) is the maximal AHMS dimension order, although the exact value remains open.The AHMS dimension is the minimum dimension realizing a specified strict distance ordering.
  • Typical orderings: A uniformly random abstract ordering is typically not realizable in low dimension, while the Gaussian-ordering analogue remains conjectural.The counting argument does not apply directly because Gaussian distance orderings are not uniform.
  • Reproducibility: The executable companion provides pinned code, theorem-level checks, reproduction programs, notebooks, and documentation for regenerating reported results.The verification harness combines exact identities, numerical integration, and seeded Monte Carlo experiments.
Loading 2609.02155v1…