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

# Exact Limits of Random Projections for Preserving Geometry:Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
Source: [https://arxiv.org/html/2609.02155](https://arxiv.org/html/2609.02155)
\\RawFloats

\[figure,table\] Piyush Sao\]saopk@ornl\.gov\\msc60D05; 62H12; 68W20

Piyush Sao[https://orcid.org/0000-0002-9432-5855](https://orcid.org/0000-0002-9432-5855)Affiliation:Computer Science and Mathematics Division, Oak Ridge National Laboratory, Oak Ridge, Tennessee 37830, USAEmail:[\[](mailto:[)

###### Abstract

The Johnson–Lindenstrauss \(JL\) lemma guarantees that a random projection ofnnpoints tom=O⁡\(ε−2​log⁡n\)m=O\(\\varepsilon^\{\-2\}\\log n\)dimensions preserves pairwise squared distances within relative errorε\\varepsilonwith 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 featuref⁡\(D\)f\(D\)of a squared distanceDDfrom 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\\Sigma=\\sigma^\{2\}I\_\{d\}\), we diagonalize this operator in closed form\. For fixedkkwithm,d−m→∞m,d\-m\\to\\infty, itskkth singular value satisfiesℓk≈\(m/d\)k/2\\ell\_\{k\}\\approx\(m/d\)^\{k/2\}\.

This yields three sharp consequences\. A rank\-mmsketch retains at most anm/dm/dfraction of the variance of any feature of one squared distance\. Ifm→∞m\\to\\inftyandm/d→0m/d\\to 0, the expected Kendall correlation is2π​m/d​\(1\+o⁡\(1\)\)\\frac\{2\}\{\\pi\}\\sqrt\{m/d\}\(1\+o\(1\)\); for fixedqq, nearest\-neighbor agreement tends to1/q1/q\. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes whenlog⁡n≪m≪d\\log n\\ll m\\ll d\. After removing scale, Haar\-averaged retained covariance\-shape information is\(m/d\)2\(m/d\)^\{2\}\. Thus JL distance preservation does not quantify the geometry available for comparison or inference\.

###### keywords

random projection; Johnson–Lindenstrauss lemma; distance recovery; nearest\-neighbor ranking; maximal correlation; covariance shape

## 1Introduction

High\-dimensional data pipelines routinely replace raw data with compressed representations\. Approximate\-nearest\-neighbor systems generate candidates in a compressed domain and rerank them with richer codes or full\-precision distances[Johnson et al\., 2021](https://arxiv.org/html/2609.02155#bib.bib47);[Jégou et al\., 2011b](https://arxiv.org/html/2609.02155#bib.bib48)\. Single\-cell methods summarize high\-dimensional measurements in low\-dimensional visualizations, even as benchmarks warn that the recovered orderings can be unstable or distorted[Moon et al\., 2019](https://arxiv.org/html/2609.02155#bib.bib49);[Saelens et al\., 2019](https://arxiv.org/html/2609.02155#bib.bib50);[Chari and Pachter, 2023](https://arxiv.org/html/2609.02155#bib.bib51)\. The decisions this forces on the practitioner—when to rerank, how far to compress, how many independent sketches to draw—are currently made empirically, because available guarantees may not capture the task\-relevant notion of quality, and their worst\-case bounds can be too conservative to guide parameter selection[Martinsson and Tropp, 2020](https://arxiv.org/html/2609.02155#bib.bib20)\. The goal of this paper is to quantify that retained geometry for the random projection, the compressed representation with the strongest formal guarantees[Halko et al\., 2011](https://arxiv.org/html/2609.02155#bib.bib19);[Indyk and Motwani, 1998](https://arxiv.org/html/2609.02155#bib.bib26)\.

The guarantee behind random projection is the Johnson–Lindenstrauss \(JL\) lemma[Johnson and Lindenstrauss, 1984](https://arxiv.org/html/2609.02155#bib.bib1): for finite sets, a suitable map into dimensionm=O⁡\(ε−2​log⁡n\)m=O\(\\varepsilon^\{\-2\}\\log n\)preserves every pairwise squared distance amongnnpoints to relative errorε\\varepsilon\. For an indexed samplex1,…,xnx\_\{1\},\\ldots,x\_\{n\}, we say that a mapTTsatisfies the*ε\\varepsilon\-JL bound*when

\(1−ε\)​‖xi−xj‖2≤‖T⁡\(xi\)−T⁡\(xj\)‖2≤\(1\+ε\)​‖xi−xj‖2for every​i<j\.\(1\-\\varepsilon\)\\left\\lVert x\_\{i\}\-x\_\{j\}\\right\\rVert^\{2\}\\leq\\left\\lVert T\(x\_\{i\}\)\-T\(x\_\{j\}\)\\right\\rVert^\{2\}\\leq\(1\+\\varepsilon\)\\left\\lVert x\_\{i\}\-x\_\{j\}\\right\\rVert^\{2\}\\qquad\\text\{for every \}i<j\.If the sample or map is random, we call the occurrence of this bound the*JL event*\.

For concentrated high\-dimensional data,*concentration of measure*causes the pairwise squared distances controlled by the JL bound to be dominated by a common population mean, which we call the*baseline*\. Consequently, these bounds become less informative about specific pairwise distances, which instead appear as smaller centered*fluctuations*around this baseline\. Downstream tasks depend on this fine scale: which distance is smaller, and how far a point distribution departs from sphericity\. Two questions follow, and the JL bound answers neither\. Does the JL event itself certify that the geometry carrying this fine scale survived the sketch? And how much of the fluctuations can any decoder recover from a rank\-mmsketch?

The structure of prior work indicates why both questions are open\. Lower bounds show that the dimension order in the JL lemma is essentially unimprovable: Alon[Alon, 2003](https://arxiv.org/html/2609.02155#bib.bib17)showed that near\-equidistant point sets already force nearly the same dimension order for every map, linear or not, and Larsen and Nelson[Larsen and Nelson, 2017](https://arxiv.org/html/2609.02155#bib.bib18)sharpened this lower bound to match the JL dimension order for worst\-case constructions\. Because the lemma attains the optimal dimension order for the guarantee it states, the gap cannot be closed by sharpening the lemma itself; informativeness about concentrated data requires a different criterion\. The literature on concentration addresses the original space rather than the sketch: Beyer et al\.[Beyer et al\., 1999](https://arxiv.org/html/2609.02155#bib.bib2)gave a sufficient condition for distance concentration, and the Durrant–Kabán converse[Durrant and Kabán, 2009](https://arxiv.org/html/2609.02155#bib.bib3)established the corresponding necessary condition and identified when nearest neighbors remain meaningful\. A third line characterizes projection outputs: Dasgupta[Dasgupta, 1999](https://arxiv.org/html/2609.02155#bib.bib4);[Dasgupta, 2000](https://arxiv.org/html/2609.02155#bib.bib5)established what we call*Dasgupta’s sphericalization phenomenon*, the rounding of eccentric Gaussian components toward sphericity; Dasgupta, Hsu, and Verma[Dasgupta et al\., 2006](https://arxiv.org/html/2609.02155#bib.bib6)and Diaconis and Freedman[Diaconis and Freedman, 1984](https://arxiv.org/html/2609.02155#bib.bib7)obtained related structural results for broader distributions, including approximation by scale mixtures of spherical Gaussians; and Li and Malik[Li and Malik, 2016](https://arxiv.org/html/2609.02155#bib.bib16)gave order preservation guarantees for fixed vector pairs at prescribed length ratios\. None of these results tests whether JL satisfaction certifies retained geometry, and none quantifies how much distance variation a decoder can recover from a sketch\.

Our approach introduces the missing object: an explicit decoder\. We model recovery as estimation of a feature of a squared distance from the sketch under squared\-error loss\. The optimal estimate is the conditional expectation, so recovery acts as a linear operator, and its singular values measure how much of each feature survives compression\. This formulation yields information limits that the pairwise error criterion of the JL lemma cannot express\. We make three main contributions\. First, we prove that the error allowed by the JL bound can exceed the fluctuation scale of a concentrated Gaussian cloud \([section2](https://arxiv.org/html/2609.02155#S2)\)\. We then show that an independent Gaussian replacement map can satisfy the same bound at the dimension prescribed by the JL lemma even though its replacement cloud is independent of the data \([section3](https://arxiv.org/html/2609.02155#S3)\); satisfying the JL bound therefore need not certify retained geometry\. Second, we identify three recovery targets that the JL bound does not separately control—distance values, neighbor rankings, and covariance shape—and derive their exact Gaussian recovery limits \([sections4](https://arxiv.org/html/2609.02155#S4)to[8](https://arxiv.org/html/2609.02155#S8)\)\. For isotropic distance features, the recoverable variance ceiling ism/dm/d; neighbor rankings vary on the associated correlation scalem/d\\sqrt\{m/d\}; and diffuse covariance shape contracts at order\(m/d\)2\(m/d\)^\{2\}\. Third, for a general known map, we separate what depends on rank, singular spectrum, and numerical precision, then quantify what ensembles of independent sketches can recover \([sections9](https://arxiv.org/html/2609.02155#S9)and[10](https://arxiv.org/html/2609.02155#S10)\)\.

These laws give the practitioner’s empirical decisions a quantitative scale\. Within the Gaussian benchmark, the fraction of distance variance retained, the correlation scale of neighbor rankings, and the contraction of covariance shape are each determined by the ratiom/dm/d, so the cost of compressing farther and the benefit of adding independent sketches can be read off before any experiment\. The replacement\-map result adds a caution that no empirical protocol supplies: a map can satisfy the JL bound while its output is independent of the data\. Beyond the specific Gaussian model, we expect these techniques to extend to other distributions and to more complex features;[section13](https://arxiv.org/html/2609.02155#S13)develops the resulting research directions\. Except where a complete argument appears directly after a statement, proofs are collected in the supplement \([sectionB](https://arxiv.org/html/2609.02155#S2a)\); the discussion following a statement in the text records the mechanism of the proof\.

## 2The Scale Problem: Baseline versus Fluctuations

We begin by quantifying when the relative error allowed by the JL bound is too coarse to resolve distance fluctuations\. LetX,X′​∼i\.i\.d\.​𝒩​\(μ,Σ\)X,X^\{\\prime\}\\overset\{\\text\{i\.i\.d\.\}\}\{\\sim\}\\mathcal\{N\}\(\\mu,\\Sigma\)inℝd\\mathbb\{R\}^\{d\}, where the eigenvalues ofΣ\\Sigmaareλ1≥⋯≥λd≥0\\lambda\_\{1\}\\geq\\cdots\\geq\\lambda\_\{d\}\\geq 0\. LetL:ℝd→ℝmL:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{m\}be any linear map of rank at mostmm, random or deterministic, oblivious orΣ\\Sigma\-aware; no statement below depends on how the map is chosen\. Write

D=‖X−X′‖2,𝒪=\(L​X,L​X′\)D=\\left\\lVert X\-X^\{\\prime\}\\right\\rVert^\{2\},\\qquad\\mathcal\{O\}=\(LX,LX^\{\\prime\}\)for the squared distance and the observed sketch\. WheneverLLis random, we condition on its realization and reveal it to the decoder; equivalently, the information statements below are conditional on the sampled map\. For a queryX0X\_\{0\}and two candidatesX1,X2X\_\{1\},X\_\{2\}, define the*neighbor contrast*

S=‖X0−X1‖2−‖X0−X2‖2\.S=\\left\\lVert X\_\{0\}\-X\_\{1\}\\right\\rVert^\{2\}\-\\left\\lVert X\_\{0\}\-X\_\{2\}\\right\\rVert^\{2\}\.Its sign identifies the nearer candidate, so preserving a two\-candidate ranking is equivalent to preserving the sign ofSS\.

The baseline and the fluctuations appear in the first two moments:

𝔼⁡D=2​tr⁡Σ,Var⁡\(D\)=8​tr⁡\(Σ2\)\.\\E D=2\\tr\\Sigma,\\qquad\\Var\(D\)=8\\tr\(\\Sigma^\{2\}\)\.\(1\)The mean𝔼⁡D\\E Dis the common population*baseline*for i\.i\.d\. pairs, while the centered deviationsD−𝔼⁡DD\-\\E Dare the*fluctuations*that carry comparative geometry\. DiagonalizingΣ\\SigmaexpressesDDas a weighted sum of independent chi\-square variables\. Their variances add, so the fluctuation scale depends on the squared eigenvalues throughtr⁡\(Σ2\)\\tr\(\\Sigma^\{2\}\)\. The relative scale of the fluctuations is

r2​\(Σ\)=\(tr⁡Σ\)2tr⁡\(Σ2\),sd⁡\(D\)𝔼⁡D=2r2​\(Σ\)\.r\_\{2\}\(\\Sigma\)=\\frac\{\(\\tr\\Sigma\)^\{2\}\}\{\\tr\(\\Sigma^\{2\}\)\},\\qquad\\frac\{\\sd\(D\)\}\{\\E D\}=\\sqrt\{\\frac\{2\}\{r\_\{2\}\(\\Sigma\)\}\}\.\(2\)The quantityr2​\(Σ\)r\_\{2\}\(\\Sigma\)is a squared\-trace effective rank: larger values mean tighter relative concentration\. For an isotropic covariance matrix,r2​\(Σ\)=dr\_\{2\}\(\\Sigma\)=d, so relative fluctuations are of orderd−1/2d^\{\-1/2\}[Beyer et al\., 1999](https://arxiv.org/html/2609.02155#bib.bib2)\.

The following proposition states exactly when a relative\-error bound fixes the sign of a comparison\. HereD~1\\widetilde\{D\}\_\{1\}andD~2\\widetilde\{D\}\_\{2\}are any distorted values satisfying the displayed inequalities; later sections reserve the notationD~\\widetilde\{D\}for the squared distance computed from a sketch\.

###### Proposition 2\.1\(When a relative\-error bound preserves order\)\.

Let0<D1<D20<D\_\{1\}<D\_\{2\}, and suppose

\(1−ε\)Dj≤D~j≤\(1\+ε\)Dj,j=1,2\.\(1\-\\varepsilon\)D\_\{j\}\\leq\\widetilde\{D\}\_\{j\}\\leq\(1\+\\varepsilon\)D\_\{j\},\\qquad j=1,2\.These inequalities guaranteeD~1<D~2\\widetilde\{D\}\_\{1\}<\\widetilde\{D\}\_\{2\}for every admissible pair if and only if

D2−D1D1\+D2\>ε\.\\frac\{D\_\{2\}\-D\_\{1\}\}\{D\_\{1\}\+D\_\{2\}\}\>\\varepsilon\.

###### Proof\.

The worst admissible distortions preserve the order exactly when\(1\+ε\)​D1<\(1−ε\)​D2\(1\+\\varepsilon\)D\_\{1\}<\(1\-\\varepsilon\)D\_\{2\}, which is equivalent to the displayed condition; if this inequality fails, the extreme admissible errors reverse or tie the order\. ∎

The neighbor contrast is one such comparison, withDj=‖X0−Xj‖2D\_\{j\}=\\left\\lVert X\_\{0\}\-X\_\{j\}\\right\\rVert^\{2\}: certifying which candidate is nearer is certifying the sign ofS=±\(D2−D1\)S=\\pm\(D\_\{2\}\-D\_\{1\}\)\. Comparisons with smaller margins may survive, but the bound does not guarantee them\.[Section7](https://arxiv.org/html/2609.02155#S7)quantifies their average behavior for the neighbor contrast under random projection\.

The allowed absolute error in a typical squared distance is of orderε​𝔼⁡D\\varepsilon\\E D\. Ifε≫r2\(Σ\)−1/2\\varepsilon\\gg r\_\{2\}\(\\Sigma\)^\{\-1/2\}, this error exceeds the fluctuation scalesd⁡\(D\)\\sd\(D\)\. In this regime, the JL bound can still hold, but it does not by itself certify neighbor comparisons\. If insteadε≍r2\(Σ\)−1/2\\varepsilon\\asymp r\_\{2\}\(\\Sigma\)^\{\-1/2\}, the JL lemma givesm=O⁡\(r2​\(Σ\)​log⁡n\)m=O\(r\_\{2\}\(\\Sigma\)\\log n\)\. For isotropic data, this scales asd​log⁡nd\\log nand therefore no longer guarantees a target dimension belowdd\.

The allowed error can therefore be too large to resolve comparative geometry\. A coarser tolerance still leaves a distinct question: whether passing the test certifies anything about the retained geometry\.

## 3The JL Bound Can Hold without Information

#### Does satisfying the JL bound imply retention of any sample\-specific structure?

[Section2](https://arxiv.org/html/2609.02155#S2)showed that the error allowed by the JL bound can exceed the fluctuation scale\. That observation concerns the tolerance, not the information retained by a particular map: a loose bound may coexist with informative maps\. We therefore ask: does satisfying the JL bound guarantee any sample\-specific structure?

We answer negatively by constructing a map\. An*independent Gaussian replacement map*assigns each indexed input pointXiX\_\{i\}a fresh Gaussian outputYiY\_\{i\}, sampled independently of the data, so thatI⁡\(Xn,Yn\)=0I\(X^\{n\};Y^\{n\}\)=0and no decoder can extract any feature of the input from the output\. Its image is the*replacement cloud*; the shared indices pair each input distance‖Xi−Xj‖\\left\\lVert X\_\{i\}\-X\_\{j\}\\right\\rVertwith the corresponding output distance‖Yi−Yj‖\\left\\lVert Y\_\{i\}\-Y\_\{j\}\\right\\rVert\. The question is whether this zero\-information map can nonetheless satisfy theε\\varepsilon\-JL bound on all\(n2\)\\binom\{n\}\{2\}pairs at the standard JL dimension\.

### 3\.1The independent Gaussian replacement map

###### Proposition 3\.1\(A zero\-information map can satisfy the JL bound\)\.

Letn≥2n\\geq 2,m,d∈ℕm,d\\in\\mathbb\{N\},σ\>0\\sigma\>0, and0<ε,δ<10<\\varepsilon,\\delta<1\. LetX1,…,Xn​∼iid​𝒩​\(μ,σ2​Id\)X\_\{1\},\\dots,X\_\{n\}\\overset\{\\mathrm\{iid\}\}\{\\sim\}\\mathcal\{N\}\(\\mu,\\sigma^\{2\}I\_\{d\}\)andY1,…,Yn​∼iid​𝒩​\(0,σ2​dm​Im\)Y\_\{1\},\\dots,Y\_\{n\}\\overset\{\\mathrm\{iid\}\}\{\\sim\}\\mathcal\{N\}\\\!\\bigl\(0,\\sigma^\{2\}\\tfrac\{d\}\{m\}I\_\{m\}\\bigr\)be independent, and define the index mapTrep​\(Xi\)=YiT\_\{\\mathrm\{rep\}\}\(X\_\{i\}\)=Y\_\{i\}\. Ifmin⁡\{m,d\}≥72​ε−2​log⁡\(4​\(n2\)/δ\)\\min\\\{m,d\\\}\\geq 72\\,\\varepsilon^\{\-2\}\\log\\\!\\bigl\(4\\tbinom\{n\}\{2\}/\\delta\\bigr\), then, with probability at least1−δ1\-\\delta,

\(1−ε\)​‖Xi−Xj‖2≤‖Trep​\(Xi\)−Trep​\(Xj\)‖2≤\(1\+ε\)​‖Xi−Xj‖2for all​i<j\.\(1\-\\varepsilon\)\\left\\lVert X\_\{i\}\-X\_\{j\}\\right\\rVert^\{2\}\\leq\\left\\lVert T\_\{\\mathrm\{rep\}\}\(X\_\{i\}\)\-T\_\{\\mathrm\{rep\}\}\(X\_\{j\}\)\\right\\rVert^\{2\}\\leq\(1\+\\varepsilon\)\\left\\lVert X\_\{i\}\-X\_\{j\}\\right\\rVert^\{2\}\\qquad\\text\{for all \}i<j\.In particular, in the compression regimem≤dm\\leq d,TrepT\_\{\\mathrm\{rep\}\}can satisfy theε\\varepsilon\-JL bound on the sample at the standard JL dimension orderm=O⁡\(ε−2​log⁡\(n/δ\)\)m=O\(\\varepsilon^\{\-2\}\\log\(n/\\delta\)\), while its output carries no information about the data:I⁡\(Xn,Yn\)=0I\(X^\{n\};Y^\{n\}\)=0\.

###### Proof\.

For everyi<ji<j,

‖Xi−Xj‖22​σ2​d​=𝑑​χd2d,‖Yi−Yj‖22​σ2​d​=𝑑​χm2m\.\\frac\{\\left\\lVert X\_\{i\}\-X\_\{j\}\\right\\rVert^\{2\}\}\{2\\sigma^\{2\}d\}\\overset\{d\}\{=\}\\frac\{\\chi^\{2\}\_\{d\}\}\{d\},\\qquad\\frac\{\\left\\lVert Y\_\{i\}\-Y\_\{j\}\\right\\rVert^\{2\}\}\{2\\sigma^\{2\}d\}\\overset\{d\}\{=\}\\frac\{\\chi^\{2\}\_\{m\}\}\{m\}\.Seta=ε/\(2\+ε\)a=\\varepsilon/\(2\+\\varepsilon\)\. The Chernoff bound givesPr\(\|χk2/k−1\|\>a\)≤2e−ka2/8\\Pr\(\\left\|\\chi\_\{k\}^\{2\}/k\-1\\right\|\>a\)\\leq 2e^\{\-ka^\{2\}/8\}\. A union bound over the2​\(n2\)2\\binom\{n\}\{2\}normalized squared distances places all of them in\[1−a,1\+a\]\[1\-a,1\+a\]with probability at least

1−4​\(n2\)​exp⁡\(−min⁡\{m,d\}​a28\)≥1−δ,1\-4\\binom\{n\}\{2\}\\exp\\\!\\left\(\-\\frac\{\\min\\\{m,d\\\}a^\{2\}\}\{8\}\\right\)\\geq 1\-\\delta,where the last inequality follows from the dimension hypothesis and8​\(2\+ε\)2<728\(2\+\\varepsilon\)^\{2\}<72\. On this event, every output\-to\-input ratio lies in

\[1−a1\+a,1\+a1−a\]=\[11\+ε,1\+ε\]⊆\[1−ε,1\+ε\],\\left\[\\frac\{1\-a\}\{1\+a\},\\frac\{1\+a\}\{1\-a\}\\right\]=\\left\[\\frac\{1\}\{1\+\\varepsilon\},1\+\\varepsilon\\right\]\\subseteq\[1\-\\varepsilon,1\+\\varepsilon\],which proves the claim\. ∎

The mechanism is that the JL event factors: input\-cloud concentration and output\-cloud concentration around a shared baseline suffice, and no cross\-conditional structure is needed\. The following remark records the constants and the two\-stage form\.

[Figure1](https://arxiv.org/html/2609.02155#S3.F1)illustrates the separation\. For comparison, we use a rescaled rank\-mmorthogonal projection whose row space is uniformly random \(Haar\-distributed, in the terminology of[section4\.3](https://arxiv.org/html/2609.02155#S4.SS3)\)\.

Figure 1:Satisfying the JL bound does not certify retained information\. Panel \(a\) reports the median maximum relative error over all\(1002\)\\binom\{100\}\{2\}pairs for a rescaled uniformly random rank\-mmorthogonal projection and an independent Gaussian replacement map atd=8192d=8192; bands span the1010th–9090th percentiles over3030trials, and the dashed line marksε=0\.2\\varepsilon=0\.2\. Panels \(b\)–\(c\) show one trial atm/d=1/4m/d=1/4: projected squared distances remain correlated with the original squared\-distance fluctuations, whereas replacement squared distances do not\. The annotated maximum errors show that both displayed maps satisfy the JL bound\.Three natural objections delimit the scope of this separation: what the output actually tells a practitioner, whether the construction depends on population scaling, and whether it requires an oversized dimension\. The same independence gives an exact answer to the first\.

###### Corollary 3\.3\(Ranking consequences of the replacement map\)\.

Under the assumptions of[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1), ifn≥3n\\geq 3, define the mean Kendall statistic for the replacement map by

τ¯nrep=1n​∑i=1n\(n−12\)−1​∑j<kj,k≠isgn⁡\[\(Di​j−Di​k\)​\(Di​jrep−Di​krep\)\]\.\\overline\{\\tau\}\_\{n\}^\{\\mathrm\{rep\}\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\binom\{n\-1\}\{2\}^\{\-1\}\\sum\_\{\\begin\{subarray\}\{c\}j<k\\\\ j,k\\neq i\\end\{subarray\}\}\\operatorname\{sgn\}\\\!\\left\[\(D\_\{ij\}\-D\_\{ik\}\)\(D\_\{ij\}^\{\\mathrm\{rep\}\}\-D\_\{ik\}^\{\\mathrm\{rep\}\}\)\\right\]\.Then

𝔼⁡τ¯nrep=0,Pr⁡\(\|τ¯nrep\|\>t\)≤2​exp⁡\(−⌊n/3⌋​t22\)\.\\E\\overline\{\\tau\}\_\{n\}^\{\\mathrm\{rep\}\}=0,\\qquad\\Pr\\\!\\left\(\\left\|\\overline\{\\tau\}\_\{n\}^\{\\mathrm\{rep\}\}\\right\|\>t\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{\\lfloor n/3\\rfloor t^\{2\}\}\{2\}\\right\)\.In the analogous setting with one query andq≥2q\\geq 2candidates, let𝒩k\\mathcal\{N\}\_\{k\}and𝒩krep\\mathcal\{N\}\_\{k\}^\{\\mathrm\{rep\}\}be the top\-kksets for the original and replacement clouds, respectively, where1≤k<q1\\leq k<q\. Then

𝔼⁡\|𝒩k∩𝒩krep\|k=kq,Pr⁡\(𝒩1=𝒩1rep\)=1q\.\\E\\frac\{\\left\|\\mathcal\{N\}\_\{k\}\\cap\\mathcal\{N\}\_\{k\}^\{\\mathrm\{rep\}\}\\right\|\}\{k\}=\\frac\{k\}\{q\},\\qquad\\Pr\\\!\\left\(\\mathcal\{N\}\_\{1\}=\\mathcal\{N\}\_\{1\}^\{\\mathrm\{rep\}\}\\right\)=\\frac\{1\}\{q\}\.

###### Proof\.

Each Kendall summand is a product of two independent signs\. Exchangeability of the candidate labels makes one sign symmetric, so the kernel has mean zero\. Since\(Xi,Yi\)\(X\_\{i\},Y\_\{i\}\)are i\.i\.d\. pairs acrossii,τ¯nrep\\overline\{\\tau\}\_\{n\}^\{\\mathrm\{rep\}\}is a bounded order\-three U\-statistic\. Hoeffding[Hoeffding, 1963](https://arxiv.org/html/2609.02155#bib.bib40)proved the required blocking inequality; applying it gives the stated tail bound\. The neighbor set from the replacement cloud is a function of that cloud alone; by exchangeability it is a uniformkk\-subset independent of𝒩k\\mathcal\{N\}\_\{k\}\. Ties have probability zero\. ∎

### 3\.2Calibration

#### Empirical calibration\.

Empirical calibration can replace population scaling, which uses knowledge ofσ2\\sigma^\{2\}that a practitioner may not have\. WithD¯X=Np−1​∑i<jDi​j\\overline\{D\}\_\{X\}=N\_\{p\}^\{\-1\}\\sum\_\{i<j\}D\_\{ij\}andD¯rep=Np−1​∑i<jDi​jrep\\overline\{D\}\_\{\\mathrm\{rep\}\}=N\_\{p\}^\{\-1\}\\sum\_\{i<j\}D\_\{ij\}^\{\\mathrm\{rep\}\}, the rescaled cloudYi⋆=\(D¯X/D¯rep\)1/2​YiY\_\{i\}^\{\\star\}=\(\\overline\{D\}\_\{X\}/\\overline\{D\}\_\{\\mathrm\{rep\}\}\)^\{1/2\}Y\_\{i\}matches the realized mean squared distance exactly\. The same proof holds withbε=\(1\+ε−1\)/\(1\+ε\+1\)∼ε/4b\_\{\\varepsilon\}=\(\\sqrt\{1\+\\varepsilon\}\-1\)/\(\\sqrt\{1\+\\varepsilon\}\+1\)\\sim\\varepsilon/4in place ofaεa\_\{\\varepsilon\}, because on the band event both empirical means also lie in the band and the worst ratio is\(\(1\+bε\)/\(1−bε\)\)2=1\+ε\(\(1\+b\_\{\\varepsilon\}\)/\(1\-b\_\{\\varepsilon\}\)\)^\{2\}=1\+\\varepsilon\. Global rescaling preserves all orderings, so the conclusions of[corollary3\.3](https://arxiv.org/html/2609.02155#S3.Thmtheorem3)for rankings and neighborhoods remain exact\. Ifℰε⋆\\mathcal\{E\}\_\{\\varepsilon\}^\{\\star\}denotes the calibrated JL event, then

Pr\(ℰε⋆\)≥1−2Npe−dbε2/8−2Npe−mbε2/8\.\\Pr\(\\mathcal\{E\}\_\{\\varepsilon\}^\{\\star\}\)\\geq 1\-2N\_\{p\}e^\{\-db\_\{\\varepsilon\}^\{2\}/8\}\-2N\_\{p\}e^\{\-mb\_\{\\varepsilon\}^\{2\}/8\}\.The calibrated output is not independent of the input\. Its data\-dependent part is characterized precisely by

Xn⟶D¯X⟶Y⋆n,D¯Y⋆=D¯Xalmost surely\.X^\{n\}\\longrightarrow\\overline\{D\}\_\{X\}\\longrightarrow Y^\{\\star n\},\\qquad\\overline\{D\}\_\{Y^\{\\star\}\}=\\overline\{D\}\_\{X\}\\quad\\text\{almost surely\}\.Thus the conditional law of the output depends onXnX^\{n\}only throughD¯X\\overline\{D\}\_\{X\}, and that statistic is recoverable from the output: empirical calibration leaks exactly one scalar and no ranking information\.

### 3\.3Sharpness

The third objection is that the replacement map might succeed only in a dimension so large that the JL bound becomes trivial to satisfy\. The following proposition rules this out\.

###### Proposition 3\.4\(Sharp dimension order for independent Gaussian replacement maps\)\.

In the setting of[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1), letr=⌊n/2⌋r=\\lfloor n/2\\rfloorand0<ε≤10<\\varepsilon\\leq 1\. There are universal constantsc,C\>0c,C\>0such that

Pr⁡\(ℰεrep\)≤exp⁡\(−c​r​e−C​m​ε2\)\.\\Pr\(\\mathcal\{E\}\_\{\\varepsilon\}^\{\\mathrm\{rep\}\}\)\\leq\\exp\\\!\\left\(\-cre^\{\-Cm\\varepsilon^\{2\}\}\\right\)\.Consequently, ifPr⁡\(ℰεrep\)≥1−δ\\Pr\(\\mathcal\{E\}\_\{\\varepsilon\}^\{\\mathrm\{rep\}\}\)\\geq 1\-\\delta, then

m≥1C​ε2​log⁡\(c​r−log⁡\(1−δ\)\)m\\geq\\frac\{1\}\{C\\varepsilon^\{2\}\}\\log\\\!\\left\(\\frac\{cr\}\{\-\\log\(1\-\\delta\)\}\\right\)whenever the logarithm is positive\. In particular, forδ≤1/2\\delta\\leq 1/2andn/δn/\\deltasufficiently large,m=Ω⁡\(ε−2​log⁡\(n/δ\)\)m=\\Omega\(\\varepsilon^\{\-2\}\\log\(n/\\delta\)\)\.

The proof in[sectionB](https://arxiv.org/html/2609.02155#S2a)uses the i\.i\.d\.Fm,dF\_\{m,d\}ratios associated with disjoint pairs and the Zhang–Zhou lower bound[Zhang and Zhou, 2020](https://arxiv.org/html/2609.02155#bib.bib46), Cor\. 3for the upper chi\-square tail probability\. Together with[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1), this shows that the dimension order prescribed by the JL lemma is both sufficient and necessary for the independent Gaussian replacement map\.

The conclusion is that the certificate and the information are separate objects\. Satisfying the JL bound does not by itself certify retained geometry; what replaces the certificate is the subject of the next section\.

## 4Recovery as an Operator Problem

### 4\.1Sketch, target, and decoder

The JL bound checks if a map preserves original distances within a small relative error\. In contrast, recovery analysis fixes an observation and determines what any decoder can infer from it\.[Section2](https://arxiv.org/html/2609.02155#S2)and[section3](https://arxiv.org/html/2609.02155#S3)show why this distinction matters: the JL bound can hold even when the mapped points contain no information about the original geometry\.

> Central question\.Which features of the original geometry can a decoder recover from the sketch, and how much of each?

To analyze a single distance, we formulate the question as follows\. A known linear mapL:ℝd→ℝmL:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{m\}acts on a pairX,X′X,X^\{\\prime\}\. The target distance isD=‖X−X′‖2D=\\left\\lVert X\-X^\{\\prime\}\\right\\rVert^\{2\}, and the observation is the sketch𝒪=\(L​X,L​X′\)\\mathcal\{O\}=\(LX,LX^\{\\prime\}\)\. A*feature*is a square\-integrable scalarf⁡\(D\)f\(D\)with positive varianceVar⁡\(f⁡\(D\)\)\>0\\Var\(f\(D\)\)\>0\. A*decoder*is any measurable functiong⁡\(𝒪\)g\(\\mathcal\{O\}\)\.

Under squared\-error loss, the optimal decoder for a feature is its conditional expectation\. By the law of total variance, this optimal decoder minimizes the mean squared error:

gf⋆\(𝒪\)=𝔼\[f\(D\)∣𝒪\],infg𝔼\[\(f\(D\)−g\(𝒪\)\)2\]=Var\(f\(D\)\)−Var\(𝔼\[f\(D\)∣𝒪\]\)\.g\_\{f\}^\{\\star\}\(\\mathcal\{O\}\)=\\E\[f\(D\)\\mid\\mathcal\{O\}\],\\qquad\\inf\_\{g\}\\E\\bigl\[\(f\(D\)\-g\(\\mathcal\{O\}\)\)^\{2\}\\bigr\]=\\Var\(f\(D\)\)\-\\Var\\bigl\(\\E\[f\(D\)\\mid\\mathcal\{O\}\]\\bigr\)\.The conditional expectation orthogonally projectsf⁡\(D\)f\(D\)onto the closed subspace of square\-integrable functions of the sketch\. This projection splits the feature’s variance into a recovered part and an orthogonal residual\. We measure this recovery using the*recoverable variance fraction*:

𝖱𝖾𝖼⁡\(f,𝒪\)=Var⁡\(𝔼⁡\[f⁡\(D\)∣𝒪\]\)Var⁡\(f⁡\(D\)\)∈\[0,1\]\.\\mathsf\{Rec\}\(f;\\mathcal\{O\}\)=\\frac\{\\Var\\bigl\(\\E\[f\(D\)\\mid\\mathcal\{O\}\]\\bigr\)\}\{\\Var\(f\(D\)\)\}\\in\[0,1\]\.This fraction depends only on the feature and the observation, not on the choice of recovery algorithm\.

The criterion separates what the JL bound conflates\. For the replacement cloud of[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1), independence gives𝔼⁡\[f⁡\(D\)∣Yn\]=𝔼⁡f⁡\(D\)\\E\[f\(D\)\\mid Y^\{n\}\]=\\E f\(D\), hence𝖱𝖾𝖼⁡\(f,Yn\)=0\\mathsf\{Rec\}\(f;Y^\{n\}\)=0for every feature: the JL event can coexist with nothing recoverable\. A linear sketch of the data instead yields a nonzero projection\. The supremum of𝖱𝖾𝖼⁡\(f,𝒪\)\\mathsf\{Rec\}\(f;\\mathcal\{O\}\)over features is therefore the object of interest, and it is an operator norm\.

### 4\.2The distance\-recovery operator

Gathering all centered, square\-integrable features ofDDinto the spaceL02​\(D\)L^\{2\}\_\{0\}\(D\)frames recovery as an operator problem\. We define the*recovery operator*

𝒜:L02​\(D\)⟶L02​\(𝒪\),𝒜​f=𝔼⁡\[f⁡\(D\)∣𝒪\],\\mathcal\{A\}:L^\{2\}\_\{0\}\(D\)\\longrightarrow L^\{2\}\_\{0\}\(\\mathcal\{O\}\),\\qquad\\mathcal\{A\}f=\\E\[f\(D\)\\mid\\mathcal\{O\}\],whereL02​\(𝒪\)L^\{2\}\_\{0\}\(\\mathcal\{O\}\)denotes the centered, square\-integrable functions of the observation\. Because𝒜\\mathcal\{A\}is a restricted orthogonal projection, it never increases theL2L^\{2\}norm, yielding

𝖱𝖾𝖼⁡\(f,𝒪\)=‖𝒜​f‖22‖f‖22\.\\mathsf\{Rec\}\(f;\\mathcal\{O\}\)=\\frac\{\\left\\lVert\\mathcal\{A\}f\\right\\rVert\_\{2\}^\{2\}\}\{\\left\\lVert f\\right\\rVert\_\{2\}^\{2\}\}\.The squared operator norm‖𝒜‖op2\\left\\lVert\\mathcal\{A\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}represents the maximum recoverable fraction over all features\. This norm also equals the squared Hirschfeld–Gebelein–Rényi \(HGR\) maximal correlation[Rényi, 1959](https://arxiv.org/html/2609.02155#bib.bib9);[Dembo et al\., 2001](https://arxiv.org/html/2609.02155#bib.bib8), which measures the maximum correlation obtainable by transforming the target and the observation:

‖𝒜‖op2=supf∈L02​\(D\)f≠0‖𝒜​f‖22‖f‖22=ρHGR2​\(D,𝒪\),ρHGR​\(Y,Z\)=supf,g\|Corr⁡\(f⁡\(Y\),g⁡\(Z\)\)\|\.\\left\\lVert\\mathcal\{A\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}=\\sup\_\{\\begin\{subarray\}\{c\}f\\in L^\{2\}\_\{0\}\(D\)\\\\ f\\neq 0\\end\{subarray\}\}\\frac\{\\left\\lVert\\mathcal\{A\}f\\right\\rVert\_\{2\}^\{2\}\}\{\\left\\lVert f\\right\\rVert\_\{2\}^\{2\}\}=\\rho\_\{\\mathrm\{HGR\}\}^\{2\}\(D;\\mathcal\{O\}\),\\qquad\\rho\_\{\\mathrm\{HGR\}\}\(Y;Z\)=\\sup\_\{f,g\}\\left\|\\Corr\(f\(Y\),g\(Z\)\)\\right\|\.\(4\)Here, the last supremum is over all measurable, nonconstant, square\-integrable scalar functions\. Optimizing first overggyields the normalized conditional variance, which confirms this identity[Rényi, 1959](https://arxiv.org/html/2609.02155#bib.bib9)\. Consequently, no estimator can recover a variance fraction of any feature ofDDthat exceeds‖𝒜‖op2\\left\\lVert\\mathcal\{A\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.

The operator describes recovery at three levels:

one feature:‖𝒜​f‖22/‖f‖22,the best feature:‖𝒜‖op2,all features at once:the singular system of​𝒜\.\\begin\{array\}\[\]\{ll\}\\text\{one feature:\}&\\left\\lVert\\mathcal\{A\}f\\right\\rVert\_\{2\}^\{2\}/\\left\\lVert f\\right\\rVert\_\{2\}^\{2\},\\\\\[2\.0pt\] \\text\{the best feature:\}&\\left\\lVert\\mathcal\{A\}\\right\\rVert\_\{\\mathrm\{op\}\}^\{2\},\\\\\[2\.0pt\] \\text\{all features at once:\}&\\text\{the singular system of \}\\mathcal\{A\}\.\\end\{array\}Constant features are recovered perfectly and form a trivial mode\. Centering removes this mode, ensuring that the operator onL02​\(D\)L^\{2\}\_\{0\}\(D\)captures only the geometric information\. While the operator norm is always defined, a discrete singular system exists only for specific channels\. The Gaussian channel we construct next admits such a system in closed form\.

### 4\.3The Gaussian distance channel

We identify the concrete operator by reducing the sketch to a scalar channel\. The first step,*row orthonormalization*, is a reversible output transformation that preserves all information in a noiseless linear observation by a known map\. Let a rank\-rrmapLLhave thin singular value decompositionL=Ur​Sr​Vr⊤L=U\_\{r\}S\_\{r\}V\_\{r\}^\{\\top\}and putR=Vr⊤R=V\_\{r\}^\{\\top\}\. Discarding redundant output coordinates yields

L​x=Ur​Sr​R​x,R​x=Sr−1​Ur⊤​L​x\.Lx=U\_\{r\}S\_\{r\}Rx,\\qquad Rx=S\_\{r\}^\{\-1\}U\_\{r\}^\{\\top\}Lx\.BecauseSrS\_\{r\}is invertible,L​xLxandR​xRxuniquely determine each other on the nonredundant output\. IfLLhas full row rank, we can instead takeR=\(LL⊤\)−1/2LR=\(LL^\{\\top\}\)^\{\-1/2\}L\. Hererrdenotes the rank ofLL; for full\-row\-rank sketches withmmrows,r=mr=m\.

LetΣ=σ2​Id\\Sigma=\\sigma^\{2\}I\_\{d\}, and letLLhave rank0<r<d0<r<d\. Under this isotropic covariance, row orthonormalization replaces the sketch with the equivalent pair\(Π​X,Π​X′\)\(\\Pi X,\\Pi X^\{\\prime\}\), whereΠ\\Piis a rank\-rrorthogonal projector, and by rotational invariance the law of this pair depends onΠ\\Pionly through its rank\. For a random oblivious map, the row space is therefore all that matters\. A randomrr\-dimensional subspace ofℝd\\mathbb\{R\}^\{d\}is*Haar distributed*if it is uniform over the Grassmannian, the set of all such subspaces; represent it by anr×dr\\times dmatrixRRwith orthonormal rows and projectorΠ=R⊤​R\\Pi=R^\{\\top\}R\. Orthonormalizing the rows of an i\.i\.d\. standard Gaussian matrix yields this same Haar row\-space distribution, a standard construction in randomized numerical linear algebra[Halko et al\., 2011](https://arxiv.org/html/2609.02155#bib.bib19): right multiplication by a fixed orthogonal matrix preserves the Gaussian law, which makes the row space uniform on the Grassmannian\.

Standardize the difference as

Z=X−X′2​σ∼𝒩⁡\(0,Id\),𝒯=‖Z‖2,U=‖Π​Z‖2,V=𝒯−U\.Z=\\frac\{X\-X^\{\\prime\}\}\{\\sqrt\{2\}\\sigma\}\\sim\\mathcal\{N\}\(0,I\_\{d\}\),\\qquad\\mathcal\{T\}=\\left\\lVert Z\\right\\rVert^\{2\},\\qquad U=\\left\\lVert\\Pi Z\\right\\rVert^\{2\},\\qquad V=\\mathcal\{T\}\-U\.ThenU∼χr2U\\sim\\chi\_\{r\}^\{2\},V∼χd−r2V\\sim\\chi\_\{d\-r\}^\{2\},U⟂VU\\perp V, andD=2​σ2​𝒯D=2\\sigma^\{2\}\\mathcal\{T\}\.

Three independence properties reduce the full sketch to the scalarUU\. First, the Gaussian midpoint\(X\+X′\)/2\(X\+X^\{\\prime\}\)/2is independent ofX−X′X\-X^\{\\prime\}, so its projection carries no information aboutDD\. Second, rotational invariance makes the direction ofΠ​Z\\Pi Zuniform on the unit sphere ofrange⁡\(Π\)\\operatorname\{range\}\(\\Pi\)and independent of its lengthU1/2U^\{1/2\}\. Third, the orthogonal Gaussian componentsΠ​Z\\Pi Zand\(I−Π\)​Z\(I\-\\Pi\)Zare independent, soVVis independent of the entire retained vector\. Therefore, the conditional law of𝒯\\mathcal\{T\}given the full sketch depends only onUU; in probabilistic notation,D⟂𝒪\|UD\\perp\\mathcal\{O\}\\mid U\.[Figure2](https://arxiv.org/html/2609.02155#S4.F2)summarizes this reduction\.

Standard gamma\-sum identities now specify the channel\. IfU∼Gamma⁡\(a,θ\)U\\sim\\operatorname\{Gamma\}\(a,\\theta\)andV∼Gamma⁡\(b,θ\)V\\sim\\operatorname\{Gamma\}\(b,\\theta\)are independent, then

𝒯=U\+V∼Gamma⁡\(a\+b,θ\),U𝒯∼Beta⁡\(a,b\),U𝒯⟂𝒯\.\\mathcal\{T\}=U\+V\\sim\\operatorname\{Gamma\}\(a\+b,\\theta\),\\qquad\\frac\{U\}\{\\mathcal\{T\}\}\\sim\\operatorname\{Beta\}\(a,b\),\\qquad\\frac\{U\}\{\\mathcal\{T\}\}\\perp\\mathcal\{T\}\.Herea=r/2a=r/2,b=\(d−r\)/2b=\(d\-r\)/2, and the common scale isθ=2\\theta=2for the chi\-squared laws above\. ObservingUUfrom the latent total𝒯=U\+V\\mathcal\{T\}=U\+Vforms the*beta–gamma channel*\.

Figure 2:The distance channel\. A rank\-rrsketch splits the squared norm of a standardized Gaussian difference into observed and omitted parts\. GivenUU, the rest of the sketch provides no further information about the distanceD=2​σ2​\(U\+V\)D=2\\sigma^\{2\}\(U\+V\)\.The distance\-recovery problem is now reduced to the conditional\-expectation operator of the beta–gamma channel: sinceD⟂𝒪\|UD\\perp\\mathcal\{O\}\\mid UandD=2​σ2​𝒯D=2\\sigma^\{2\}\\mathcal\{T\}, the operator𝒜\\mathcal\{A\}acts throughh⁡\(𝒯\)↦𝔼⁡\[h⁡\(𝒯\)∣U\]h\(\\mathcal\{T\}\)\\mapsto\\E\[h\(\\mathcal\{T\}\)\\mid U\]\.[Section5](https://arxiv.org/html/2609.02155#S5)computes its operator norm and its complete singular spectrum\.

### 4\.4How the framework recurs

The ranking and covariance\-shape problems replace the pair\(L02​\(D\),L02​\(𝒪\)\)\(L^\{2\}\_\{0\}\(D\),L^\{2\}\_\{0\}\(\\mathcal\{O\}\)\)by other target and observable spaces\. One formulation—conditional expectation as orthogonal projection—covers all three problems; the operator itself differs with each target\. Throughout,ddis the ambient dimension,mmthe output dimension, andrrthe map rank;nnis the sample size andqqthe number of candidates compared to a query;DDdenotes a squared distance,SSa shared\-query distance contrast, and𝒪\\mathcal\{O\}the observed sketch\. Three derived quantities recur:ρHGR\\rho\_\{\\mathrm\{HGR\}\}is the maximal correlation between a target and an observation,r2​\(Σ\)=\(tr⁡Σ\)2/tr⁡\(Σ2\)r\_\{2\}\(\\Sigma\)=\(\\tr\\Sigma\)^\{2\}/\\tr\(\\Sigma^\{2\}\)is the effective rank of the spectrum, andℓk\\ell\_\{k\}indexes the singular values of the distance\-recovery operator\. Sections[6](https://arxiv.org/html/2609.02155#S6)and beyond introduce the recovery fractionsαm​\(Σ\)\\alpha\_\{m\}\(\\Sigma\)andαΠ​\(Σ\)\\alpha\_\{\\Pi\}\(\\Sigma\)and the block retention ratiosθg\\theta\_\{g\}where they are first used\.

For distance features,[section5](https://arxiv.org/html/2609.02155#S5)solves the operator just constructed: the centered distance attains the operator normr/d\\sqrt\{r/d\}, and the full singular system is a generalized Laguerre family\.[Section6](https://arxiv.org/html/2609.02155#S6)then treats general covariance, where recovering the distance value and recovering the best nonlinear feature can differ\. The recovery scale is a variance fraction of orderm/dm/d, a quantity the JL bound does not control \([section2](https://arxiv.org/html/2609.02155#S2)\)\.

For neighbor rankings, the target is the shared\-query contrastS=D01−D02S=D\_\{01\}\-D\_\{02\}, or its sign, and we observe𝒪=\(L​X0,L​X1,L​X2\)\\mathcal\{O\}=\(LX\_\{0\},LX\_\{1\},LX\_\{2\}\)\. The target is a function of two dependent distances, so the scalar operator is replaced by a projection of the joint contrast; we calculate the exact sign law from a conditional Gaussian calculation \([section7](https://arxiv.org/html/2609.02155#S7)\)\. Sign statistics inherit the correlation scalem/d\\sqrt\{m/d\}rather than the variance\-fraction scalem/dm/d\.

For covariance shape, the relevant Hilbert space is the Gaussian score space, and removing the unknown overall scale is an orthogonal projection of the shape score onto the orthogonal complement of the nuisance scale score\. The resulting efficient Fisher information contracts at order\(m/d\)2\(m/d\)^\{2\}for diffuse shape directions \([section8](https://arxiv.org/html/2609.02155#S8)\)\.

Table 1:Guide to the three recovery laws\. Each law is stated in the units of its recovery quantity\.TargetRecovery quantityRecovery lawDistance features, isotropicrecoverable variance fractionm/dm/dNeighbor rankingsexcess pairwise agreement over chanceπ−1​m/d​\(1\+o⁡\(1\)\)\\pi^\{\-1\}\\sqrt\{m/d\}\\,\(1\+o\(1\)\)Diffuse covariance shapeHaar\-mean efficient\-information fraction\(m−1\)​\(m\+2\)\(d−1\)​\(d\+2\)∼\(m/d\)2\\dfrac\{\(m\-1\)\(m\+2\)\}\{\(d\-1\)\(d\+2\)\}\\sim\(m/d\)^\{2\}

The exponents differ because the three rows measure different objects\. Variance recovery squares anL2L^\{2\}correlation, rank comparisons depend on a sign probability and therefore on the correlation itself, and a covariance perturbation is compressed on both sides by the random projector\.

## 5Exact Solution of the Gaussian Distance Operator

For the beta–gamma channel of[section4\.3](https://arxiv.org/html/2609.02155#S4.SS3), the recovery operator𝒜\\mathcal\{A\}of[section4\.2](https://arxiv.org/html/2609.02155#S4.SS2)acts through the scalar pair\(U,𝒯\)\(U,\\mathcal\{T\}\)\. This section computes its operator norm, then its complete singular system, and derives the channel’s mutual information and identities for the distance\.

### 5\.1The operator norm

The norm follows from a result on partial sums\. Dembo, Kagan, and Shepp[Dembo et al\., 2001](https://arxiv.org/html/2609.02155#bib.bib8)proved that the maximal correlation between a partial sum ofrri\.i\.d\. nondegenerate finite\-variance variables and a containing sum ofddsuch variables isr/d\\sqrt\{r/d\}\. The chi\-square variables of[section4\.3](https://arxiv.org/html/2609.02155#S4.SS3)satisfy these hypotheses\. Ordinary linear correlation already equalsr/d\\sqrt\{r/d\}; the theorem says that nonlinear transformations of the partial and total sums cannot improve it\.

###### Theorem 5\.1\(Operator norm and maximal correlation\)\.

For the isotropic component and any rank\-rrlinear observation,

‖𝒜‖op=ρHGR​\(D,𝒪\)=rd\.\\left\\lVert\\mathcal\{A\}\\right\\rVert\_\{\\mathrm\{op\}\}=\\rho\_\{\\mathrm\{HGR\}\}\(D;\\mathcal\{O\}\)=\\sqrt\{\\frac\{r\}\{d\}\}\.Consequently,Var⁡\(𝔼⁡\[f⁡\(D\)∣𝒪\]\)≤\(r/d\)​Var⁡\(f⁡\(D\)\)\\Var\(\\E\[f\(D\)\\mid\\mathcal\{O\}\]\)\\leq\(r/d\)\\Var\(f\(D\)\)for everyf∈L2f\\in L^\{2\}, and

infg𝔼⁡\[\(f⁡\(D\)−g⁡\(𝒪\)\)2\]≥\(1−r/d\)​Var⁡\(f⁡\(D\)\)\.\\inf\_\{g\}\\E\[\(f\(D\)\-g\(\\mathcal\{O\}\)\)^\{2\}\]\\geq\(1\-r/d\)\\Var\(f\(D\)\)\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) writes𝒯\\mathcal\{T\}as a sum ofddindependentχ12\\chi\_\{1\}^\{2\}variables andUUas the partial sum of the firstrr\. The Dembo–Kagan–Shepp theorem gives maximal correlationr/d\\sqrt\{r/d\}for this pair\. BecauseUUis sufficient for𝒯\\mathcal\{T\}—the rest of the sketch carries no further information about the distance—the identity transfers to the full sketch\. Thus thresholds, quantiles, clipped distances, and every other square\-integrable scalar feature obey the same decoder\-free ceiling\. Mutual information complements this ceiling by measuring total dependence[Cover and Thomas, 2006](https://arxiv.org/html/2609.02155#bib.bib33), but neither quantity resolves recovery mode by mode; the singular system does\.

### 5\.2The singular spectrum

The gamma law is the orthogonality measure for the generalized Laguerre polynomials, and Griffiths[Griffiths, 1969](https://arxiv.org/html/2609.02155#bib.bib10)diagonalized the gamma conditional\-expectation operatorh⁡\(𝒯\)↦𝔼⁡\[h⁡\(𝒯\)∣U\]h\(\\mathcal\{T\}\)\\mapsto\\E\[h\(\\mathcal\{T\}\)\\mid U\]in that basis\. For the beta–gamma pair of[section4\.3](https://arxiv.org/html/2609.02155#S4.SS3), this system resolves recoverable variance one fluctuation component at a time\.

###### Theorem 5\.2\(Laguerre spectrum\)\.

The conditional\-expectation operatorf⁡\(𝒯\)↦𝔼⁡\[f⁡\(𝒯\)∣U\]f\(\\mathcal\{T\}\)\\mapsto\\E\[f\(\\mathcal\{T\}\)\\mid U\]has generalized Laguerre singular functions and singular values

ℓk=\(\(r/2\)k\(d/2\)k\)1/2,k=0,1,2,…,\\ell\_\{k\}=\\left\(\\frac\{\(r/2\)\_\{k\}\}\{\(d/2\)\_\{k\}\}\\right\)^\{1/2\},\\qquad k=0,1,2,\\ldots,where\(a\)k\(a\)\_\{k\}is the rising factorial[Griffiths, 1969](https://arxiv.org/html/2609.02155#bib.bib10)\. Iff⁡\(𝒯\)−𝔼⁡f⁡\(𝒯\)=∑k≥1ck​ϕk​\(𝒯\)f\(\\mathcal\{T\}\)\-\\E f\(\\mathcal\{T\}\)=\\sum\_\{k\\geq 1\}c\_\{k\}\\phi\_\{k\}\(\\mathcal\{T\}\)is the orthonormal Laguerre expansion, then

Var⁡\(𝔼⁡\[f⁡\(𝒯\)∣𝒪\]\)=∑k≥1ℓk2​ck2\.\\Var\(\\E\[f\(\\mathcal\{T\}\)\\mid\\mathcal\{O\}\]\)=\\sum\_\{k\\geq 1\}\\ell\_\{k\}^\{2\}c\_\{k\}^\{2\}\.For fixedkk, asr→∞r\\to\\inftyandd−r→∞d\-r\\to\\infty,

ℓk=\(rd\)k/2​\[1\+Ok​\(1r\+1d\)\]\.\\ell\_\{k\}=\\left\(\\frac\{r\}\{d\}\\right\)^\{k/2\}\\left\[1\+O\_\{k\}\\\!\\left\(\\frac\{1\}\{r\}\+\\frac\{1\}\{d\}\\right\)\\right\]\.

This is Griffiths’s diagonalization specialized to the gamma parametersa=r/2a=r/2anda\+b=d/2a\+b=d/2; the proof, with that of[theorem5\.3](https://arxiv.org/html/2609.02155#S5.Thmtheorem3), appears in[sectionB](https://arxiv.org/html/2609.02155#S2a)\. The first nonconstant mode is the centered total energy𝒯−𝔼⁡𝒯\\mathcal\{T\}\-\\E\\mathcal\{T\}and hasℓ1=r/d=‖𝒜‖op\\ell\_\{1\}=\\sqrt\{r/d\}=\\left\\lVert\\mathcal\{A\}\\right\\rVert\_\{\\mathrm\{op\}\}, so the operator norm of[theorem5\.1](https://arxiv.org/html/2609.02155#S5.Thmtheorem1)is attained by the centered distance itself\. The second mode is the orthogonalized quadratic fluctuation of𝒯\\mathcal\{T\}\. Thuskkindexes increasingly nonlinear fluctuation components, not additional spatial coordinates\. At leading order, advancing from modekkto modek\+1k\+1costs an additional factor ofr/d\\sqrt\{r/d\}\.

### 5\.3Mutual information and identities for the distance

The spectrum measures recoverable variance feature by feature\. From the gamma entropies of the observed and omitted squared norms, we also obtain the total mutual information\.

###### Theorem 5\.3\(Exact mutual information\)\.

WithhΓ​\(k\)h\_\{\\Gamma\}\(k\)the entropy of a gamma variable of shapekkat any fixed scale,

I⁡\(D,𝒪\)=hΓ​\(d2\)−hΓ​\(d−r2\)⟶−12​log⁡\(1−α\)I\(D;\\mathcal\{O\}\)=h\_\{\\Gamma\}\\\!\\left\(\\frac\{d\}\{2\}\\right\)\-h\_\{\\Gamma\}\\\!\\left\(\\frac\{d\-r\}\{2\}\\right\)\\longrightarrow\-\\frac\{1\}\{2\}\\log\(1\-\\alpha\)ifr/d→α<1r/d\\to\\alpha<1andd−r→∞d\-r\\to\\infty\. Ifr/d→0r/d\\to 0, thenI⁡\(D,𝒪\)=r/\(2​d\)\+O⁡\(r2/d2\+1/d\)I\(D;\\mathcal\{O\}\)=r/\(2d\)\+O\(r^\{2\}/d^\{2\}\+1/d\)\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) evaluates the gamma entropies of the observed and omitted squared norms; the limits follow from Stirling expansions\.

For the rank\-rrprojector, define the rescaled projected distance by

D~=dr​‖Π⁡\(X−X′\)‖2\.\\widetilde\{D\}=\\frac\{d\}\{r\}\\left\\lVert\\Pi\(X\-X^\{\\prime\}\)\\right\\rVert^\{2\}\.The same decomposition gives three identities for the distance:

Corr⁡\(D,D~\)=r/d,inff𝔼⁡\[\(D−f⁡\(D~\)\)2\]Var⁡\(D\)=1−rd,\\Corr\(D,\\widetilde\{D\}\)=\\sqrt\{r/d\},\\qquad\\frac\{\\inf\_\{f\}\\E\[\(D\-f\(\\widetilde\{D\}\)\)^\{2\}\]\}\{\\Var\(D\)\}=1\-\\frac\{r\}\{d\},and

𝔼⁡\[\(\(D~−𝔼⁡D~\)−\(D−𝔼⁡D\)\)2\]Var⁡\(D\)=d−rr\.\\frac\{\\E\[\(\(\\widetilde\{D\}\-\\E\\widetilde\{D\}\)\-\(D\-\\E D\)\)^\{2\}\]\}\{\\Var\(D\)\}=\\frac\{d\-r\}\{r\}\.Rescaling preserves the common baseline, but the fluctuation noise ofD~\\widetilde\{D\}has relative orderr−1/2r^\{\-1/2\}rather than the data’sd−1/2d^\{\-1/2\}\.

For one pair under a rank\-mmlinear sketch,

ρHGR​\(Di​j,\(L​Xi,L​Xj\)\)=m/d\\rho\_\{\\mathrm\{HGR\}\}\\bigl\(D\_\{ij\};\(LX\_\{i\},LX\_\{j\}\)\\bigr\)=\\sqrt\{m/d\}whereas the replacement cloudYnY^\{n\}of[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1)gives

ρHGR​\(Di​j,Yn\)=0\.\\rho\_\{\\mathrm\{HGR\}\}\(D\_\{ij\};Y^\{n\}\)=0\.Thus, the JL bound is compatible both with the maximal dependencem/d\\sqrt\{m/d\}attainable from a rank\-mmlinear sketch of one distance and with zero dependence\.

The isotropic operator is now solved\.[Section6](https://arxiv.org/html/2609.02155#S6)extends distance recovery to general covariance, where the operator norm and the recovery fraction for the distance can separate\.

## 6Distance Recovery Beyond Isotropy

The isotropic solution is complete:[theorems5\.1](https://arxiv.org/html/2609.02155#S5.Thmtheorem1)and[5\.2](https://arxiv.org/html/2609.02155#S5.Thmtheorem2)give the operator norm and the full singular spectrum\. Anisotropy separates two questions that coincide for a flat spectrum: recovery of the distance value and recovery of an arbitrary nonlinear feature\.

### 6\.1General covariance: the recovery fraction for the distance

[Theorem5\.1](https://arxiv.org/html/2609.02155#S5.Thmtheorem1)is an isotropic statement about every feature\. For general covariance, recovery of the distance value itself admits an exact answer for every spectrum and every rank\-mmmap\. Because eigendirectionjjcontributes8​λj28\\lambda\_\{j\}^\{2\}toVar⁡\(D\)\\Var\(D\), an optimalmm\-dimensional observation targets the largest squared eigenvalues\. We therefore define the*recovery fraction for the distanceDD*by

αm​\(Σ\)=∑j≤mλj2∑j≤dλj2∈\(0,1\]\.\\alpha\_\{m\}\(\\Sigma\)=\\frac\{\\sum\_\{j\\leq m\}\\lambda\_\{j\}^\{2\}\}\{\\sum\_\{j\\leq d\}\\lambda\_\{j\}^\{2\}\}\\in\(0,1\]\.\(5\)
We must separate two recovery questions\. First,αm​\(Σ\)\\alpha\_\{m\}\(\\Sigma\)is the largest fraction ofVar⁡\(D\)\\Var\(D\)recoverable by a rank\-mmmap\. Second, for a fixed observation,ρHGR2​\(D,𝒪\)\\rho\_\{\\mathrm\{HGR\}\}^\{2\}\(D;\\mathcal\{O\}\)is the largest recoverable fraction over*all*square\-integrable features ofDD\. These quantities coincide atm/dm/din the isotropic case\. Under anisotropy they can differ; balanced spectral retention is a sufficient condition that restores equality\.

###### Theorem 6\.1\(Sharp rank\-mmlimit for distance recovery\)\.

For every rank\-mmlinearLLand every measurable estimatorgg,

Var⁡\(𝔼⁡\[D∣𝒪\]\)Var⁡\(D\)≤αm​\(Σ\),𝔼⁡\[\(D−g⁡\(𝒪\)\)2\]≥8​∑j\>mλj2\.\\frac\{\\Var\\bigl\(\\E\[D\\mid\\mathcal\{O\}\]\\bigr\)\}\{\\Var\(D\)\}\\leq\\alpha\_\{m\}\(\\Sigma\),\\qquad\\E\\bigl\[\(D\-g\(\\mathcal\{O\}\)\)^\{2\}\\bigr\]\\geq 8\\sum\_\{j\>m\}\\lambda\_\{j\}^\{2\}\.The variance bound is attained when the row space ofLLis the top\-mmeigenspace ofΣ\\Sigma; for this map, the mean\-square bound is attained byg=𝔼⁡\[D∣𝒪\]g=\\E\[D\\mid\\mathcal\{O\}\]\. The same statements, withVar⁡\(S\)=12​tr⁡\(Σ2\)\\Var\(S\)=12\\tr\(\\Sigma^\{2\}\), hold for the neighbor contrastS=‖X0−X1‖2−‖X0−X2‖2S=\\left\\lVert X\_\{0\}\-X\_\{1\}\\right\\rVert^\{2\}\-\\left\\lVert X\_\{0\}\-X\_\{2\}\\right\\rVert^\{2\}given\(L​X0,L​X1,L​X2\)\(LX\_\{0\},LX\_\{1\},LX\_\{2\}\)\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) combines the Gaussian conditional mean, a projector identity, and eigenvalue interlacing for the compressed covariance\. The bounds are uniform: no nonlinear estimator of the distance value and noΣ\\Sigma\-aware choice ofLLexceeds the squared\-eigenvalue limit\. The mean\-square bound also follows from the law of total variance: subtracting at most8​∑j≤mλj28\\sum\_\{j\\leq m\}\\lambda\_\{j\}^\{2\}recovered variance fromVar⁡\(D\)=8​∑j≤dλj2\\Var\(D\)=8\\sum\_\{j\\leq d\}\\lambda\_\{j\}^\{2\}leaves at least8​∑j\>mλj28\\sum\_\{j\>m\}\\lambda\_\{j\}^\{2\}\.

### 6\.2Anisotropy: divergence and reconciliation

The isotropic identity might suggest thatαm​\(Σ\)\\sqrt\{\\alpha\_\{m\}\(\\Sigma\)\}bounds HGR under anisotropy, but this bound fails in general\. The mechanism is unequal retention across independent spectral blocks: observing one block completely while discarding another can let a nonlinear transformation reweight their contributions\. A two\-dimensional counterexample illustrates this mechanism\.

###### Theorem 6\.2\(Anisotropic counterexample\)\.

LetD=2​G12\+G22D=2G\_\{1\}^\{2\}\+G\_\{2\}^\{2\}for independent standard normalsG1,G2G\_\{1\},G\_\{2\}, and observeU=2​G12U=2G\_\{1\}^\{2\}\. Althoughα1=4/5\\alpha\_\{1\}=4/5, quadratic polynomial features already give

ρHGR​\(D,U\)≥246\+2​201311≈0\.9392\>4/5\.\\rho\_\{\\mathrm\{HGR\}\}\(D;U\)\\geq\\sqrt\{\\frac\{246\+2\\sqrt\{201\}\}\{311\}\}\\approx 0\.9392\>\\sqrt\{4/5\}\.

WhenρHGR2​\(D,𝒪\)\>αm​\(Σ\)\\rho\_\{\\mathrm\{HGR\}\}^\{2\}\(D;\\mathcal\{O\}\)\>\\alpha\_\{m\}\(\\Sigma\), some nonlinear feature ofDDis more recoverable than the distance value itself\. We call this gap*nonlinear excess*\. Here4/5≈0\.8944\\sqrt\{4/5\}\\approx 0\.8944is the linear correlation with the distance\. The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) evaluates the canonical correlation of the quadratic features, which makes the displayed value a lower bound onρHGR\\rho\_\{\\mathrm\{HGR\}\}\. ForDλ=λ​G12\+G22D\_\{\\lambda\}=\\lambda G\_\{1\}^\{2\}\+G\_\{2\}^\{2\}andUλ=λ​G12U\_\{\\lambda\}=\\lambda G\_\{1\}^\{2\},[Figure4](https://arxiv.org/html/2609.02155#S7.F4)reports canonical\-correlation lower bounds from nested polynomial feature spaces\. These values are lower bounds for a fixed observation, not the unrestricted HGR value or an optimization over observations\.

Nonlinear excess can occur but is not universal\. A sufficient condition for its absence follows by writing

Σ=∑g=1Gλg​Pg,rg=rank⁡Pg,\\Sigma=\\sum\_\{g=1\}^\{G\}\\lambda\_\{g\}P\_\{g\},\\qquad r\_\{g\}=\\rank P\_\{g\},where theλg\>0\\lambda\_\{g\}\>0are distinct andPgP\_\{g\}projects onto the associated eigenspace, or*spectral block*\. LetΠ\\PisatisfyΠ​Σ=Σ​Π\\Pi\\Sigma=\\Sigma\\Pi, so it preserves every block, and define

sg=rank⁡\(Π​Pg\),θg=sgrg,αΠ​\(Σ\)=tr⁡\(Π​Σ2\)tr⁡\(Σ2\)=∑gλg2​sg∑gλg2​rg\.s\_\{g\}=\\rank\(\\Pi P\_\{g\}\),\\qquad\\theta\_\{g\}=\\frac\{s\_\{g\}\}\{r\_\{g\}\},\\qquad\\alpha\_\{\\Pi\}\(\\Sigma\)=\\frac\{\\tr\(\\Pi\\Sigma^\{2\}\)\}\{\\tr\(\\Sigma^\{2\}\)\}=\\frac\{\\sum\_\{g\}\\lambda\_\{g\}^\{2\}s\_\{g\}\}\{\\sum\_\{g\}\\lambda\_\{g\}^\{2\}r\_\{g\}\}\.The Gaussian distance then splits across independent beta–gamma channels, one per spectral block\. Maximal correlation tensorizes over such independent pairs[Witsenhausen, 1975](https://arxiv.org/html/2609.02155#bib.bib34): for nondegenerate\(Yj,Zj\)\(Y\_\{j\},Z\_\{j\}\)independent acrossjj,

ρHGR​\(\(Yj\)j,\(Zj\)j\)=maxj⁡ρHGR​\(Yj,Zj\)\.\\rho\_\{\\mathrm\{HGR\}\}\\bigl\(\(Y\_\{j\}\)\_\{j\};\(Z\_\{j\}\)\_\{j\}\\bigr\)=\\max\_\{j\}\\rho\_\{\\mathrm\{HGR\}\}\(Y\_\{j\};Z\_\{j\}\)\.
###### Theorem 6\.3\(Spectral\-block HGR bounds and the balanced regime\)\.

For independentX,X′∼𝒩⁡\(μ,Σ\)X,X^\{\\prime\}\\sim\\mathcal\{N\}\(\\mu,\\Sigma\), letD=‖X−X′‖2D=\\left\\lVert X\-X^\{\\prime\}\\right\\rVert^\{2\}and𝒪=\(Π​X,Π​X′\)\\mathcal\{O\}=\(\\Pi X,\\Pi X^\{\\prime\}\)\. UnderΠ​Σ=Σ​Π\\Pi\\Sigma=\\Sigma\\Pi,

αΠ​\(Σ\)≤ρHGR​\(D,𝒪\)≤maxg⁡θg\.\\sqrt\{\\alpha\_\{\\Pi\}\(\\Sigma\)\}\\leq\\rho\_\{\\mathrm\{HGR\}\}\(D;\\mathcal\{O\}\)\\leq\\sqrt\{\\max\_\{g\}\\theta\_\{g\}\}\.Ifsg=θ​rgs\_\{g\}=\\theta r\_\{g\}for every nonzero spectral block, then

ρHGR​\(D,𝒪\)=θ=αΠ​\(Σ\)\.\\rho\_\{\\mathrm\{HGR\}\}\(D;\\mathcal\{O\}\)=\\sqrt\{\\theta\}=\\sqrt\{\\alpha\_\{\\Pi\}\(\\Sigma\)\}\.Consequently,Var⁡\(𝔼⁡\[f⁡\(D\)∣𝒪\]\)≤θ​Var⁡\(f⁡\(D\)\)\\Var\(\\E\[f\(D\)\\mid\\mathcal\{O\}\]\)\\leq\\theta\\Var\(f\(D\)\)for everyf∈L2​\(D\)f\\in L^\{2\}\(D\), and the centered distance paired with the centered retained squared norm attains maximal correlation\.

Witsenhausen tensorization bounds this product channel by its largest block correlation,maxg⁡θg\\sqrt\{\\max\_\{g\}\\theta\_\{g\}\}; a centered linear witness supplies the lower bound \([sectionB](https://arxiv.org/html/2609.02155#S2a)contains the full argument\)\. Unequal eigenvalues alone therefore do not break the balanced identity\. Unequal retention permits nonlinear excess but does not force it; equal fractional retention makes the excess vanish\.

The flat spectrum closes the gap between the two recovery quantities\. IfΣ=λ​P\\Sigma=\\lambda Phas flat support of rankrr, an observation retaining ranksswithinrange⁡\(P\)\\operatorname\{range\}\(P\)hasρHGR2=s/r\\rho\_\{\\mathrm\{HGR\}\}^\{2\}=s/r; an optimal rank\-at\-most\-mmobservation chooses its row space inside the support, takess=min⁡\{m,r\}s=\\min\\\{m,r\\\}, and attainsρHGR2=αm​\(Σ\)\\rho\_\{\\mathrm\{HGR\}\}^\{2\}=\\alpha\_\{m\}\(\\Sigma\)\. More generally, for one distance,αm​\(Σ\)\\alpha\_\{m\}\(\\Sigma\)governs the distance value for every spectrum, andαΠ​\(Σ\)\\alpha\_\{\\Pi\}\(\\Sigma\)is also the ceiling for every feature under a balanced aligned projection\. Rankings compare several dependent distances sharing a query and follow the square\-root correlation scale associated with the same rank ratio\.

## 7Rankings Under Random Projection

[Sections5](https://arxiv.org/html/2609.02155#S5)and[6](https://arxiv.org/html/2609.02155#S6)quantified the recovery of one distance\. Rankings instantiate the projection template of[section4\.4](https://arxiv.org/html/2609.02155#S4.SS4)with the shared\-query contrast as target and the three projected points as observation\. Because rankings compare several dependent distances, we first define the rank functional and identify the ranking scale before computing its exact law\.

For two tie\-free score vectorsa,b∈ℝqa,b\\in\\mathbb\{R\}^\{q\}, Kendall’s rank correlation is

τ⁡\(a,b\)=\(q2\)−1​∑j<ksgn⁡\[\(aj−ak\)​\(bj−bk\)\]\.\\tau\(a,b\)=\\binom\{q\}\{2\}^\{\-1\}\\sum\_\{j<k\}\\operatorname\{sgn\}\\\!\\left\[\(a\_\{j\}\-a\_\{k\}\)\(b\_\{j\}\-b\_\{k\}\)\\right\]\.\(6\)This statistic is the fraction of concordant pairs minus the fraction of discordant pairs[Kendall, 1938](https://arxiv.org/html/2609.02155#bib.bib36)\. For independent continuous rankings, the expected Kendall correlation is zero\.

### 7\.1Whym/d\\sqrt\{m/d\}: sign statistics at the linear mode

We can identify the ranking scale before the exact calculation\. For a queryX0X\_\{0\}and candidatesX1,X2X\_\{1\},X\_\{2\}, write

S=D01−D02=a⊤​b,a=X1−X2,b=X1\+X2−2​X0\.S=D\_\{01\}\-D\_\{02\}=a^\{\\top\}b,\\qquad a=X\_\{1\}\-X\_\{2\},\\qquad b=X\_\{1\}\+X\_\{2\}\-2X\_\{0\}\.For i\.i\.d\. isotropic Gaussians,aaandbbare independent\. Under the rescaled rank\-mmprojector, the contrast isS~=\(d/m\)​a⊤​Π​b\\widetilde\{S\}=\(d/m\)a^\{\\top\}\\Pi b\. Conditional onaa, the pair\(S,S~\)\(S,\\widetilde\{S\}\)is centered jointly Gaussian inbbwith correlation

ρ⁡\(a\)=‖Π​a‖‖a‖,ρ​\(a\)2∼Beta⁡\(m2,d−m2\)\.\\rho\(a\)=\\frac\{\\left\\lVert\\Pi a\\right\\rVert\}\{\\left\\lVert a\\right\\rVert\},\\qquad\\rho\(a\)^\{2\}\\sim\\operatorname\{Beta\}\\\!\\left\(\\frac\{m\}\{2\},\\frac\{d\-m\}\{2\}\\right\)\.The squared correlation has meanm/dm/d\.

For a centered jointly Gaussian pair, Sheppard[Sheppard, 1899](https://arxiv.org/html/2609.02155#bib.bib11)showed that the sign\-agreement probability is12\+π−1​arcsin⁡ρ\\tfrac\{1\}\{2\}\+\\pi^\{\-1\}\\arcsin\\rho\. Asρ→0\\rho\\to 0, this agreement probability exceeds chance byρ/π\+O⁡\(ρ3\)\\rho/\\pi\+O\(\\rho^\{3\}\)\. Thus the retained\-energy fractionm/dm/dbecomes a ranking excess of orderπ−1​m/d\\pi^\{\-1\}\\sqrt\{m/d\}on the correlation scale\. Averaging Sheppard’s formula over the Beta\-distributed conditional correlation then yields the exact law\.

### 7\.2Exact pairwise order agreement

LetX0,X1,X2​∼i\.i\.d\.​𝒩​\(μ,σ2​Id\)X\_\{0\},X\_\{1\},X\_\{2\}\\overset\{\\text\{i\.i\.d\.\}\}\{\\sim\}\\mathcal\{N\}\(\\mu,\\sigma^\{2\}I\_\{d\}\)independently of a Haar rank\-mmprojection, where0<m<d0<m<d\. LetD0​jD\_\{0j\}andD~0​j\\widetilde\{D\}\_\{0j\}be the original and rescaled projected squared distances\.

###### Theorem 7\.1\(Exact pairwise order agreement\)\.

The probability that the comparisons agree is

pm,d=Pr\[\(D01−D02\)\(D~01−D~02\)\>0\]=12\+1π𝔼\[arcsinB\],B∼Beta\(m2,d−m2\)\.p\_\{m,d\}=\\Pr\\bigl\[\(D\_\{01\}\-D\_\{02\}\)\(\\widetilde\{D\}\_\{01\}\-\\widetilde\{D\}\_\{02\}\)\>0\\bigr\]=\\frac\{1\}\{2\}\+\\frac\{1\}\{\\pi\}\\E\\\!\\left\[\\arcsin\\sqrt\{B\}\\right\],\\qquad B\\sim\\mathrm\{Beta\}\\\!\\left\(\\frac\{m\}\{2\},\\frac\{d\-m\}\{2\}\\right\)\.Hencepm,d≤12\+12​m/dp\_\{m,d\}\\leq\\tfrac\{1\}\{2\}\+\\tfrac\{1\}\{2\}\\sqrt\{m/d\}, and

pm,d=12\+1π​md​\(1\+O⁡\(1m\+md\)\)p\_\{m,d\}=\\frac\{1\}\{2\}\+\\frac\{1\}\{\\pi\}\\sqrt\{\\frac\{m\}\{d\}\}\\left\(1\+O\\\!\\left\(\\frac\{1\}\{m\}\+\\frac\{m\}\{d\}\\right\)\\right\)whenm→∞m\\to\\inftyandm/d→0m/d\\to 0\. For one query ranking any number of candidates, the expected Kendall correlation is𝔼⁡τ=2​pm,d−1\\E\\tau=2p\_\{m,d\}\-1\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) conditions onaain the preceding reduction and averages Sheppard’s formula over the Beta law\. Thus, whenm=o⁡\(d\)m=o\(d\), the expected pairwise agreement is onlyΘ⁡\(m/d\)\\Theta\(\\sqrt\{m/d\}\)above chance\.

Figure 3:Polynomial lower bounds forDλ↦UλD\_\{\\lambda\}\\mapsto U\_\{\\lambda\}\. Higher degrees reveal nonlinear dependence beyondα1\\sqrt\{\\alpha\_\{1\}\}; the vertical line marks the counterexampleλ=2\\lambda=2\.Figure 4:Pairwise order agreement: the exact Beta–arcsine law, its asymptote, and Monte Carlo simulations atd=200d=200with120,000120\{,\}000samples per marker\.

### 7\.3Nearest\-neighbor and top\-kkoverlap

Pairwise agreement does not determine whether the nearest candidate or the full top\-kkset is preserved\. LetX0,X1,…,Xq​∼i\.i\.d\.​𝒩​\(0,Id\)X\_\{0\},X\_\{1\},\\ldots,X\_\{q\}\\overset\{\\text\{i\.i\.d\.\}\}\{\\sim\}\\mathcal\{N\}\(0,I\_\{d\}\), withX0X\_\{0\}the query\. LetR∈ℝm×dR\\in\\mathbb\{R\}^\{m\\times d\}have orthonormal rows and be independent of the sample; isotropy makes its orientation irrelevant\. Let𝒩~k\\widetilde\{\\mathcal\{N\}\}\_\{k\}and𝒩k\\mathcal\{N\}\_\{k\}be the projected and original sets ofkknearest candidate indices\.

Write

Uj=‖R⁡\(Xj−X0\)‖2,Vj=‖\(I−Π\)​\(Xj−X0\)‖2,Π=R⊤​R\.U\_\{j\}=\\left\\lVert R\(X\_\{j\}\-X\_\{0\}\)\\right\\rVert^\{2\},\\qquad V\_\{j\}=\\left\\lVert\(I\-\\Pi\)\(X\_\{j\}\-X\_\{0\}\)\\right\\rVert^\{2\},\\qquad\\Pi=R^\{\\top\}R\.The projected ranking is determined byU=\(Uj\)jU=\(U\_\{j\}\)\_\{j\}, while the original ranking is determined byU\+VU\+V\. For one coordinate, Gaussian fourth moments give, for distinct candidatesjjandkk,

Var⁡\(\(xj−x0\)2\)=8,Cov⁡\(\(xj−x0\)2,\(xk−x0\)2\)=2\.\\Var\\\!\\left\(\(x\_\{j\}\-x\_\{0\}\)^\{2\}\\right\)=8,\\qquad\\Cov\\\!\\left\(\(x\_\{j\}\-x\_\{0\}\)^\{2\},\(x\_\{k\}\-x\_\{0\}\)^\{2\}\\right\)=2\.The centered and normalized vectors\(U−2​m​𝟏\)/m\(U\-2m\\mathbf\{1\}\)/\\sqrt\{m\}and\(V−2​\(d−m\)​𝟏\)/d−m\(V\-2\(d\-m\)\\mathbf\{1\}\)/\\sqrt\{d\-m\}therefore converge to independent Gaussian score vectors with covariance6​Iq\+2​𝟏𝟏⊤6I\_\{q\}\+2\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\. The rank\-one term in this covariance represents a random shift shared by every candidate\. Removing this shift leaves the ranks unchanged and gives correlationm/d\\sqrt\{m/d\}between the retained and full scores\.

For independent standard normal vectorsG,H∈ℝqG,H\\in\\mathbb\{R\}^\{q\}, let𝒦k​\(z\)\\mathcal\{K\}\_\{k\}\(z\)return the indices of thekksmallest coordinates and define

ℛq,k​\(ρ\)=1k​𝔼⁡\|𝒦k​\(G\)∩𝒦k​\(ρ​G\+1−ρ2​H\)\|\.\\mathcal\{R\}\_\{q,k\}\(\\rho\)=\\frac\{1\}\{k\}\\E\\left\|\\mathcal\{K\}\_\{k\}\(G\)\\cap\\mathcal\{K\}\_\{k\}\\\!\\left\(\\rho G\+\\sqrt\{1\-\\rho^\{2\}\}H\\right\)\\right\|\.The nearest\-neighbor case ispq​\(ρ\)=ℛq,1​\(ρ\)p\_\{q\}\(\\rho\)=\\mathcal\{R\}\_\{q,1\}\(\\rho\), the probability that the two score vectors have the same smallest coordinate\. ForGρ=ρ​G\+1−ρ2​HG\_\{\\rho\}=\\rho G\+\\sqrt\{1\-\\rho^\{2\}\}H, define the minimum cells

Ai=\{x∈ℝq:xi=minjxj\},i=1,…,q\.A\_\{i\}=\\\{x\\in\\mathbb\{R\}^\{q\}:x\_\{i\}=\\min\_\{j\}x\_\{j\}\\\},\\qquad i=1,\\ldots,q\.Then

∑i=1qPr⁡\(G∈Ai,Gρ∈Ai\)=Pr⁡\(arg⁡mini​Gi=arg⁡mini​\(Gρ\)i\)\.\\sum\_\{i=1\}^\{q\}\\Pr\(G\\in A\_\{i\},\\,G\_\{\\rho\}\\in A\_\{i\}\)=\\Pr\\\!\\left\(\\arg\\min\_\{i\}G\_\{i\}=\\arg\\min\_\{i\}\(G\_\{\\rho\}\)\_\{i\}\\right\)\.\(7\)The sum over allqqcells is essential; one cell has probability smaller by a factor ofqqby symmetry\. Letϕρ\\phi\_\{\\rho\}be the standard bivariate\-normal density and letΦ¯ρ​\(x,y\)=Pr⁡\(Z1\>x,Z2\>y\)\\overline\{\\Phi\}\_\{\\rho\}\(x,y\)=\\Pr\(Z\_\{1\}\>x,Z\_\{2\}\>y\)be its joint survival function\. We also writeΦ¯​\(x\)=Pr⁡\(Z\>x\)\\overline\{\\Phi\}\(x\)=\\Pr\(Z\>x\)for the univariate standard\-normal survival function\. Conditioning on the common minimum gives

pq​\(ρ\)=q​∬ℝ2ϕρ​\(x,y\)​Φ¯ρ​\(x,y\)q−1​𝑑x​𝑑y\.p\_\{q\}\(\\rho\)=q\\iint\_\{\\mathbb\{R\}^\{2\}\}\\phi\_\{\\rho\}\(x,y\)\\overline\{\\Phi\}\_\{\\rho\}\(x,y\)^\{q\-1\}\\,dx\\,dy\.\(8\)Each remaining Gaussian pair must exceed both conditioned values\. By central symmetry the same integral may be written with the lower joint CDF after replacing the common minimum by a common maximum\.

###### Theorem 7\.2\(Gaussian score limit for fixed candidate count\)\.

Fixqqand1≤k<q1\\leq k<q\. Ifm→∞m\\to\\infty,d−m→∞d\-m\\to\\infty, andm/d→α∈\[0,1\]m/d\\to\\alpha\\in\[0,1\], then

𝔼⁡\|𝒩k∩𝒩~k\|k⟶ℛq,k​\(α\)\.\\E\\frac\{\\left\|\\mathcal\{N\}\_\{k\}\\cap\\widetilde\{\\mathcal\{N\}\}\_\{k\}\\right\|\}\{k\}\\longrightarrow\\mathcal\{R\}\_\{q,k\}\(\\sqrt\{\\alpha\}\)\.Fork=1k=1,

Pr\(𝒩1=𝒩~1\)=pq\(m/d\)\+Oq\(m−1/2\+\(d−m\)−1/2\)\.\\Pr\(\\mathcal\{N\}\_\{1\}=\\widetilde\{\\mathcal\{N\}\}\_\{1\}\)=p\_\{q\}\\\!\\left\(\\sqrt\{m/d\}\\right\)\+O\_\{q\}\\\!\\left\(m^\{\-1/2\}\+\(d\-m\)^\{\-1/2\}\\right\)\.In particular,pq​\(0\)=1/qp\_\{q\}\(0\)=1/qandℛq,k​\(0\)=k/q\\mathcal\{R\}\_\{q,k\}\(0\)=k/q\. Thus, for fixedq,kq,kandm/d→0m/d\\to 0, the probability that the nearest neighbors agree tends to1/q1/q, and the expected normalized top\-kkoverlap tends tok/qk/q\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) applies Bentkus’s multivariate Berry–Esseen bound for convex sets[Bentkus, 2003](https://arxiv.org/html/2609.02155#bib.bib39)to the independent coordinate sums forming the projected and omitted scores; becauseqqis fixed, summing over theqqdisjoint choices of common minimizer gives the statedOq\(m−1/2\+\(d−m\)−1/2\)O\_\{q\}\(m^\{\-1/2\}\+\(d\-m\)^\{\-1/2\}\)transfer\.

More generally, letRr:qR\_\{r:q\}be the rank of the second\-coordinate value paired with therrth ordered first\-coordinate value\. This paired value is the*concomitant*of therrth order statistic\. Then

ℛq,k\(ρ\)=1k∑r=1kPr\(Rr:q≤k\)\.\\mathcal\{R\}\_\{q,k\}\(\\rho\)=\\frac\{1\}\{k\}\\sum\_\{r=1\}^\{k\}\\Pr\(R\_\{r:q\}\\leq k\)\.The distribution of ranks in a finite sample is classical[David et al\., 1977](https://arxiv.org/html/2609.02155#bib.bib35)\. We reduce neighborhoods after random projection to these kernels at correlationm/d\\sqrt\{m/d\}, establish the finite\-dimensional transfer, and derive the top\-kklimit\.

Frieze and Jerrum derived the small\-correlation expansion of the same Gaussian common\-argmax kernel[Frieze and Jerrum, 1997](https://arxiv.org/html/2609.02155#bib.bib43)\. In common\-minimum notation it gives the following result; the proof, by differentiating[equation8](https://arxiv.org/html/2609.02155#S7.E8)atρ=0\\rho=0, appears in[sectionB](https://arxiv.org/html/2609.02155#S2a)\.

###### Proposition 7\.3\(Classical small\-correlation expansion\)\.

For fixedq≥2q\\geq 2,

pq​\(ρ\)=1q\+cq​ρ\+Oq​\(ρ2\),cq=q2​\(q−1\)​\[∫−∞∞ϕ​\(x\)2​Φ¯​\(x\)q−2​𝑑x\]2\.p\_\{q\}\(\\rho\)=\\frac\{1\}\{q\}\+c\_\{q\}\\rho\+O\_\{q\}\(\\rho^\{2\}\),\\qquad c\_\{q\}=q^\{2\}\(q\-1\)\\left\[\\int\_\{\-\\infty\}^\{\\infty\}\\phi\(x\)^\{2\}\\overline\{\\Phi\}\(x\)^\{q\-2\}\\,dx\\right\]^\{2\}\.In particular,c2=1/πc\_\{2\}=1/\\pi, recovering the small\-correlation expansion of Sheppard’s formula\. Hence

Pr⁡\(𝒩1=𝒩~1\)=1q\+cq​md\+Oq​\(md\+1m\+1d−m\)\.\\Pr\(\\mathcal\{N\}\_\{1\}=\\widetilde\{\\mathcal\{N\}\}\_\{1\}\)=\\frac\{1\}\{q\}\+c\_\{q\}\\sqrt\{\\frac\{m\}\{d\}\}\+O\_\{q\}\\\!\\left\(\\frac\{m\}\{d\}\+\\frac\{1\}\{\\sqrt\{m\}\}\+\\frac\{1\}\{\\sqrt\{d\-m\}\}\\right\)\.

### 7\.4The JL bound can hold while rankings collapse

[Section3](https://arxiv.org/html/2609.02155#S3)showed that the JL bound alone forces no retained geometry: an independent Gaussian replacement map can satisfy it\. The same separation also holds for a linear projection\. Although the pairwise law suggests that rankings degrade under thin projection, it does not show whether one fixed map can satisfy the JL bound on the same sample while its rankings collapse\. We prove that these events coexist\.

LetA=d/m​RA=\\sqrt\{d/m\}\\,R, whereRRhas Haar\-distributed orthonormal rows\. For distinctx,y,zx,y,z, define

sA​\(x,y,z\)=sgn⁡\[\(‖x−y‖2−‖x−z‖2\)​\(‖A⁡\(x−y\)‖2−‖A⁡\(x−z\)‖2\)\]\.s\_\{A\}\(x;y,z\)=\\operatorname\{sgn\}\\\!\\left\[\\bigl\(\\left\\lVert x\-y\\right\\rVert^\{2\}\-\\left\\lVert x\-z\\right\\rVert^\{2\}\\bigr\)\\bigl\(\\left\\lVert A\(x\-y\)\\right\\rVert^\{2\}\-\\left\\lVert A\(x\-z\)\\right\\rVert^\{2\}\\bigr\)\\right\]\.Fornndata points, the average Kendall correlation across queries is

τ¯n=1n​∑i=1n\(n−12\)−1​∑j<kj,k≠isA​\(Xi,Xj,Xk\),\\overline\{\\tau\}\_\{n\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\binom\{n\-1\}\{2\}^\{\-1\}\\sum\_\{\\begin\{subarray\}\{c\}j<k\\\\ j,k\\neq i\\end\{subarray\}\}s\_\{A\}\(X\_\{i\};X\_\{j\},X\_\{k\}\),whose expectation involves the single\-query constant

τm,d=2π​𝔼⁡arcsin⁡B,B∼Beta⁡\(m2,d−m2\):\\tau\_\{m,d\}=\\frac\{2\}\{\\pi\}\\E\\arcsin\\sqrt\{B\},\\qquad B\\sim\\mathrm\{Beta\}\\\!\\left\(\\frac\{m\}\{2\},\\frac\{d\-m\}\{2\}\\right\):by[theorem7\.1](https://arxiv.org/html/2609.02155#S7.Thmtheorem1),τm,d\\tau\_\{m,d\}is the expected Kendall correlation for one query under a rank\-mmHaar projection\.

###### Theorem 7\.4\(One map can satisfy the JL bound while rankings collapse\)\.

LetX1,…,Xn​∼i\.i\.d\.​𝒩​\(0,Id\)X\_\{1\},\\ldots,X\_\{n\}\\overset\{\\text\{i\.i\.d\.\}\}\{\\sim\}\\mathcal\{N\}\(0,I\_\{d\}\)independently ofAA, withn≥3n\\geq 3,0<m<d0<m<d,0<ε<10<\\varepsilon<1, and0<δ,η<10<\\delta,\\eta<1\.

1. \(i\)*Conditional concentration\.*Conditionally onAA,𝔼⁡\[τ¯n∣A\]=τm,d\\E\[\\overline\{\\tau\}\_\{n\}\\mid A\]=\\tau\_\{m,d\}and, fort\>0t\>0, Pr⁡\(\|τ¯n−τm,d\|\>t∣A\)≤2​exp⁡\(−⌊n/3⌋​t22\)\.\\Pr\\\!\\left\(\\left\|\\overline\{\\tau\}\_\{n\}\-\\tau\_\{m,d\}\\right\|\>t\\mid A\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{\\lfloor n/3\\rfloor t^\{2\}\}\{2\}\\right\)\.
2. \(ii\)*JL event\.*A universalC\>0C\>0exists such that, ifm≥C​ε−2​log⁡\(n/δ\)m\\geq C\\varepsilon^\{\-2\}\\log\(n/\\delta\), thenAAsatisfies theε\\varepsilon\-JL bound on the sample with probability at least1−δ1\-\\delta\.
3. \(iii\)*Simultaneous conclusion\.*With probability at least1−δ−η1\-\\delta\-\\eta, the JL event in part \(ii\) and τ¯n≤md\+2​log⁡\(2/η\)⌊n/3⌋\\overline\{\\tau\}\_\{n\}\\leq\\sqrt\{\\frac\{m\}\{d\}\}\+\\sqrt\{\\frac\{2\\log\(2/\\eta\)\}\{\\lfloor n/3\\rfloor\}\}hold simultaneously\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) symmetrizes the Kendall kernel and applies the blocking inequality of Hoeffding[Hoeffding, 1963](https://arxiv.org/html/2609.02155#bib.bib40)for bounded order\-three U\-statistics, partitioning the sample into disjoint triples to restore independence and give conditional concentration; a union bound gives the JL event\. Ifn→∞n\\to\\inftyandlog⁡n≪m≪d\\log n\\ll m\\ll d, the same sampled map can satisfy the JL bound for fixedε\\varepsilonwhileτ¯n→0\\overline\{\\tau\}\_\{n\}\\to 0in probability\.

Our results show that ranking agreement follows them/d\\sqrt\{m/d\}correlation scale, whereas the JL bound does not constrain it\. We next study clustering and estimation, which depend on how well a sketch preserves the ability to distinguish nearby distributions\.

## 8Covariance\-Shape Information

Distance rankings concern single\-sample observables\. Clustering and estimation instead ask how well projected data distinguish nearby distributions\. We use Fisher information to measure that local distinction and to remove overall scale before measuring covariance shape\.

For a regular parametric family with densitypθp\_\{\\theta\}, the Fisher information matrix is the second\-moment matrix of the score,

ℐ⁡\(θ\)=𝔼θ⁡\[∇θ​log​pθ​\(X\)​\(∇θ​log​pθ​\(X\)\)⊤\]\.\\mathcal\{I\}\(\\theta\)=\\E\_\{\\theta\}\\\!\\left\[\\nabla\_\{\\theta\}\\log p\_\{\\theta\}\(X\)\\bigl\(\\nabla\_\{\\theta\}\\log p\_\{\\theta\}\(X\)\\bigr\)^\{\\top\}\\right\]\.\(9\)Under the usual regularity conditions it also equals−𝔼θ⁡\[∇θ2​log⁡pθ​\(X\)\]\-\\E\_\{\\theta\}\[\\nabla\_\{\\theta\}^\{2\}\\log p\_\{\\theta\}\(X\)\]\. Fisher information gives the local quadratic approximation

DKL\(Pθ∥Pθ\+δ\)=12δ⊤ℐ\(θ\)δ\+o\(‖δ‖2\)D\_\{\\mathrm\{KL\}\}\(P\_\{\\theta\}\\,\\\|\\,P\_\{\\theta\+\\delta\}\)=\\frac\{1\}\{2\}\\delta^\{\\top\}\\mathcal\{I\}\(\\theta\)\\delta\+o\(\\left\\lVert\\delta\\right\\rVert^\{2\}\)[van der Vaart, 1998](https://arxiv.org/html/2609.02155#bib.bib44)\. It therefore measures local statistical distinguishability; through the Cramér–Rao bound, its inverse also controls the variance of regular estimators\.

When a parameter of interestϑ\\varthetais accompanied by a nuisance parameterζ\\zeta, the efficient information removes score variation explained by the nuisance direction\. If the nuisance block is nonsingular, the efficient information is the Schur complement

ℐeff=ℐϑ​ϑ−ℐϑ​ζ​ℐζ​ζ−1​ℐζ​ϑ\.\\mathcal\{I\}\_\{\\mathrm\{eff\}\}=\\mathcal\{I\}\_\{\\vartheta\\vartheta\}\-\\mathcal\{I\}\_\{\\vartheta\\zeta\}\\mathcal\{I\}\_\{\\zeta\\zeta\}^\{\-1\}\\mathcal\{I\}\_\{\\zeta\\vartheta\}\.\(10\)Equivalently, it is the information in the residual score after projecting out the span of the nuisance score\. This is the projection in score space anticipated in[section4\.4](https://arxiv.org/html/2609.02155#S4.SS4): the target space is spanned by scores rather than by features of a distance, and orthogonal projection again determines what the observation retains\.

### 8\.1Fisher information under projection

LetRRhave Haar\-distributed orthonormal rows and writeΠ=R⊤​R\\Pi=R^\{\\top\}R\. ForX∼𝒩⁡\(μ,σ2​Id\)X\\sim\\mathcal\{N\}\(\\mu,\\sigma^\{2\}I\_\{d\}\)observed through this known projection, the Fisher information for the mean is exactly

ℐμ​\(R​X\)=1σ2​Π\.\\mathcal\{I\}\_\{\\mu\}\(RX\)=\\frac\{1\}\{\\sigma^\{2\}\}\\,\\Pi\.\(11\)It is the identity on the observedmm\-space and zero on the kernel\. For a scalar submodelμ=θ​v\\mu=\\theta v, the retained fractionv⊤​Π​v/‖v‖2v^\{\\top\}\\Pi v/\\left\\lVert v\\right\\rVert^\{2\}isBeta⁡\(m2,d−m2\)\\mathrm\{Beta\}\(\\tfrac\{m\}\{2\},\\tfrac\{d\-m\}\{2\}\)\-distributed with meanm/dm/d, and the Cramér–Rao variance inflation in directionvvis its reciprocal\.

### 8\.2Mean, scale, and shape contraction

A local perturbation of a Gaussian component decomposes into a change of mean, a scalar change of log\-scale, and a traceless change of covariance shape\. To define shape independently of scale, considerΣζ,ϵ=eζ​\(Id\+ϵ​H\)\\Sigma\_\{\\zeta,\\epsilon\}=e^\{\\zeta\}\(I\_\{d\}\+\\epsilon H\)withtr⁡H=0\\tr H=0\. Hereζ\\zetacontrols overall scale andϵ\\epsilonthe magnitude of the traceless shape directionHH\. Treatingζ\\zetaas a nuisance parameter projects the shape scoreR​H​R⊤RHR^\{\\top\}away from the scale score, which is proportional toImI\_\{m\}\. The efficient shape score is therefore the traceless part ofR​H​R⊤RHR^\{\\top\},

R​H​R⊤−tr⁡\(R​H​R⊤\)m​Im\.RHR^\{\\top\}\-\\frac\{\\tr\(RHR^\{\\top\}\)\}\{m\}I\_\{m\}\.Haar averaging gives a separate contraction factor for each perturbation type\.

Table 2:Haar\-averaged fractions of local Gaussian Fisher information, equivalently of local Kullback–Leibler divergence\. The shape fraction is computed after eliminating unknown overall scale; unlike the log\-scale fraction, it varies across row spaces, and the table reports its Haar mean\.PerturbationRetained fractionDependence on row spaceMean directionm/dm/dBeta\-distributed around its meanScalar log\-scalem/dm/dDeterministicDiffuse traceless shape\(m−1\)​\(m\+2\)\(d−1\)​\(d\+2\)∼\(m/d\)2\\dfrac\{\(m\-1\)\(m\+2\)\}\{\(d\-1\)\(d\+2\)\}\\sim\(m/d\)^\{2\}Random; displayed fraction is the Haar mean

###### Theorem 8\.1\(Local contraction taxonomy\)\.

A Haar rank\-mmprojection retains the three expected fractions summarized in[Table2](https://arxiv.org/html/2609.02155#S8.T2); the shape row uses efficient Fisher information after eliminating the nuisance scaleζ\\zeta\. For any symmetric tracelessHH, the exact moment identity is

𝔼R⁡‖RHR⊤−tr⁡\(RHR⊤\)m​Im‖F2=\(m−1\)​\(m\+2\)\(d−1\)​\(d\+2\)​‖H‖F2\.\\E\_\{R\}\\left\\lVert RHR^\{\\top\}\-\\frac\{\\tr\(RHR^\{\\top\}\)\}\{m\}I\_\{m\}\\right\\rVert\_\{F\}^\{2\}=\\frac\{\(m\-1\)\(m\+2\)\}\{\(d\-1\)\(d\+2\)\}\\,\\left\\lVert H\\right\\rVert\_\{F\}^\{2\}\.

At the isotropic model, the unprojected efficient Fisher information forϵ\\epsilonis12​‖H‖F2\\tfrac\{1\}\{2\}\\left\\lVert H\\right\\rVert\_\{F\}^\{2\}, while the projected information is one half of the squared norm inside the expectation\. The Haar moment identity therefore gives the contraction factor for shape directly; the proof, based on second\-order Haar integration, appears in[sectionB](https://arxiv.org/html/2609.02155#S2a)\. A diffuse shape perturbation distributes its squared Frobenius norm across many eigendirections rather than concentrating it in a few spikes\. Such a perturbation loses information twice\. Projection removes coordinates and also reduces contrast within the retained coordinates\.[Figure6](https://arxiv.org/html/2609.02155#S9.F6)compares the exact constant with simulation\.

For two well\-separated Gaussian components with common isotropic covariance, the leading logarithm of the Bayes error is proportional to the squared distance between their means\. A Haar projection multiplies that exponent by the Beta\-distributed factor in[equation11](https://arxiv.org/html/2609.02155#S8.E11), which has meanm/dm/dand concentrates as both dimensions grow\. Dasgupta[Dasgupta, 1999](https://arxiv.org/html/2609.02155#bib.bib4)obtained logarithmic projection dimensions for learning separated mixtures\. Our local information rate is consistent with that result but is not a complete clustering guarantee\.

### 8\.3Compression toward sphericity and the spike exception

The local calculation describes infinitesimal changes\. To connect it with a global covariance, letA=d/m​RA=\\sqrt\{d/m\}\\,R, defineCA=A​Σ​A⊤C\_\{A\}=A\\Sigma A^\{\\top\}, putλ¯=tr⁡\(Σ\)/d\\bar\{\\lambda\}=\\tr\(\\Sigma\)/d, and setΔ=Σ−λ¯​I\\Delta=\\Sigma\-\\bar\{\\lambda\}I\. Then

CA−tr⁡Σm​Im=dm​R​Δ​R⊤\.C\_\{A\}\-\\frac\{\\tr\\Sigma\}\{m\}I\_\{m\}=\\frac\{d\}\{m\}R\\Delta R^\{\\top\}\.Standard bounds for random compression identify two dimensionless quantities that control convergence to a scalar matrix in operator norm[Dasgupta, 1999](https://arxiv.org/html/2609.02155#bib.bib4);[Dasgupta, 2000](https://arxiv.org/html/2609.02155#bib.bib5)\. The quantitym​‖Δ‖F/tr⁡Σ\\sqrt\{m\}\\,\\left\\lVert\\Delta\\right\\rVert\_\{F\}/\\tr\\Sigmacontrols the distributed anisotropic bulk: the square\-root factor reflects accumulation across many weak directions\. The quantitym​‖Δ‖op/tr⁡Σm\\,\\left\\lVert\\Delta\\right\\rVert\_\{\\mathrm\{op\}\}/\\tr\\Sigmacontrols the largest individual direction, for which no such averaging occurs\. Thus the compressed covariance approaches a scalar matrix in regimes where both quantities vanish\. The resulting rounding toward a scalar covariance is Dasgupta’s sphericalization phenomenon\. Dasgupta[Dasgupta, 1999](https://arxiv.org/html/2609.02155#bib.bib4);[Dasgupta, 2000](https://arxiv.org/html/2609.02155#bib.bib5)established the phenomenon for eccentric Gaussians, and Dasgupta, Hsu, and Verma[Dasgupta et al\., 2006](https://arxiv.org/html/2609.02155#bib.bib6)extended it to more general distributions\.

A sufficiently large spectral spike violates the operator\-norm condition and can remain visible after compression\. Its detection threshold depends on the population spectrum, sample size, and statistical task, so the rate derived for diffuse shape should not be applied to finite\-rank spikes without an additional model\.

The quadratic contraction completes the taxonomy: mean and scale contract atm/dm/d, diffuse traceless shape at order\(m/d\)2\(m/d\)^\{2\}, and a sufficiently large spike escapes the diffuse rate\. A known noiseless map can be row orthonormalized without changing its information, whereas estimators that use the output metric directly or invert noisy measurements remain sensitive to its singular spectrum\.

## 9General Maps: Rank, Spectrum, and Precision

Orthogonal projections lose information only by discarding directions: they are isometries on their retained row spaces\. A general linear map, by contrast, can also distort the geometry it keeps\. The relevant spectral summary depends on the downstream task\.[Table3](https://arxiv.org/html/2609.02155#S9.T3)previews the three cases\.

Table 3:Three downstream uses of a fixed known rank\-rrmapTT, withM=T⊤​TM=T^\{\\top\}Tand nonzero singular valuess1,…,srs\_\{1\},\\ldots,s\_\{r\}\. The first two rows takeZ∼𝒩⁡\(0,Id\)Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\); the third takesy=T​x\+ε​ηy=Tx\+\\varepsilon\\etafor independentx∼𝒩⁡\(0,Id\)x\\sim\\mathcal\{N\}\(0,I\_\{d\}\)andη∼𝒩⁡\(0,Im\)\\eta\\sim\\mathcal\{N\}\(0,I\_\{m\}\)\.Downstream useGoverning summaryExact lawOptimal nonlinear inferenceRankrrρHGR​\(‖Z‖2,T​Z\)=r/d\\rho\_\{\\mathrm\{HGR\}\}\(\\left\\lVert Z\\right\\rVert^\{2\};TZ\)=\\sqrt\{r/d\}Unwhitened squared\-norm estimateTrace ratior2​\(M\)r\_\{2\}\(M\)Corr⁡\(‖Z‖2,‖T​Z‖2\)=r2​\(M\)/d\\Corr\(\\left\\lVert Z\\right\\rVert^\{2\},\\left\\lVert TZ\\right\\rVert^\{2\}\)=\\sqrt\{r\_\{2\}\(M\)/d\}Inversion with additive noiseSpectrum near zeroMMSE⁡\(x∣T​x\+ε​η,T\)=d−∑i=1rsi2/\(si2\+ε2\)\\MMSE\(x\\mid Tx\+\\varepsilon\\eta,T\)=d\-\\sum\_\{i=1\}^\{r\}s\_\{i\}^\{2\}/\(s\_\{i\}^\{2\}\+\\varepsilon^\{2\}\)

### 9\.1The rank–spectrum–precision trichotomy

###### Theorem 9\.1\(Trichotomy\)\.

LetZ∼𝒩⁡\(0,Id\)Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\), letT∈ℝm×dT\\in\\mathbb\{R\}^\{m\\times d\}be a fixed known map of rankrrwith nonzero singular valuessis\_\{i\}, and writeD=‖Z‖2D=\\left\\lVert Z\\right\\rVert^\{2\},Q=‖T​Z‖2Q=\\left\\lVert TZ\\right\\rVert^\{2\}, andM=T⊤​TM=T^\{\\top\}T\.

1. \(i\)*Best\-possible inference is governed by rank alone:*ρHGR​\(D,T​Z\)=r/d\\rho\_\{\\mathrm\{HGR\}\}\(D;TZ\)=\\sqrt\{r/d\}, so for everyf∈L2f\\in L^\{2\},Var⁡\(𝔼⁡\[f⁡\(D\)∣TZ\]\)≤\(r/d\)​Var⁡\(f⁡\(D\)\)\\Var\(\\E\[f\(D\)\\mid TZ\]\)\\leq\(r/d\)\\Var\(f\(D\)\)\.
2. \(ii\)*The unwhitened squared\-norm estimate is governed by the spectrum:* Corr⁡\(D,Q\)=tr⁡Md​tr⁡\(M2\)=r2​\(M\)d,r2​\(M\)=\(tr⁡M\)2tr⁡\(M2\)\.\\Corr\(D,Q\)=\\frac\{\\tr M\}\{\\sqrt\{d\\,\\tr\(M^\{2\}\)\}\}=\\sqrt\{\\frac\{r\_\{2\}\(M\)\}\{d\}\},\\qquad r\_\{2\}\(M\)=\\frac\{\(\\tr M\)^\{2\}\}\{\\tr\(M^\{2\}\)\}\.Ifκ=smax/smin\\kappa=s\_\{\\max\}/s\_\{\\min\}over the nonzero singular values, then r​4​κ2\(κ2\+1\)2≤r2​\(M\)≤r\.r\\frac\{4\\kappa^\{2\}\}\{\(\\kappa^\{2\}\+1\)^\{2\}\}\\leq r\_\{2\}\(M\)\\leq r\.The lower bound is asymptotic to4​r/κ24r/\\kappa^\{2\}asκ→∞\\kappa\\to\\infty\.
3. \(iii\)*Recovery under additive noise is governed by the spectrum near zero:*ifx∼𝒩⁡\(0,Id\)x\\sim\\mathcal\{N\}\(0,I\_\{d\}\)andη∼𝒩⁡\(0,Im\)\\eta\\sim\\mathcal\{N\}\(0,I\_\{m\}\)are independent andy=T​x\+ε​ηy=Tx\+\\varepsilon\\eta, then trVar\(𝔼\[x∣y,T\]\)=∑i=1rsi2si2\+ε2,MMSE\(x∣y,T\)=d−∑i=1rsi2si2\+ε2\.\\tr\\Var\(\\E\[x\\mid y,T\]\)=\\sum\_\{i=1\}^\{r\}\\frac\{s\_\{i\}^\{2\}\}\{s\_\{i\}^\{2\}\+\\varepsilon^\{2\}\},\\qquad\\MMSE\(x\\mid y,T\)=d\-\\sum\_\{i=1\}^\{r\}\\frac\{s\_\{i\}^\{2\}\}\{s\_\{i\}^\{2\}\+\\varepsilon^\{2\}\}\.

The proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) treats the three parts separately\. Part \(i\) follows by orthonormalizing the rows ofTTas in[section4\.3](https://arxiv.org/html/2609.02155#S4.SS3)\. The singular value decomposition shows that observingT​ZTZis equivalent to observingrrcoordinates of a rotated standard Gaussian\. WithW=\(TT⊤\)†/2TW=\(TT^\{\\top\}\)^\{\\dagger/2\}T, one hasCorr⁡\(D,‖W​Z‖2\)=r/d\\Corr\(D,\\left\\lVert WZ\\right\\rVert^\{2\}\)=\\sqrt\{r/d\}\. IfTTis invertible, thenD=\(T​Z\)⊤​\(T​T⊤\)−1​\(T​Z\)D=\(TZ\)^\{\\top\}\(TT^\{\\top\}\)^\{\-1\}\(TZ\)exactly\.

Part \(ii\) analyzesQ=‖T​Z‖2Q=\\left\\lVert TZ\\right\\rVert^\{2\}without row\-orthonormalizingTT\. We bound its correlation withDDusing the Kantorovich inequality: for positivexi∈\[xmin,xmax\]x\_\{i\}\\in\[x\_\{\\min\},x\_\{\\max\}\],

\(∑i=1rxi\)2r​∑i=1rxi2≥4​xmin​xmax\(xmin\+xmax\)2\.\\frac\{\(\\sum\_\{i=1\}^\{r\}x\_\{i\}\)^\{2\}\}\{r\\sum\_\{i=1\}^\{r\}x\_\{i\}^\{2\}\}\\geq\\frac\{4x\_\{\\min\}x\_\{\\max\}\}\{\(x\_\{\\min\}\+x\_\{\\max\}\)^\{2\}\}\.Takingxi=si2x\_\{i\}=s\_\{i\}^\{2\}andxmax/xmin=κ2x\_\{\\max\}/x\_\{\\min\}=\\kappa^\{2\}yields the displayed trace\-ratio bound\.

In part \(iii\), we ask whether invertingTTremains stable under additive noise\. The factorsi2/\(si2\+ε2\)s\_\{i\}^\{2\}/\(s\_\{i\}^\{2\}\+\\varepsilon^\{2\}\)is the variance recovered in singular directioniiby the Gaussian posterior mean, or equivalently the Wiener\-filter gain\. Whensi≪εs\_\{i\}\\ll\\varepsilon, the recovered fraction in directioniiis negligible even if the map is invertible\. Invertibility alone does not imply that the output Euclidean metric preserves distances or that noisy inversion is stable\.

### 9\.2Gaussian\-map examples

Gaussian maps isolate reversible spectral distortion from rank loss\. A square i\.i\.d\. Gaussian map is full rank, yet its unwhitened centered\-distance correlation tends to1/21/\\sqrt\{2\}; row orthonormalization restores the Haar value\.[Figure6](https://arxiv.org/html/2609.02155#S9.F6)shows the one\-stage comparison\.

Figure 5:Local information contraction\. Mean and log\-scale directions retainm/dm/d; traceless shape retains\(m−1\)​\(m\+2\)/\(\(d−1\)​\(d\+2\)\)\(m\-1\)\(m\+2\)/\(\(d\-1\)\(d\+2\)\)\. Markers used=60d=60and1,5001\{,\}500Haar frames permm\.Figure 6:Correlation between original and mapped centered squared distances after one Haar or i\.i\.d\. Gaussian stage\. Markers use the chi\-square representation atd=200d=200, with150,000150\{,\}000samples permm\.
A single map exposes the distinction among rank loss, reversible spectral distortion, and instability under noise\. We next ask how multiple independent sketches change the available rank\.

## 10Ensembles

We now consider multiple independent sketches, which reduce the variability of a single sketch\. By stacking them, we obtain their information ceiling; by averaging them, we obtain a simple decoder whose finite\-size gap can be computed exactly\.

###### Theorem 10\.1\(Ensemble ceiling and averaging\)\.

LetA1,…,Ak∈ℝm×dA\_\{1\},\\dots,A\_\{k\}\\in\\mathbb\{R\}^\{m\\times d\}be sketches applied to the same data\.

1. \(i\)*Converse\.*Stacking gives one linear map of rank at mostp=min⁡\{k​m,d\}p=\\min\\\{km,d\\\}\. For any joint decoder, the recoverable centered\-distance variance is at mostαp​\(Σ\)\\alpha\_\{p\}\(\\Sigma\)\. In the isotropic case,ρHGR≤p/d\\rho\_\{\\mathrm\{HGR\}\}\\leq\\sqrt\{p/d\}, with equality for independent Gaussian blocks and the optimal joint decoder\.
2. \(ii\)*Explicit averaging decoder\.*If theAiA\_\{i\}are independent Gaussian maps and we average thekkrescaled squared distances they produce, then the correlation, jointly over the maps and data, is k​mk​m\+d\+2\.\\sqrt\{\\frac\{km\}\{km\+d\+2\}\}\.The ratio of this correlation to the HGR ceiling is γk,m,d=k​m​d\(k​m\+d\+2\)​min⁡\{k​m,d\}=\{d/\(k​m\+d\+2\),k​m≤d,k​m/\(k​m\+d\+2\),k​m≥d\.\\gamma\_\{k,m,d\}=\\sqrt\{\\frac\{km\\,d\}\{\(km\+d\+2\)\\min\\\{km,d\\\}\}\}=\\begin\{cases\}\\sqrt\{d/\(km\+d\+2\)\},&km\\leq d,\\\\ \\sqrt\{km/\(km\+d\+2\)\},&km\\geq d\.\\end\{cases\}

For the averaging decoder, the proof \([sectionB](https://arxiv.org/html/2609.02155#S2a)\) conditions on the standardized difference to obtain an estimate of the form‖Z‖2​C\\left\\lVert Z\\right\\rVert^\{2\}C, whereC∼χk​m2/\(k​m\)C\\sim\\chi^\{2\}\_\{km\}/\(km\)is independent ofZZ\. The resulting correlation is the exact effect of an independent multiplicative chi\-square fluctuation, including the finited\+2d\+2correction: averagingkksketches leaves the distance estimate intact and shrinks this fluctuation by a factork\\sqrt\{k\}in standard deviation\.

Independent sketches add rank, but they never exceed the rank\-k​mkmceiling\. The converse in part \(i\) is the stacked\-rank special case of[theorem6\.1](https://arxiv.org/html/2609.02155#S6.Thmtheorem1); the averaging identity is the single\-stage correlation of the concatenatedk​m×dkm\\times dGaussian map \([sectionB](https://arxiv.org/html/2609.02155#S2a)\)\. Simple averaging has the correct scaling and approaches this ceiling whenk​m≪dkm\\ll dork​m≫dkm\\gg d; its largest constant\-factor gap occurs neark​m≈dkm\\approx d, whereγk,m,d≈1/2\\gamma\_\{k,m,d\}\\approx 1/\\sqrt\{2\}\. Beforek​mkmreachesdd, added sketches expand the available rank; afterward, they only reduce distortion in the averaging decoder\. Correcting the joint metric whenk​m≤dkm\\leq d, or inverting the stacked map whenk​m≥dkm\\geq d, removes this reversible spectral distortion and reaches the isotropic ceiling\.

These identities are exact population statements\. We verify representative finite\-size claims in[section11](https://arxiv.org/html/2609.02155#S11)\.

## 11Numerical Validation

The preceding results include exact population identities, asymptotic limits, and probability statements at finiteddandmm\. We use numerical validation for two purposes: to check independent implementations of the closed\-form expressions and to measure how closely experiments at finiteddandmmfollow their limiting predictions\. We use exact Gaussian moments for polynomial identities, deterministic quadrature for integral formulas, and Monte Carlo sampling for stochastic claims at finiteddandmm\. We report one standard error for Monte Carlo estimates and Wilson95%95\\%intervals for frequencies of joint events\. These calculations support the formulas and their interpretation at finite dimensions; they do not replace the proofs\.

The independent Gaussian replacement experiment tests whether the JL bound distinguishes a genuine shared projection from a cloud that is sampled independently of the data\. It compares a normalized Haar projection, an i\.i\.d\. Gaussian map, and the independent Gaussian replacement map at the same\(n,d,m,ε\)\(n,d,m,\\varepsilon\)values\. Forn=100n=100,d=8192d=8192,m=1024m=1024, andε=0\.2\\varepsilon=0\.2, all3030Haar trials and all3030Gaussian\-map trials satisfied the JL bound, as did2828of3030replacement trials\. Atm/d=1/4m/d=1/4, the Pearson correlation of centered squared distances in[Figure1](https://arxiv.org/html/2609.02155#S3.F1)was0\.550\.55for the Haar projection and0\.010\.01for the replacement map; both displayed maps satisfied the same JL bound\.[Figure1](https://arxiv.org/html/2609.02155#S3.F1)reports the manuscript view, while the reproducibility repository records the full ranking, nearest\-neighbor, calibration, and disjoint\-pair diagnostics\.

Every calculation based on exact moments or quadrature in[Table4](https://arxiv.org/html/2609.02155#S11.T4)agrees with its reference value to the displayed precision, and every Monte Carlo estimate agrees within two standard errors\. Two rows require separate interpretation\. The quarter\-circle entry is the limiting mean of a posterior variance fraction\. The entry forr2r\_\{2\}is a deterministic equivalent formed from a ratio of moments, not an identity for a finite sample\.

Table 4:Numerical validation summary\. Monte Carlo \(MC\) estimates are estimate±\\pmone standard error; exact\-moment and quadrature checks have no sampling error\. Both isotropic mean\-square error rows are normalized byVar⁡\(D\)\\Var\(D\)\.ClaimReference valueComputed valueMethodIsotropicCorr⁡\(D,D~\)\\Corr\(D,\\widetilde\{D\}\)0\.22360\.2228±\\pm0\.0015MC, independent chi\-square split,N=400,000N=400\{,\}000Normalized minimum mean\-square error0\.95000\.9519±\\pm0\.0022MC, conditional mean,N=400,000N=400\{,\}000Centered estimation MSE /Var⁡\(D\)\\operatorname\{Var\}\(D\)19\.00019\.100±\\pm0\.053MC, rescaled projection,N=400,000N=400\{,\}000Quadratic canonical correlation atλ=2\\lambda\{=\}20\.9392390\.939239exact Gaussian momentsBeta–arcsinep5,50p\_\{5,50\}0\.598290\.59907±\\pm0\.00077MC, conditional Gaussian,N=400,000N=400\{,\}000Diffuse traceless covariance\-shapecontraction \(8/408/40\)0\.042740\.04297±\\pm0\.00018MC, Haar frames,N=3,000N=3\{,\}000One Gaussian stage \(200→200200\\to 200\)0\.705350\.70442±\\pm0\.00080MC, chi\-square stage,N=400,000N=400\{,\}000Gaussian chain \(300→150→100300\\to 150\\to 100\)0\.40580\.4050±\\pm0\.0013MC, independent chi\-square stages,N=400,000N=400\{,\}000Wishart𝔼⁡tr⁡\(M2\)\\E\\tr\(M^\{2\}\)243\.00243\.14±\\pm0\.38MC, Gaussian maps,N=3,000N=3\{,\}000Ratio\-of\-moments proxy vs\.Monte Carlo mean ofr2r\_\{2\}14\.814814\.8413±\\pm0\.0070MC; proxy is not an identity,N=3,000N=3\{,\}000Quarter\-circle mean posterior\-variance fraction \(ε=0\.2\\varepsilon\{=\}0\.2\)0\.1809980\.180998deterministic quadratureEnsemble average \(k​m=100,d=400km\{=\}100,d\{=\}400\)0\.446320\.44618±\\pm0\.00080MC, stacked Gaussian map,N=1,000,000N=1\{,\}000\{,\}000

[Table5](https://arxiv.org/html/2609.02155#S11.T5)validates the results for balanced blocks, the Gaussian common minimum, nearest neighbors, and JL–Kendall coexistence\. The calculation for balanced blocks uses exact moments to check, without Monte Carlo error, the degree\-two lower bound on canonical correlation and hence on nonlinear excess\. The nearest\-neighbor row compares a simulation at finiteddandmm,0\.1370200\.137020, with its Gaussian score limit,0\.1383250\.138325, atm=20m=20\. Here them−1/2m^\{\-1/2\}Berry–Esseen remainder can exceed the first\-order signal, so simulation provides the check at finiteddandmm\. The final row tests the coexistence phenomenon of[theorem7\.4](https://arxiv.org/html/2609.02155#S7.Thmtheorem4)\. Its joint rate,0\.9900\.990, is the empirical frequency with maximum sample distortion at most15%15\\%and mean Kendall correlation magnitude at most0\.10\.1\.

Table 5:Independent checks of the incorporated results\. Monte Carlo uncertainty is one standard error; the JL–Kendall coexistence event has Wilson95%95\\%interval\[0\.9710,0\.9966\]\[0\.9710,0\.9966\]\.Claim and settingPredictionComputationBalanced blocks,θ=0\.25\\theta=0\.25ρHGR=0\.5\\rho\_\{\\mathrm\{HGR\}\}=0\.5degree\-two CCA lower bound0\.5000000000000\.500000000000p8​\(20/104\)p\_\{8\}\(\\sqrt\{20/10^\{4\}\}\)integral in[equation8](https://arxiv.org/html/2609.02155#S7.E8)0\.1383249980\.138324998kNN,\(d,m,q\)=\(104,20,8\)\(d,m,q\)=\(10^\{4\},20,8\)Gaussian score limit0\.1383250\.1383250\.137020±0\.0005440\.137020\\pm 0\.000544JL–Kendall coexistence,\(n,d,m\)=\(100,106,2000\)\(n,d,m\)=\(100,10^\{6\},2000\)𝔼⁡τ=0\.028476\\E\\tau=0\.0284760\.028996±0\.0012540\.028996\\pm 0\.001254; joint rate0\.9900\.990

We interpret two checks in more detail because they reveal finite\-sample behavior that asymptotic notation can obscure\. First, we calculate exact Gaussian moments atλ=2\\lambda=2to reproduce the quadratic canonical correlation in[theorem6\.2](https://arxiv.org/html/2609.02155#S6.Thmtheorem2)\. We then sweep the polynomial canonical correlation ofDλ=λ​G12\+G22D\_\{\\lambda\}=\\lambda G\_\{1\}^\{2\}\+G\_\{2\}^\{2\}andUλ=λ​G12U\_\{\\lambda\}=\\lambda G\_\{1\}^\{2\}to produce[Figure4](https://arxiv.org/html/2609.02155#S7.F4)\. Degree one agrees withα1\\sqrt\{\\alpha\_\{1\}\}, while nested degree\-two through degree\-four spaces yield larger lower bounds away from isotropy\. These values concern one observation and finite polynomial classes; they neither evaluate unrestricted HGR nor optimize the observed subspace\.

Second, the rows for Gaussian stages in[Table4](https://arxiv.org/html/2609.02155#S11.T4)distinguish an exact correlation averaged over map and data randomness from a deterministic equivalent for a typical map\. We compare one\- and two\-stage simulations with the finite products in[theoremA\.1](https://arxiv.org/html/2609.02155#S1.Thmtheorem1), including their\+2\+2corrections\. A separate Wishart experiment checks𝔼⁡tr⁡\(M2\)=d⁡\(m\+d\+1\)/m\\E\\tr\(M^\{2\}\)=d\(m\+d\+1\)/m\. By contrast,m​d/\(m\+d\+1\)md/\(m\+d\+1\)is a ratio of trace moments, not𝔼⁡\[r2\]\\E\[r\_\{2\}\]; the adjacent row records the finite\-sample difference rather than treating the proxy as an identity\.

Having checked the population formulas and their finite\-dimensional approximations, we turn to their practical implications\.

## 12Discussion: Implications for Practice

The distinct preservation laws imply different responses in practice\. Reranking repairs a coarse neighbor stage, task alignment changes what information matters, and independent sketches trade added rank against distortion in an unwhitened estimate\.

#### Candidate generation and reranking

Locality\-sensitive hashing and compressed indexes can support a coarse candidate stage[Indyk and Motwani, 1998](https://arxiv.org/html/2609.02155#bib.bib26);[Charikar, 2002](https://arxiv.org/html/2609.02155#bib.bib27)\.[Theorem7\.2](https://arxiv.org/html/2609.02155#S7.Thmtheorem2)explains why evaluating a short list at full precision can still matter: at fixedqq, the projected top choice approaches an independent uniform choice whenm/d→0m/d\\to 0\. This theorem does not prescribe an engineering threshold because real margins, candidate counts, and data distributions differ from the Gaussian benchmark\. It does replace a pairwise heuristic with a complete ranking law for a fixed number of candidates\.

#### Objectives governed by the baseline rather than fluctuations

Subspace embeddings, sketched regression, and randomized low\-rank approximation target residual norms or dominant subspaces rather than the ordering of nearly equal within\-cloud distances[Halko et al\., 2011](https://arxiv.org/html/2609.02155#bib.bib19)\. Randomized singular value decomposition is designed to retain spectral spikes, not diffuse anisotropy\. Its success is therefore compatible with the recovery limits derived here\.

#### Coding and task alignment

Product quantization changes the resource from output dimension to a finite bit rate[Jégou et al\., 2011a](https://arxiv.org/html/2609.02155#bib.bib24)\. For a Gaussian source,*reverse water\-filling*assigns rate only to covariance modes above a distortion threshold and allocates more rate to larger variances[Cover and Thomas, 2006](https://arxiv.org/html/2609.02155#bib.bib33)\. Learned rotations can then redistribute distortion across coordinates[Ge et al\., 2013](https://arxiv.org/html/2609.02155#bib.bib25)\. Supervised nested\-representation training, often called*Matryoshka training*, takes a different route\. It trains each leading coordinate block to remain predictive, so label\-relevant information appears early in the representation[Kusupati et al\., 2022](https://arxiv.org/html/2609.02155#bib.bib31)\. Both approaches add assumptions absent from an oblivious rank\-mmprojection\. The relevant resource is task information, not total within\-cloud distance recovery\.

#### Cannings–Samworth ensembles

Cannings and Samworth[Cannings and Samworth, 2017](https://arxiv.org/html/2609.02155#bib.bib28)aggregate classifiers trained on multiple random projections\. Our population calculation isolates the geometric benefit of the parallel sketches: beforek​m=dkm=d, more sketches raise both rank and averaging accuracy; afterward, they improve only the chosen estimate \([theorem10\.1](https://arxiv.org/html/2609.02155#S10.Thmtheorem1)\)\. Related cluster ensembles use the same parallel strategy[Fern and Brodley, 2003](https://arxiv.org/html/2609.02155#bib.bib29)\. Task gains still depend on margins and downstream learning\.

#### Limits of transfer

These practical responses rely on exact Gaussian laws whose transfer beyond the benchmark requires care\. Gaussianity makes the chi\-square channel and score covariance exact\. The relative\-error criterion in[proposition2\.1](https://arxiv.org/html/2609.02155#S2.Thmtheorem1)is distribution\-free, and the proof mechanisms suggest extensions under invariance principles or elliptical models, but the constants need not survive\. Aligned anisotropy is now covered by[theorem6\.3](https://arxiv.org/html/2609.02155#S6.Thmtheorem3); noncommuting maps remain open\. Fixed\-qqneighbor overlap is solved for isotropic Gaussian data and an independent orthogonal projection, while growing neighborhoods, hubness, density estimates, and non\-Gaussian universality require a theory for distances that share a query\.

## 13Research Directions

The operator toolkit developed here—conditional\-expectation channels, singular systems, and sharp Gaussian limits—extends to settings the scalar isotropic channel does not directly reach\. This section formulates the resulting challenges as precise problems, each anchored to a theorem or conjecture the framework already produces\.

###### Research Direction 13\.1\(General anisotropic maximal correlation\)\.

ForD=∑iλi​Gi2D=\\sum\_\{i\}\\lambda\_\{i\}G\_\{i\}^\{2\}observed through a rank\-mmmap, determineρHGR​\(D,𝒪\)\\rho\_\{\\mathrm\{HGR\}\}\(D;\\mathcal\{O\}\)and the optimizing observation\. We solve the problem for commuting projectors with balanced spectral retention in[theorem6\.3](https://arxiv.org/html/2609.02155#S6.Thmtheorem3), which also bounds every commuting block allocation\.[Theorem6\.2](https://arxiv.org/html/2609.02155#S6.Thmtheorem2)shows that an unbalanced allocation can exceedαm\\sqrt\{\\alpha\_\{m\}\}\. For a noncommuting map, the observed quadratic form no longer splits along covariance eigenspaces, preventing direct use of the blockwise beta–gamma reduction or its tensorization\. The unrestricted problem couples a weighted\-gamma conditional\-expectation operator with an optimization over row spaces\.

###### Research Direction 13\.2\(Uniform concomitant asymptotics and growing top\-kksets\)\.

For fixedρ∈\(0,1\)\\rho\\in\(0,1\), Gaussian plurality stability measures the probability that two correlated Gaussian score vectors select the same extremal coordinate\. The corresponding literature gives the classical asymptotic[Khot et al\., 2007](https://arxiv.org/html/2609.02155#bib.bib37);[de Klerk et al\., 2004](https://arxiv.org/html/2609.02155#bib.bib38)

pq\(ρ\)∼Γ​\(1/\(1\+ρ\)\)21−ρ2\(q−1\)−\(1−ρ\)/\(1\+ρ\)\(4πlog\(q−1\)\)−ρ/\(1\+ρ\)\.p\_\{q\}\(\\rho\)\\sim\\frac\{\\Gamma\(1/\(1\+\\rho\)\)^\{2\}\}\{\\sqrt\{1\-\\rho^\{2\}\}\}\(q\-1\)^\{\-\(1\-\\rho\)/\(1\+\\rho\)\}\\bigl\(4\\pi\\log\(q\-1\)\\bigr\)^\{\-\\rho/\(1\+\\rho\)\}\.When the correlation varies withqq, existing uniform Gaussian\-tail control and Borell’s bound imply[Khot et al\., 2007](https://arxiv.org/html/2609.02155#bib.bib37)

lim supq→∞q​pq​\(ρq\)≤e2​λwhenρq​log⁡q→λ∈\[0,∞\)\.\\limsup\_\{q\\to\\infty\}q\\,p\_\{q\}\(\\rho\_\{q\}\)\\leq e^\{2\\lambda\}\\qquad\\text\{when\}\\qquad\\rho\_\{q\}\\log q\\to\\lambda\\in\[0,\\infty\)\.A matching lower bound, ideally with a uniform error estimate, remains open in this triangular regime, whereq→∞q\\to\\inftyandρq​log⁡q→λ\\rho\_\{q\}\\log q\\to\\lambda\. The caseλ=0\\lambda=0already follows from the upper bound andpq​\(ρ\)≥1/qp\_\{q\}\(\\rho\)\\geq 1/qforρ≥0\\rho\\geq 0\. More generally, determine overlap whenqq,kk, andρ−1\\rho^\{\-1\}grow jointly\. The goal is to establish a sharp triangular\-regime and top\-kkextension of the Gaussian stability kernel\. Deterministic ordinal capacity and the corresponding Gaussian\-cloud conjecture are recorded in[theoremsD\.1](https://arxiv.org/html/2609.02155#S4.Thmtheorem1)and[D\.2](https://arxiv.org/html/2609.02155#S4.Thmtheorem2)\.

###### Conjecture 13\.3\(Thin\-compression \(m/d→0m/d\\to 0\) spike phase diagram\)\.

Considerm/d→0m/d\\to 0with centered covariance variation spread across many eigendirections and with no dominant eigenvalue\. First, identify conditions under which the normalized compressed traceless bulk has a universal limiting spectrum\. Second, determine when a finite\-rank population spike becomes distinguishable from that bulk\. A semicircle transition is plausible only under additional assumptions\. Under*free compression*—the free\-probability model for compression by a generic random projection—the compressed spectral law still depends on the population law\. For example, compressingσ2​I\+λ​v​v⊤\\sigma^\{2\}I\+\\lambda vv^\{\\top\}produces a scalar matrix plus rank one, with no population\-level random bulk\. A detection threshold must therefore depend jointly on projection dimension, sample size, and covariance, as in deformed random\-matrix models, which study random spectral bulks perturbed by low\-rank structure[Baik et al\., 2005](https://arxiv.org/html/2609.02155#bib.bib32)\.

###### Research Direction 13\.4\(Growing\-neighborhood statistics\)\.

Determine the leading components of density, hubness\-magnitude, and intrinsic\-dimension estimators when the number of distances sharing a query grows\. Here*hubness*is the tendency of a few points to be nearest neighbors of many queries[Radovanović et al\., 2010](https://arxiv.org/html/2609.02155#bib.bib30); hub magnitude counts how often this occurs, whereas hub identity records which points become hubs\. Although[theorem7\.2](https://arxiv.org/html/2609.02155#S7.Thmtheorem2)resolves fixed\-qqtop\-kkoverlap, the single\-distance Laguerre decomposition in[theorem5\.2](https://arxiv.org/html/2609.02155#S5.Thmtheorem2)does not tensorize across a shared query\. A complete theory of these statistics must therefore cover non\-Gaussian score limits and distinguish changes in hub magnitude from changes in hub identity\.

###### Research Direction 13\.5\(Supervised task\-recovery limit\)\.

Defineαmtask\\alpha\_\{m\}^\{\\mathrm\{task\}\}as the Fisher information about a task parameter retained under the best rank\-mmlinear map\. We seek to determine when supervised training can makeαmtask\\alpha\_\{m\}^\{\\mathrm\{task\}\}close to one at smallmmwhile total\-covariance recovery remains small\. This includes objectives that train nested prefixes of a representation to remain predictive, such as Matryoshka\-style training[Kusupati et al\., 2022](https://arxiv.org/html/2609.02155#bib.bib31)\. Characterize the resulting trade\-off with nuisance geometry\.

## 14Conclusion

Random projections do not preserve a single, undifferentiated notion of geometry\. On the Gaussian benchmark, the retention laws reviewed in[Table1](https://arxiv.org/html/2609.02155#S4.T1)share one parameter, the rank ratiom/dm/d, yet act on different scales: a variance fraction for distance features, a correlation for their signs, and a squared ratio for diffuse shape\. Under general covariance,αm​\(Σ\)\\alpha\_\{m\}\(\\Sigma\)replacesm/dm/dfor the distance value, and sign statistics inherit the associated correlation scale, so neighborhoods with a fixed number of candidates approach chance asm/d→0m/d\\to 0\.

The differences among these scales have direct consequences\. Because shape contracts faster than mean and scale, compression sphericalizes distributed anisotropy while concentrated spikes can remain visible\. Because rankings depend on the correlation scale, a projection can satisfy the JL bound on a finite sample while its mean ranking correlation vanishes—and the replacement\-map construction shows the bound is compatible with output entirely independent of the data\. The JL bound alone therefore does not force data\-dependent geometry\.

For a general known map, rank governs optimal decoding, spectral spread governs an unwhitened squared\-norm estimate, and the smallest singular values govern noisy inversion\. Multiple independent sketches can raise the combined rank, but only up to the ambient dimension\. These exact Gaussian laws show where reranking, metric correction, or additional sketches are necessary\. The same conditional\-expectation toolkit extends beyond the Gaussian benchmark;[section13](https://arxiv.org/html/2609.02155#S13)develops the resulting research directions, from anisotropic maximal correlation and growing neighborhoods to compressed covariance phase diagrams and supervised task recovery\.

## Acknowledgments

This work was supported by the Applied Mathematics program of the U\.S\. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research \(ASCR\), through the SPARSITUTE Mathematical Multifaceted Integrated Capability Center \(MMICC\),*A Mathematical Institute for Sparse Computations in Science and Engineering*\([sparsitute\.lbl\.gov](https://sparsitute.lbl.gov/)\)\. We thank David Rabson, ASCR program manager; Ramakrishnan Kannan, acting director of the SPARSITUTE MMICC; and Michael L\. Parks, the Oak Ridge National Laboratory point of contact for ASCR Applied Mathematics, for their leadership and support\.

## AGaussian Chains and Hard\-Edge Precision

Hanin and Nica[Hanin and Nica, 2020](https://arxiv.org/html/2609.02155#bib.bib21)showed that the harmonic sumHL=∑ℓ=1Lnℓ−1H\_\{L\}=\\sum\_\{\\ell=1\}^\{L\}n\_\{\\ell\}^\{\-1\}of inverse layer widths governs norm fluctuations in long random\-matrix products applied to a fixed vector\. For a random Gaussian input, we add the input\-fluctuation termn0−1=d−1n\_\{0\}^\{\-1\}=d^\{\-1\}\. The spectrum law in[theorem9\.1](https://arxiv.org/html/2609.02155#S9.Thmtheorem1)\(ii\) then gives the following exact finite\-chain identity\.

###### Theorem A\.1\(Gaussian chains\)\.

LetPL=GL⋯G1P\_\{L\}=G\_\{L\}\\cdots G\_\{1\}be a chain of independent Gaussian stagesGℓ∈ℝnℓ×nℓ−1G\_\{\\ell\}\\in\\mathbb\{R\}^\{n\_\{\\ell\}\\times n\_\{\\ell\-1\}\}with entriesN⁡\(0,1/nℓ\)N\(0,1/n\_\{\\ell\}\), wheren0=dn\_\{0\}=d\. Apply the chain toZ∼𝒩⁡\(0,2​σ2​Id\)Z\\sim\\mathcal\{N\}\(0,2\\sigma^\{2\}I\_\{d\}\)\. With correlation taken jointly overZZand the stages,

Corr2⁡\(‖Z‖2,‖PL​Z‖2\)=2/d∏ℓ=0L\(1\+2/nℓ\)−1\\Corr^\{2\}\\bigl\(\\left\\lVert Z\\right\\rVert^\{2\},\\left\\lVert P\_\{L\}Z\\right\\rVert^\{2\}\\bigr\)=\\frac\{2/d\}\{\\prod\_\{\\ell=0\}^\{L\}\(1\+2/n\_\{\\ell\}\)\-1\}at every finite size\. A single stage of widthmmtherefore givesCorr=m/\(m\+d\+2\)\\Corr=\\sqrt\{m/\(m\+d\+2\)\}\. For a typical sampled map,

r2​\(PL⊤​PL\)=\(1\+oℙ​\(1\)\)​\(∑ℓ=0L1nℓ\)−1\.r\_\{2\}\(P\_\{L\}^\{\\top\}P\_\{L\}\)=\(1\+o\_\{\\mathbb\{P\}\}\(1\)\)\\left\(\\sum\_\{\\ell=0\}^\{L\}\\frac\{1\}\{n\_\{\\ell\}\}\\right\)^\{\-1\}\.For one stage, the deterministic equivalent is\(1/m\+1/d\)−1\(1/m\+1/d\)^\{\-1\}\. The finite ratio of moments ism​d/\(m\+d\+1\)md/\(m\+d\+1\)because𝔼⁡tr⁡M=d\\E\\tr M=dand𝔼⁡tr⁡M2=d⁡\(m\+d\+1\)/m\\E\\tr M^\{2\}=d\(m\+d\+1\)/m\.

Conditional on its input, each stage multiplies squared norm by an independentχnℓ2/nℓ\\chi^\{2\}\_\{n\_\{\\ell\}\}/n\_\{\\ell\}factor, so relative second moments multiply\. The finite identity concerns the joint law of stages and input, whereas ther2r\_\{2\}statement concerns a typical fixed map asymptotically\. The verification in[section11](https://arxiv.org/html/2609.02155#S11)distinguishes the exact identity from its deterministic equivalent\.

The polar decomposition factors one Gaussian stage into a Haar\-distributed row\-orthonormal factor and an independent Wishart factor\. The first imposes the rank bottleneck; the second adds a multiplicativeχd2/d\\chi\_\{d\}^\{2\}/dnorm fluctuation\. Their product has the fullχm2/m\\chi\_\{m\}^\{2\}/mfluctuation\. Thus a square Gaussian stage is full rank but has unwhitened correlationd/\(2​d\+2\)→1/2\\sqrt\{d/\(2d\+2\)\}\\to 1/\\sqrt\{2\}\. In contrast, a square orthogonal stage does not distort Euclidean distance\. ForLLsquare Gaussian stages of widthnn, the Hanin–Nica harmonic sum contributesL/nL/nand the random input contributes1/n1/n\. Hencer2∼n/\(L\+1\)r\_\{2\}\\sim n/\(L\+1\)and correlation tends to1/L\+11/\\sqrt\{L\+1\}\.

Sequential composition differs from parallel concatenation\. Concatenatingkkindependentmm\-row sketches gives1/r2∼1/d\+1/\(k​m\)1/r\_\{2\}\\sim 1/d\+1/\(km\), as in[theorem10\.1](https://arxiv.org/html/2609.02155#S10.Thmtheorem1)\. The chain equivalent is specific to the i\.i\.d\. Gaussian stages considered above and to ensembles with the same limiting trace moments; structured transforms can have other spectral laws\. Moreover,r2r\_\{2\}contains no singular\-vector information, so an anisotropic diagnostic also needs an alignment quantity such as

ρΣ​\(T\)2=\[tr⁡\(M​Σ2\)\]2tr⁡\(Σ2\)​tr⁡\(M​Σ​M​Σ\)\.\\rho\_\{\\Sigma\}\(T\)^\{2\}=\\frac\{\[\\tr\(M\\Sigma^\{2\}\)\]^\{2\}\}\{\\tr\(\\Sigma^\{2\}\)\\tr\(M\\Sigma M\\Sigma\)\}\.
### A\.1Precision and the hard edge

Marchenko and Pastur[Marchenko and Pastur, 1967](https://arxiv.org/html/2609.02155#bib.bib22)derived the limiting law that, for a normalized square Gaussian map, gives the quarter\-circle singular\-value density

ρ⁡\(s\)=1π​4−s2,0≤s≤2\.\\rho\(s\)=\\frac\{1\}\{\\pi\}\\sqrt\{4\-s^\{2\}\},\\qquad 0\\leq s\\leq 2\.The origin is the*hard edge*: singular values are constrained to be nonnegative, and the limiting density remains nonzero there\. Under the additive\-noise model in[theorem9\.1](https://arxiv.org/html/2609.02155#S9.Thmtheorem1)\(iii\), the fraction of directions with signal\-to\-noise ratio below one is approximately\(2/π\)​ε\(2/\\pi\)\\varepsilon, while the average posterior loss has the exact limit

1d​MMSE⁡\(x∣y,T\)⟶ψedge​\(ε\)=ε2​\(ε2\+4−ε\)=ε−ε22\+O⁡\(ε3\)\.\\frac\{1\}\{d\}\\MMSE\(x\\mid y,T\)\\longrightarrow\\psi\_\{\\mathrm\{edge\}\}\(\\varepsilon\)=\\frac\{\\varepsilon\}\{2\}\\left\(\\sqrt\{\\varepsilon^\{2\}\+4\}\-\\varepsilon\\right\)=\\varepsilon\-\\frac\{\\varepsilon^\{2\}\}\{2\}\+O\(\\varepsilon^\{3\}\)\.Edelman[Edelman, 1988](https://arxiv.org/html/2609.02155#bib.bib23)showed thatsmin=Θℙ​\(1/d\)s\_\{\\min\}=\\Theta\_\{\\mathbb\{P\}\}\(1/d\)after normalization\. Thus, ifε≈2−b\\varepsilon\\approx 2^\{\-b\}, recovering every direction requiresb≳log2⁡db\\gtrsim\\log\_\{2\}d\. The average unrecovered fraction is instead approximately2−b2^\{\-b\}, independent ofdd\. These statements calibrate additive Gaussian noise; floating\-point roundoff is not itself isotropic additive noise\.

## BProofs

Throughout, letZ=X−X′Z=X\-X^\{\\prime\}, soZ∼𝒩⁡\(0,2​Σ\)Z\\sim\\mathcal\{N\}\(0,2\\Sigma\)andD=‖Z‖2D=\\left\\lVert Z\\right\\rVert^\{2\}\.

### B\.1Proof of[proposition3\.4](https://arxiv.org/html/2609.02155#S3.Thmtheorem4)

Letr=⌊n/2⌋r=\\lfloor n/2\\rflooras in[proposition3\.4](https://arxiv.org/html/2609.02155#S3.Thmtheorem4)\. For the disjoint pairs\(2​ℓ−1,2​ℓ\)\(2\\ell\-1,2\\ell\), define

Rℓ=D2​ℓ−1,2​ℓrepD2​ℓ−1,2​ℓ\.R\_\{\\ell\}=\\frac\{D\_\{2\\ell\-1,2\\ell\}^\{\\mathrm\{rep\}\}\}\{D\_\{2\\ell\-1,2\\ell\}\}\.The variablesR1,…,RrR\_\{1\},\\ldots,R\_\{r\}are i\.i\.d\., and

Rℓ​=𝑑​χm2/mχd2/d∼Fm,d\.R\_\{\\ell\}\\overset\{d\}\{=\}\\frac\{\\chi\_\{m\}^\{2\}/m\}\{\\chi\_\{d\}^\{2\}/d\}\\sim F\_\{m,d\}\.LetU=χm2/mU=\\chi\_\{m\}^\{2\}/mandV=χd2/dV=\\chi\_\{d\}^\{2\}/dbe independent\. Chen and Rubin[Chen and Rubin, 1986](https://arxiv.org/html/2609.02155#bib.bib45)showed that the median of a gamma variable is smaller than its mean, soPr⁡\(V≤1\)≥1/2\\Pr\(V\\leq 1\)\\geq 1/2\. Moreover, the Zhang–Zhou lower bound for theχ2\\chi^\{2\}upper\-tail probability[Zhang and Zhou, 2020](https://arxiv.org/html/2609.02155#bib.bib46), Cor\. 3gives, uniformly for0<ε≤10<\\varepsilon\\leq 1,

Pr⁡\(U≥1\+ε\)≥c0​e−C0​m​ε2\.\\Pr\(U\\geq 1\+\\varepsilon\)\\geq c\_\{0\}e^\{\-C\_\{0\}m\\varepsilon^\{2\}\}\.The event on the left together withV≤1V\\leq 1impliesU/V≥1\+εU/V\\geq 1\+\\varepsilon\. Thus, if

pm,drep​\(ε\)=Pr⁡\(Fm,d∉\[1−ε,1\+ε\]\),p^\{\\mathrm\{rep\}\}\_\{m,d\}\(\\varepsilon\)=\\Pr\\\!\\left\(F\_\{m,d\}\\notin\[1\-\\varepsilon,1\+\\varepsilon\]\\right\),thenpm,drep​\(ε\)≥c​e−C​m​ε2p^\{\\mathrm\{rep\}\}\_\{m,d\}\(\\varepsilon\)\\geq ce^\{\-Cm\\varepsilon^\{2\}\}\. The JL event implies that every disjoint\-pair ratio lies in the prescribed interval, hence

Pr⁡\(ℰεrep\)≤\(1−pm,drep​\(ε\)\)r≤exp⁡\(−c​r​e−C​m​ε2\)\.\\Pr\(\\mathcal\{E\}\_\{\\varepsilon\}^\{\\mathrm\{rep\}\}\)\\leq\\bigl\(1\-p^\{\\mathrm\{rep\}\}\_\{m,d\}\(\\varepsilon\)\\bigr\)^\{r\}\\leq\\exp\\\!\\left\(\-cre^\{\-Cm\\varepsilon^\{2\}\}\\right\)\.IfPr⁡\(ℰεrep\)≥1−δ\\Pr\(\\mathcal\{E\}\_\{\\varepsilon\}^\{\\mathrm\{rep\}\}\)\\geq 1\-\\delta, taking logarithms and rearranging proves the displayed necessary condition in[proposition3\.4](https://arxiv.org/html/2609.02155#S3.Thmtheorem4)\. Finally,−log⁡\(1−δ\)≤2​δ\-\\log\(1\-\\delta\)\\leq 2\\deltaforδ≤1/2\\delta\\leq 1/2, which gives the stated order\. ∎

### B\.2Moment matching for the replacement cloud

In the setting of[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1), letNp=\(n2\)N\_\{p\}=\\binom\{n\}\{2\}andaε=ε/\(2\+ε\)a\_\{\\varepsilon\}=\\varepsilon/\(2\+\\varepsilon\)\. The Gaussian replacement cloud matches the population mean squared distance but inflates its variance:Var⁡\(Di​jrep\)=8​σ4​d2/m\\Var\(D\_\{ij\}^\{\\mathrm\{rep\}\}\)=8\\sigma^\{4\}d^\{2\}/m, whereasVar⁡\(Di​j\)=8​σ4​d\\Var\(D\_\{ij\}\)=8\\sigma^\{4\}d\. The replacement map satisfies the JL bound through concentration rather than moment matching\. More generally, if two distance families have common meanμD\\mu\_\{D\}and variances bounded byvXv\_\{X\}andvYv\_\{Y\}, Chebyshev’s inequality and a union bound give

Pr⁡\(failure\)≤Np​\(vX\+vY\)aε2​μD2\.\\Pr\(\\text\{failure\}\)\\leq\\frac\{N\_\{p\}\(v\_\{X\}\+v\_\{Y\}\)\}\{a\_\{\\varepsilon\}^\{2\}\\mu\_\{D\}^\{2\}\}\.For the two Gaussian clouds,

vXμD2=2d,vYμD2=2m,Pr⁡\(failure\)≤2​Npaε2​\(1d\+1m\)\.\\frac\{v\_\{X\}\}\{\\mu\_\{D\}^\{2\}\}=\\frac\{2\}\{d\},\\qquad\\frac\{v\_\{Y\}\}\{\\mu\_\{D\}^\{2\}\}=\\frac\{2\}\{m\},\\qquad\\Pr\(\\text\{failure\}\)\\leq\\frac\{2N\_\{p\}\}\{a\_\{\\varepsilon\}^\{2\}\}\\left\(\\frac\{1\}\{d\}\+\\frac\{1\}\{m\}\\right\)\.Chebyshev control alone therefore requiresmin⁡\{m,d\}=Ω⁡\(n2/\(ε2​δ\)\)\\min\\\{m,d\\\}=\\Omega\(n^\{2\}/\(\\varepsilon^\{2\}\\delta\)\)\. The logarithmic dimension in[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1)comes from sub\-exponential concentration, not merely from the first two moments\. Exact matching of those moments imposes a different dimensional obstruction\.

###### Proposition B\.1\(Exact first\-two\-moment matching requires half dimension\)\.

LetY,Y′Y,Y^\{\\prime\}be i\.i\.d\. random vectors inℝm\\mathbb\{R\}^\{m\}with finite fourth moments and covarianceCC\. Then

𝔼⁡‖Y−Y′‖2=2​tr⁡C\\E\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}=2\\tr Cand

Var⁡\(‖Y−Y′‖2\)=2​Var⁡\(‖Y−𝔼⁡Y‖2\)\+4​tr⁡\(C2\)\.\\Var\(\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}\)=2\\Var\(\\left\\lVert Y\-\\E Y\\right\\rVert^\{2\}\)\+4\\tr\(C^\{2\}\)\.If these moments equal2​σ2​d2\\sigma^\{2\}dand8​σ4​d8\\sigma^\{4\}d, respectively, thenm≥d/2m\\geq d/2\. This lower bound is sharp whenddis even: form=d/2m=d/2andU∼Unif⁡\(Sm−1\)U\\sim\\operatorname\{Unif\}\(S^\{m\-1\}\), the replacementY=σ​d​UY=\\sigma\\sqrt\{d\}\\,Umatches both moments exactly\.

CenteringYYdoes not change pairwise distances, so assume𝔼⁡Y=0\\E Y=0\. Expanding

‖Y−Y′‖2=‖Y‖2\+‖Y′‖2−2​Y⊤​Y′\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}=\\left\\lVert Y\\right\\rVert^\{2\}\+\\left\\lVert Y^\{\\prime\}\\right\\rVert^\{2\}\-2Y^\{\\top\}Y^\{\\prime\}and using independence gives

𝔼⁡‖Y−Y′‖2=2​tr​C,Var⁡\(‖Y−Y′‖2\)=2​Var⁡\(‖Y‖2\)\+4​𝔼​\(Y⊤​Y′\)2\.\\E\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}=2\\tr C,\\qquad\\Var\(\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}\)=2\\Var\(\\left\\lVert Y\\right\\rVert^\{2\}\)\+4\\E\(Y^\{\\top\}Y^\{\\prime\}\)^\{2\}\.The remaining expectation istr⁡\(C2\)\\tr\(C^\{2\}\)\. Moment matching therefore impliestr⁡C=σ2​d\\tr C=\\sigma^\{2\}dand

8​σ4​d≥4​tr⁡\(C2\)≥4​\(tr⁡C\)2m=4​σ4​d2m,8\\sigma^\{4\}d\\geq 4\\tr\(C^\{2\}\)\\geq\\frac\{4\(\\tr C\)^\{2\}\}\{m\}=\\frac\{4\\sigma^\{4\}d^\{2\}\}\{m\},where the middle inequality is Cauchy–Schwarz on the eigenvalues ofCC\. Thusm≥d/2m\\geq d/2\.

For the claimed extremizer,‖Y‖2=σ2​d\\left\\lVert Y\\right\\rVert^\{2\}=\\sigma^\{2\}dis deterministic andCov⁡\(Y\)=\(σ2​d/m\)​Im\\Cov\(Y\)=\(\\sigma^\{2\}d/m\)I\_\{m\}\. Hence

𝔼⁡‖Y−Y′‖2=2​σ2​d,Var⁡\(‖Y−Y′‖2\)=4​tr⁡\(Cov⁡\(Y\)2\)=4​σ4​d2m=8​σ4​d\.\\E\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}=2\\sigma^\{2\}d,\\qquad\\Var\(\\left\\lVert Y\-Y^\{\\prime\}\\right\\rVert^\{2\}\)=4\\tr\(\\Cov\(Y\)^\{2\}\)=\\frac\{4\\sigma^\{4\}d^\{2\}\}\{m\}=8\\sigma^\{4\}d\.These matching moments prove sharpness\. Thus exact first\-two\-moment matching requires a linear share of the ambient dimension, even though the replacement map in[proposition3\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1)satisfies the JL bound in logarithmic dimension without matching the variance\. ∎

### B\.3Proof of[theorem5\.1](https://arxiv.org/html/2609.02155#S5.Thmtheorem1)

After row orthonormalization, the sketch is informationally equivalent to\(Π​X,Π​X′\)\(\\Pi X,\\Pi X^\{\\prime\}\)withΠ\\Pia rank\-rrprojector\. SetZ=\(X−X′\)/\(2​σ\)Z=\(X\-X^\{\\prime\}\)/\(\\sqrt\{2\}\\sigma\),𝒯=‖Z‖2\\mathcal\{T\}=\\left\\lVert Z\\right\\rVert^\{2\}, andU=‖Π​Z‖2U=\\left\\lVert\\Pi Z\\right\\rVert^\{2\}\. The Gaussian midpoint is independent ofZZ, and the conditional law of𝒯\\mathcal\{T\}givenΠ​Z\\Pi Zdepends on the projected vector only throughUU\. HenceU∼χr2U\\sim\\chi^\{2\}\_\{r\},V=𝒯−U∼χd−r2V=\\mathcal\{T\}\-U\\sim\\chi^\{2\}\_\{d\-r\},U⟂VU\\perp V, and𝒯⟂𝒪\|U\\mathcal\{T\}\\perp\\mathcal\{O\}\\mid U\. Sufficiency then givesρHGR​\(D,𝒪\)=ρHGR​\(𝒯,U\)\\rho\_\{\\mathrm\{HGR\}\}\(D;\\mathcal\{O\}\)=\\rho\_\{\\mathrm\{HGR\}\}\(\\mathcal\{T\};U\)\.

Write𝒯=∑i=1dWi\\mathcal\{T\}=\\sum\_\{i=1\}^\{d\}W\_\{i\}withWiW\_\{i\}i\.i\.d\.χ12\\chi^\{2\}\_\{1\}and, by rotation,U=∑i≤rWiU=\\sum\_\{i\\leq r\}W\_\{i\}\. The partial\-sum theorem of Dembo, Kagan, and Shepp[Dembo et al\., 2001](https://arxiv.org/html/2609.02155#bib.bib8)yieldsρHGR=r/d\\rho\_\{\\mathrm\{HGR\}\}=\\sqrt\{r/d\}, proving[theorem5\.1](https://arxiv.org/html/2609.02155#S5.Thmtheorem1)\. The variance and MMSE corollaries follow becauseVar⁡\(𝔼⁡\[f∣𝒪\]\)/Var⁡\(f\)≤ρHGR2\\Var\(\\E\[f\\mid\\mathcal\{O\}\]\)/\\Var\(f\)\\leq\\rho\_\{\\mathrm\{HGR\}\}^\{2\}\. ∎

### B\.4Proof of[theorems5\.2](https://arxiv.org/html/2609.02155#S5.Thmtheorem2)and[5\.3](https://arxiv.org/html/2609.02155#S5.Thmtheorem3)

Retain the variablesUU,VV, and𝒯\\mathcal\{T\}from the preceding proof\. For[theorem5\.2](https://arxiv.org/html/2609.02155#S5.Thmtheorem2),\(U,𝒯\)\(U,\\mathcal\{T\}\)is the classical gamma pair withU/𝒯∼Beta⁡\(r2,d−r2\)U/\\mathcal\{T\}\\sim\\mathrm\{Beta\}\(\\tfrac\{r\}\{2\},\\tfrac\{d\-r\}\{2\}\)independent of𝒯\\mathcal\{T\}\. Griffiths[Griffiths, 1969](https://arxiv.org/html/2609.02155#bib.bib10)identifies the canonical \(singular\) system of the induced conditional\-expectation operator as generalized Laguerre polynomials with singular valuesℓk=\[\(r/2\)k/\(d/2\)k\]1/2\\ell\_\{k\}=\[\(r/2\)\_\{k\}/\(d/2\)\_\{k\}\]^\{1/2\}, and Parseval’s identity yields the variance decomposition\. The stated asymptotics follow fromlog⁡ℓk2=∑j<klog⁡r/2\+jd/2\+j\\log\\ell\_\{k\}^\{2\}=\\sum\_\{j<k\}\\log\\frac\{r/2\+j\}\{d/2\+j\}\.

Finally, for[theorem5\.3](https://arxiv.org/html/2609.02155#S5.Thmtheorem3),I⁡\(D,𝒪\)=I⁡\(𝒯,U\)=h⁡\(𝒯\)−h⁡\(𝒯∣U\)=h⁡\(𝒯\)−h⁡\(V\)I\(D;\\mathcal\{O\}\)=I\(\\mathcal\{T\};U\)=h\(\\mathcal\{T\}\)\-h\(\\mathcal\{T\}\\mid U\)=h\(\\mathcal\{T\}\)\-h\(V\)by independence, which is the stated gamma\-entropy difference; the limits follow from Stirling expansions ofhΓh\_\{\\Gamma\}\. ∎

### B\.5Proof of[theorem6\.1](https://arxiv.org/html/2609.02155#S6.Thmtheorem1)

The conditional meanX^=𝔼⁡\[X∣LX\]\\widehat\{X\}=\\E\[X\\mid LX\]is Gaussian with covarianceB=Σ​L⊤​\(L​Σ​L⊤\)†​L​Σ=Σ1/2​P​Σ1/2B=\\Sigma L^\{\\top\}\(L\\Sigma L^\{\\top\}\)^\{\\dagger\}L\\Sigma=\\Sigma^\{1/2\}P\\Sigma^\{1/2\}, where the pseudoinverse identity implies thatP=Σ1/2​L⊤​\(L​Σ​L⊤\)†​L​Σ1/2P=\\Sigma^\{1/2\}L^\{\\top\}\(L\\Sigma L^\{\\top\}\)^\{\\dagger\}L\\Sigma^\{1/2\}is idempotent of rank at mostmm\. Conditioning on𝒪\\mathcal\{O\}givesX−X′∼𝒩⁡\(X^−X^′,2​\(Σ−B\)\)X\-X^\{\\prime\}\\sim\\mathcal\{N\}\(\\widehat\{X\}\-\\widehat\{X\}^\{\\prime\},\\,2\(\\Sigma\-B\)\), so

𝔼⁡\[D∣𝒪\]=‖X^−X^′‖2\+2​tr⁡\(Σ−B\)\.\\E\[D\\mid\\mathcal\{O\}\]=\\left\\lVert\\widehat\{X\}\-\\widehat\{X\}^\{\\prime\}\\right\\rVert^\{2\}\+2\\tr\(\\Sigma\-B\)\.BecauseX^−X^′∼𝒩⁡\(0,2​B\)\\widehat\{X\}\-\\widehat\{X\}^\{\\prime\}\\sim\\mathcal\{N\}\(0,2B\),

Var⁡\(𝔼⁡\[D∣𝒪\]\)=8​tr⁡\(B2\)\.\\Var\(\\E\[D\\mid\\mathcal\{O\}\]\)=8\\tr\(B^\{2\}\)\.
Sincetr⁡\(B2\)=tr⁡\(\(P​Σ​P\)2\)\\tr\(B^\{2\}\)=\\tr\\bigl\(\(P\\Sigma P\)^\{2\}\\bigr\), Poincaré separation implies that the eigenvalues of the compressionP​Σ​PP\\Sigma Pare dominated pairwise byλ1,…,λm\\lambda\_\{1\},\\dots,\\lambda\_\{m\}\. Hencetr⁡\(B2\)≤∑j≤mλj2\\tr\(B^\{2\}\)\\leq\\sum\_\{j\\leq m\}\\lambda\_\{j\}^\{2\}, with equality whenrange⁡\(P\)\\mathrm\{range\}\(P\)is the top\-mmeigenspace\. We derive the minimum mean\-square error \(MMSE\) claim from the law of total variance:

infg𝔼⁡\[\(D−g⁡\(𝒪\)\)2\]=𝔼⁡Var⁡\(D∣𝒪\)=Var⁡\(D\)−Var⁡\(𝔼⁡\[D∣𝒪\]\)≥8​∑j\>mλj2\.\\inf\_\{g\}\\E\[\(D\-g\(\\mathcal\{O\}\)\)^\{2\}\]=\\E\\Var\(D\\mid\\mathcal\{O\}\)=\\Var\(D\)\-\\Var\(\\E\[D\\mid\\mathcal\{O\}\]\)\\geq 8\\sum\_\{j\>m\}\\lambda\_\{j\}^\{2\}\.
For the contrast, seta=X1−X2a=X\_\{1\}\-X\_\{2\},b=X1\+X2−2​X0b=X\_\{1\}\+X\_\{2\}\-2X\_\{0\}, andc=X0\+X1\+X2c=X\_\{0\}\+X\_\{1\}\+X\_\{2\}\. Covariance computation shows thata,b,ca,b,care mutually independent,S=a⊤​bS=a^\{\\top\}b, andVar⁡\(S\)=tr⁡\(6​Σ⋅2​Σ\)=12​tr⁡\(Σ2\)\\Var\(S\)=\\tr\(6\\Sigma\\cdot 2\\Sigma\)=12\\tr\(\\Sigma^\{2\}\)\. The observations are a linear bijection of\(L​a,L​b,L​c\)\(La,Lb,Lc\), soa,ba,bremain conditionally independent given𝒪\\mathcal\{O\}\. Hence𝔼⁡\[S∣𝒪\]=a^⊤​b^\\E\[S\\mid\\mathcal\{O\}\]=\\widehat\{a\}^\{\\top\}\\widehat\{b\}andVar⁡\(a^⊤​b^\)=tr⁡\(2​B⋅6​B\)=12​tr⁡\(B2\)\\Var\(\\widehat\{a\}^\{\\top\}\\widehat\{b\}\)=\\tr\(2B\\cdot 6B\)=12\\tr\(B^\{2\}\), yielding the same ratio\. ∎

### B\.6Proof of[theorem6\.2](https://arxiv.org/html/2609.02155#S6.Thmtheorem2)

LetA=G12A=G\_\{1\}^\{2\}andB=G22B=G\_\{2\}^\{2\}, whose moments are1,3,15,1051,3,15,105\. The covariances among\{D,D2\}\\\{D,D^\{2\}\\\}and\{U,U2\}\\\{U,U^\{2\}\\\}are polynomials in these moments:

Var⁡D\\displaystyle\\Var D=10,\\displaystyle=10,Cov⁡\(D,D2\)\\displaystyle\\Cov\(D,D^\{2\}\)=132,\\displaystyle=132,Var⁡D2\\displaystyle\\Var D^\{2\}=2240,\\displaystyle=2240,Var⁡U\\displaystyle\\Var U=8,\\displaystyle=8,Cov⁡\(U,U2\)\\displaystyle\\Cov\(U,U^\{2\}\)=96,\\displaystyle=96,Var⁡U2\\displaystyle\\Var U^\{2\}=1536,\\displaystyle=1536,Cov⁡\(D,U\)\\displaystyle\\Cov\(D,U\)=8,\\displaystyle=8,Cov⁡\(D,U2\)\\displaystyle\\Cov\(D,U^\{2\}\)=96,\\displaystyle=96,Cov⁡\(D2,U\)\\displaystyle\\Cov\(D^\{2\},U\)=112,\\displaystyle=112,Cov⁡\(D2,U2\)\\displaystyle\\Cov\(D^\{2\},U^\{2\}\)=1728\.\\displaystyle=1728\.The largest eigenvalue ofΣD​D−1​ΣD​U​ΣU​U−1​ΣU​D\\Sigma\_\{DD\}^\{\-1\}\\Sigma\_\{DU\}\\Sigma\_\{UU\}^\{\-1\}\\Sigma\_\{UD\}is\(246\+2​201\)/311≈0\.882170\(246\+2\\sqrt\{201\}\)/311\\approx 0\.882170, and its square root exceeds4/5\\sqrt\{4/5\}\. Restricting to quadratic polynomials makes this value a lower bound onρHGR\\rho\_\{\\mathrm\{HGR\}\}\. ∎

### B\.7Proof of[theorem6\.3](https://arxiv.org/html/2609.02155#S6.Thmtheorem3)

Remove the independent Gaussian midpoint and whiten inside each spectral block\. Then

D=2​∑g=1Gλg​Tg,Tg=Ug\+Vg,D=2\\sum\_\{g=1\}^\{G\}\\lambda\_\{g\}T\_\{g\},\\qquad T\_\{g\}=U\_\{g\}\+V\_\{g\},where the block pairs are independent and

Ug∼χsg2,Vg∼χrg−sg2,Ug⟂Vg\.U\_\{g\}\\sim\\chi^\{2\}\_\{s\_\{g\}\},\\qquad V\_\{g\}\\sim\\chi^\{2\}\_\{r\_\{g\}\-s\_\{g\}\},\\qquad U\_\{g\}\\perp V\_\{g\}\.For estimatingDD, the vector\(Ug\)g\(U\_\{g\}\)\_\{g\}is sufficient for the full sketch\. The beta–gamma channelTg↦UgT\_\{g\}\\mapsto U\_\{g\}has nontrivial maximal correlationsg/rg\\sqrt\{s\_\{g\}/r\_\{g\}\}\. Witsenhausen[Witsenhausen, 1975](https://arxiv.org/html/2609.02155#bib.bib34)proved the tensorization theorem; together with data processing, it gives

ρHGR​\(D,𝒪\)≤maxg⁡sg/rg\.\\rho\_\{\\mathrm\{HGR\}\}\(D;\\mathcal\{O\}\)\\leq\\max\_\{g\}\\sqrt\{s\_\{g\}/r\_\{g\}\}\.
For the lower bound, takeG⁡\(U\)=2​∑gλg​\(Ug−sg\)G\(U\)=2\\sum\_\{g\}\\lambda\_\{g\}\(U\_\{g\}\-s\_\{g\}\)\. The omitted weighted sum is independent ofG⁡\(U\)G\(U\), so

Cov⁡\(D,G⁡\(U\)\)=Var⁡\(G⁡\(U\)\)=8​∑gλg2​sg,Var⁡\(D\)=8​∑gλg2​rg\.\\Cov\(D,G\(U\)\)=\\Var\(G\(U\)\)=8\\sum\_\{g\}\\lambda\_\{g\}^\{2\}s\_\{g\},\\qquad\\Var\(D\)=8\\sum\_\{g\}\\lambda\_\{g\}^\{2\}r\_\{g\}\.ThusCorr⁡\(D,G⁡\(U\)\)=αΠ​\(Σ\)\\Corr\(D,G\(U\)\)=\\sqrt\{\\alpha\_\{\\Pi\}\(\\Sigma\)\}\. If everysg/rgs\_\{g\}/r\_\{g\}equalsθ\\theta, the bounds coincide\. The flat\-support statement is the one\-block specialization\. ∎

### B\.8Proof of[theorem7\.1](https://arxiv.org/html/2609.02155#S7.Thmtheorem1)

Witha=X1−X2a=X\_\{1\}\-X\_\{2\}andb=X1\+X2−2​X0b=X\_\{1\}\+X\_\{2\}\-2X\_\{0\}independent isotropic Gaussians,D01−D02=a⊤​bD\_\{01\}\-D\_\{02\}=a^\{\\top\}bandD~01−D~02=dm​a⊤​Π​b\\widetilde\{D\}\_\{01\}\-\\widetilde\{D\}\_\{02\}=\\tfrac\{d\}\{m\}a^\{\\top\}\\Pi b\. Conditional onaa, these differences are centered jointly Gaussian inbbwith correlationa⊤​Π​a/a⊤​a\\sqrt\{a^\{\\top\}\\Pi a/a^\{\\top\}a\}, whose square isBeta⁡\(m2,d−m2\)\\mathrm\{Beta\}\(\\tfrac\{m\}\{2\},\\tfrac\{d\-m\}\{2\}\)by rotation invariance\. Sheppard[Sheppard, 1899](https://arxiv.org/html/2609.02155#bib.bib11)showed that the sign\-agreement probability is12\+1π​arcsin⁡ρ\\tfrac\{1\}\{2\}\+\\tfrac\{1\}\{\\pi\}\\arcsin\\rho; averaging overaayields the law\. Applyingarcsin⁡B≤π2​B\\arcsin\\sqrt\{B\}\\leq\\tfrac\{\\pi\}\{2\}\\sqrt\{B\}and𝔼⁡B≤m/d\\E\\sqrt\{B\}\\leq\\sqrt\{m/d\}gives the bound, whereas concentration ofBBatm/dm/dgives the expansion\. Kendall’sτ\\tauover one query’s ranking averages pairwise sign agreements, each with marginal probabilitypm,dp\_\{m,d\}by exchangeability; hence𝔼⁡\[τ\]=2​pm,d−1\\E\[\\tau\]=2p\_\{m,d\}\-1\. ∎

### B\.9Proof of[theorems7\.2](https://arxiv.org/html/2609.02155#S7.Thmtheorem2)and[7\.3](https://arxiv.org/html/2609.02155#S7.Thmtheorem3)

By rotational invariance, takeRRto select the firstmmcoordinates and putr=d−mr=d\-m\. SplitXj=\(Yj,Zj\)X\_\{j\}=\(Y\_\{j\},Z\_\{j\}\)and define

Uj=‖Yj−Y0‖2,Vj=‖Zj−Z0‖2\.U\_\{j\}=\\left\\lVert Y\_\{j\}\-Y\_\{0\}\\right\\rVert^\{2\},\\qquad V\_\{j\}=\\left\\lVert Z\_\{j\}\-Z\_\{0\}\\right\\rVert^\{2\}\.The projected ranking is that of\(Uj\)j\(U\_\{j\}\)\_\{j\}, the original ranking is that of\(Uj\+Vj\)j\(U\_\{j\}\+V\_\{j\}\)\_\{j\}, and the vectorsUUandVVare independent\.

For one coordinate, set

W=\(\(X1−X0\)2−2,…,\(Xq−X0\)2−2\)\.W=\(\(X\_\{1\}\-X\_\{0\}\)^\{2\}\-2,\\ldots,\(X\_\{q\}\-X\_\{0\}\)^\{2\}\-2\)\.Direct Gaussian moments giveCov⁡\(W\)=6​Iq\+2​𝟏𝟏⊤=:Cq\\Cov\(W\)=6I\_\{q\}\+2\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}=:C\_\{q\}\. Independently,

U−2​m​𝟏m⇒G\(1\),V−2​r​𝟏r⇒G\(2\),\\frac\{U\-2m\\mathbf\{1\}\}\{\\sqrt\{m\}\}\\Rightarrow G^\{\(1\)\},\\qquad\\frac\{V\-2r\\mathbf\{1\}\}\{\\sqrt\{r\}\}\\Rightarrow G^\{\(2\)\},whereG\(1\),G\(2\)∼𝒩⁡\(0,Cq\)G^\{\(1\)\},G^\{\(2\)\}\\sim\\mathcal\{N\}\(0,C\_\{q\}\)\. We may write

G\(1\)=6​G\+2​ξ​𝟏,G\(2\)=6​H\+2​η​𝟏\.G^\{\(1\)\}=\\sqrt\{6\}G\+\\sqrt\{2\}\\xi\\mathbf\{1\},\\qquad G^\{\(2\)\}=\\sqrt\{6\}H\+\\sqrt\{2\}\\eta\\mathbf\{1\}\.The common shifts do not affect rankings\. The limiting projected scores are thereforeGG, and the limiting original scores areα​G\+1−α​H\\sqrt\{\\alpha\}G\+\\sqrt\{1\-\\alpha\}H\. Ties have probability zero, so the continuous mapping theorem proves the top\-kklimit\.

Fork=1k=1, the event that one fixed index minimizes both rankings is an intersection of linear halfspaces in the2​q2qnormalized score coordinates\. Applying Bentkus’s multivariate Berry–Esseen bound for convex sets[Bentkus, 2003](https://arxiv.org/html/2609.02155#bib.bib39)to themm\-coordinate sum and then to the independentrr\-coordinate sum gives errorOq\(m−1/2\+r−1/2\)O\_\{q\}\(m^\{\-1/2\}\+r^\{\-1/2\}\)\. Summing over theqqdisjoint common minimizers gives the stated rate\. Conditioning on the score pair of the common minimizer yields[equation8](https://arxiv.org/html/2609.02155#S7.E8): all other pairs must lie above it, so the joint survival function appears\. This proves[theorem7\.2](https://arxiv.org/html/2609.02155#S7.Thmtheorem2)\.

For[proposition7\.3](https://arxiv.org/html/2609.02155#S7.Thmtheorem3), differentiate[equation8](https://arxiv.org/html/2609.02155#S7.E8)\. Atρ=0\\rho=0,

∂ρϕρ​\(x,y\)=x​y​ϕ​\(x\)​ϕ​\(y\),∂ρΦ¯ρ​\(x,y\)=ϕ⁡\(x\)​ϕ​\(y\)\.\\partial\_\{\\rho\}\\phi\_\{\\rho\}\(x,y\)=xy\\phi\(x\)\\phi\(y\),\\qquad\\partial\_\{\\rho\}\\overline\{\\Phi\}\_\{\\rho\}\(x,y\)=\\phi\(x\)\\phi\(y\)\.Setaq=∫ϕ​\(x\)2​Φ¯​\(x\)q−2​𝑑xa\_\{q\}=\\int\\phi\(x\)^\{2\}\\overline\{\\Phi\}\(x\)^\{q\-2\}\\,dx\. Integration by parts gives

∫x​ϕ​\(x\)​Φ¯​\(x\)q−1​𝑑x=−\(q−1\)​aq\.\\int x\\phi\(x\)\\overline\{\\Phi\}\(x\)^\{q\-1\}\\,dx=\-\(q\-1\)a\_\{q\}\.The first differentiated term contains the square of this integral, and the second contributesq⁡\(q−1\)​aq2q\(q\-1\)a\_\{q\}^\{2\}\. Hencepq′​\(0\)=q2​\(q−1\)​aq2p\_\{q\}^\{\\prime\}\(0\)=q^\{2\}\(q\-1\)a\_\{q\}^\{2\}\. A Taylor expansion proves the proposition\. ∎

### B\.10Proof of[theorem7\.4](https://arxiv.org/html/2609.02155#S7.Thmtheorem4)

For a fixed rank\-mmprojector and an isotropic Gaussian triple,[theorem7\.1](https://arxiv.org/html/2609.02155#S7.Thmtheorem1)gives𝔼⁡sA​\(X1,X2,X3\)=τm,d\\E s\_\{A\}\(X\_\{1\};X\_\{2\},X\_\{3\}\)=\\tau\_\{m,d\}, independently of the orientation ofAA\. Define the symmetric kernel

hA​\(x,y,z\)=13​\(sA​\(x,y,z\)\+sA​\(y,x,z\)\+sA​\(z,x,y\)\)\.h\_\{A\}\(x,y,z\)=\\frac\{1\}\{3\}\\bigl\(s\_\{A\}\(x;y,z\)\+s\_\{A\}\(y;x,z\)\+s\_\{A\}\(z;x,y\)\\bigr\)\.A counting identity gives

τ¯n=\(n3\)−1​∑1≤i<j<k≤nhA​\(Xi,Xj,Xk\)\.\\overline\{\\tau\}\_\{n\}=\\binom\{n\}\{3\}^\{\-1\}\\sum\_\{1\\leq i<j<k\\leq n\}h\_\{A\}\(X\_\{i\},X\_\{j\},X\_\{k\}\)\.The kernel takes values in\[−1,1\]\[\-1,1\]\. Hoeffding[Hoeffding, 1963](https://arxiv.org/html/2609.02155#bib.bib40)proved the blocking inequality for bounded order\-three U\-statistics; applying it yields

Pr⁡\(\|τ¯n−τm,d\|\>t∣A\)≤2​exp⁡\(−⌊n/3⌋​t22\)\.\\Pr\\\!\\left\(\\left\|\\overline\{\\tau\}\_\{n\}\-\\tau\_\{m,d\}\\right\|\>t\\mid A\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{\\lfloor n/3\\rfloor t^\{2\}\}\{2\}\\right\)\.
For each fixed nonzerovv, the ratio‖A​v‖2/‖v‖2\\left\\lVert Av\\right\\rVert^\{2\}/\\left\\lVert v\\right\\rVert^\{2\}has a scaled Beta law and satisfies

Pr⁡\(\|‖A​v‖2‖v‖2−1\|\>ε\)≤2​e−c​ε2​m\.\\Pr\\\!\\left\(\\left\|\\frac\{\\left\\lVert Av\\right\\rVert^\{2\}\}\{\\left\\lVert v\\right\\rVert^\{2\}\}\-1\\right\|\>\\varepsilon\\right\)\\leq 2e^\{\-c\\varepsilon^\{2\}m\}\.Conditioning on the data and taking a union bound over the\(n2\)\\binom\{n\}\{2\}differences proves the stated JL event\. Finally,[theorem7\.1](https://arxiv.org/html/2609.02155#S7.Thmtheorem1)givesτm,d≤m/d\\tau\_\{m,d\}\\leq\\sqrt\{m/d\}\. Substituting the statedttinto the U\-statistic bound and applying a union bound with the JL event completes the proof\. ∎

### B\.11Proof of[theorem8\.1](https://arxiv.org/html/2609.02155#S8.Thmtheorem1)

*Mean direction\.*The Kullback–Leibler divergenceDKLD\_\{\\mathrm\{KL\}\}between shifted isotropic Gaussians is‖δ‖2/2​σ2\\left\\lVert\\delta\\right\\rVert^\{2\}/2\\sigma^\{2\}before projection and‖R​δ‖2/2​σ2\\left\\lVert R\\delta\\right\\rVert^\{2\}/2\\sigma^\{2\}afterward\. The ratio‖R​δ‖2/‖δ‖2\\left\\lVert R\\delta\\right\\rVert^\{2\}/\\left\\lVert\\delta\\right\\rVert^\{2\}has distributionBeta⁡\(m2,d−m2\)\\mathrm\{Beta\}\(\\tfrac\{m\}\{2\},\\tfrac\{d\-m\}\{2\}\)and meanm/dm/d\.

*Scalar log\-scale\.*The divergenceDKL=d2​\(r−1−log⁡r\)D\_\{\\mathrm\{KL\}\}=\\tfrac\{d\}\{2\}\(r\-1\-\\log r\)maps deterministically tom2​\(r−1−log⁡r\)\\tfrac\{m\}\{2\}\(r\-1\-\\log r\)becauseR⁡\(σ2​I\)​R⊤=σ2​ImR\(\\sigma^\{2\}I\)R^\{\\top\}=\\sigma^\{2\}I\_\{m\}\.

*Diffuse traceless covariance shape\.*ConsiderΣζ,ε=eζ​\(I\+ε​H\)\\Sigma\_\{\\zeta,\\varepsilon\}=e^\{\\zeta\}\(I\+\\varepsilon H\)withHHsymmetric traceless and withζ\\zetaan unknown nuisance scale\. At the isotropic model, the covariance\-tangent Fisher inner product is⟨A,B⟩=12​tr⁡\(A​B\)\\langle A,B\\rangle=\\tfrac\{1\}\{2\}\\tr\(AB\)\. The original shape tangentHHis orthogonal to the scale tangentIdI\_\{d\}\. After projection, removing the component ofR​H​R⊤RHR^\{\\top\}parallel to the nuisance tangentImI\_\{m\}gives the efficient shape tangentR​H​R⊤−tr⁡\(R​H​R⊤\)m​ImRHR^\{\\top\}\-\\tfrac\{\\tr\(RHR^\{\\top\}\)\}\{m\}I\_\{m\}\. Fortr⁡H=0\\tr H=0, second\-order Haar integration gives

𝔼⁡tr⁡\(\(RHR⊤\)2\)=m⁡\(\(m\+1\)​d−2\)d​\(d−1\)​\(d\+2\)​‖H‖F2,𝔼⁡\[tr⁡\(RHR⊤\)2\]=2​m​\(d−m\)d​\(d−1\)​\(d\+2\)​‖H‖F2\.\\E\\tr\\\!\\left\(\(RHR^\{\\top\}\)^\{2\}\\right\)=\\frac\{m\(\(m\+1\)d\-2\)\}\{d\(d\-1\)\(d\+2\)\}\\,\\left\\lVert H\\right\\rVert\_\{F\}^\{2\},\\qquad\\E\\\!\\left\[\\tr\(RHR^\{\\top\}\)^\{2\}\\right\]=\\frac\{2m\(d\-m\)\}\{d\(d\-1\)\(d\+2\)\}\\,\\left\\lVert H\\right\\rVert\_\{F\}^\{2\}\.Subtracting1/m1/mtimes the second identity from the first yields the traceless moment in[theorem8\.1](https://arxiv.org/html/2609.02155#S8.Thmtheorem1)\. Dividing the projected efficient Fisher information by12​‖H‖F2\\tfrac\{1\}\{2\}\\left\\lVert H\\right\\rVert\_\{F\}^\{2\}gives the exact ratio\. Equation \([11](https://arxiv.org/html/2609.02155#S8.E11)\) follows from the standard Gaussian Fisher\-information calculation with knownRR\. ∎

### B\.12Proof of[theorems9\.1](https://arxiv.org/html/2609.02155#S9.Thmtheorem1),[A\.1](https://arxiv.org/html/2609.02155#S1.Thmtheorem1)and[10\.1](https://arxiv.org/html/2609.02155#S10.Thmtheorem1)

*Rank\.*By the singular value decomposition,T​ZTZis an invertible function of\(si​Zi′\)i≤r\(s\_\{i\}Z\_\{i\}^\{\\prime\}\)\_\{i\\leq r\}for a rotated standard GaussianZ′Z^\{\\prime\}\. Because eachsis\_\{i\}is nonzero, observingT​ZTZis informationally equivalent to observingrrcoordinates ofZ′Z^\{\\prime\}, so[theorem5\.1](https://arxiv.org/html/2609.02155#S5.Thmtheorem1)applies withrrin place ofmm\.

*Unwhitened squared\-norm estimate\.*WithM=T⊤​TM=T^\{\\top\}T, Gaussian quadratic\-form identities giveCov⁡\(D,Q\)=2​tr⁡\(M\)\\Cov\(D,Q\)=2\\tr\(M\)andVar⁡\(Q\)=2​tr⁡\(M2\)\\Var\(Q\)=2\\tr\(M^\{2\}\)forZ∼𝒩⁡\(0,Id\)Z\\sim\\mathcal\{N\}\(0,I\_\{d\}\)\. HenceCorr=tr⁡M/d​tr⁡\(M2\)\\Corr=\\tr M/\\sqrt\{d\\,\\tr\(M^\{2\}\)\}\. The Kantorovich inequality applied to the positive eigenvaluessi2s\_\{i\}^\{2\}gives the stated two\-sided bound, with the extremizer placing mass≈1/\(κ2\+1\)\\approx 1/\(\\kappa^\{2\}\+1\)atsmaxs\_\{\\max\}\. Whitening makesW⊤​WW^\{\\top\}Wthe row\-space projector, sor2​\(W⊤​W\)=rr\_\{2\}\(W^\{\\top\}W\)=r\.

*Additive\-noise recovery\.*Gaussian conditioning gives recovered variancesi2/\(si2\+ε2\)s\_\{i\}^\{2\}/\(s\_\{i\}^\{2\}\+\\varepsilon^\{2\}\)and posterior varianceε2/\(si2\+ε2\)\\varepsilon^\{2\}/\(s\_\{i\}^\{2\}\+\\varepsilon^\{2\}\)in each right\-singular direction\. Averaging the posterior variance over the quarter\-circle law yieldsψedge​\(ε\)=ε2​\(ε2\+4−ε\)\\psi\_\{\\mathrm\{edge\}\}\(\\varepsilon\)=\\tfrac\{\\varepsilon\}\{2\}\(\\sqrt\{\\varepsilon^\{2\}\+4\}\-\\varepsilon\)\.

*Finite joint identity\.*Conditional on its inputyy, a Gaussian stage with entriesN⁡\(0,1/nℓ\)N\(0,1/n\_\{\\ell\}\)outputsGℓ​y∼𝒩⁡\(0,‖y‖2/nℓ​Inℓ\)G\_\{\\ell\}y\\sim\\mathcal\{N\}\(0,\\left\\lVert y\\right\\rVert^\{2\}/n\_\{\\ell\}\\,I\_\{n\_\{\\ell\}\}\)\. Thus‖Gℓ​y‖2=‖y‖2⋅χnℓ2/nℓ\\left\\lVert G\_\{\\ell\}y\\right\\rVert^\{2\}=\\left\\lVert y\\right\\rVert^\{2\}\\cdot\\chi^\{2\}\_\{n\_\{\\ell\}\}/n\_\{\\ell\}, with theχ2\\chi^\{2\}factor independent of everything prior\. Hence𝔼⁡\[‖PL​Z‖2∣Z\]=‖Z‖2\\E\[\\left\\lVert P\_\{L\}Z\\right\\rVert^\{2\}\\mid Z\]=\\left\\lVert Z\\right\\rVert^\{2\}, and second moments multiply:

𝔼⁡‖PL​Z‖4=𝔼⁡‖Z‖4​∏ℓ≥1\(1\+2/nℓ\)\.\\E\\left\\lVert P\_\{L\}Z\\right\\rVert^\{4\}=\\E\\left\\lVert Z\\right\\rVert^\{4\}\\prod\_\{\\ell\\geq 1\}\(1\+2/n\_\{\\ell\}\)\.With𝔼⁡‖Z‖4=\(𝔼⁡‖Z‖2\)2​\(1\+2/d\)\\E\\left\\lVert Z\\right\\rVert^\{4\}=\(\\E\\left\\lVert Z\\right\\rVert^\{2\}\)^\{2\}\(1\+2/d\), these moments give

Var⁡\(‖PL​Z‖2\)=\(𝔼⁡‖Z‖2\)2​\[∏ℓ≥0\(1\+2/nℓ\)−1\],n0=d\.\\Var\(\\left\\lVert P\_\{L\}Z\\right\\rVert^\{2\}\)=\(\\E\\left\\lVert Z\\right\\rVert^\{2\}\)^\{2\}\\left\[\\prod\_\{\\ell\\geq 0\}\(1\+2/n\_\{\\ell\}\)\-1\\right\],\\qquad n\_\{0\}=d\.Moreover,Cov⁡\(‖Z‖2,‖PL​Z‖2\)=Var⁡\(‖Z‖2\)=\(𝔼⁡‖Z‖2\)2⋅2/d\\Cov\(\\left\\lVert Z\\right\\rVert^\{2\},\\left\\lVert P\_\{L\}Z\\right\\rVert^\{2\}\)=\\Var\(\\left\\lVert Z\\right\\rVert^\{2\}\)=\(\\E\\left\\lVert Z\\right\\rVert^\{2\}\)^\{2\}\\cdot 2/d\. Their ratio is the stated identity, andL=1L=1givesm/\(m\+d\+2\)m/\(m\+d\+2\)\.

*Typical\-map deterministic equivalent\.*The identities𝔼⁡tr⁡M=d\\E\\tr M=dand𝔼⁡tr⁡M2=d⁡\(m\+d\+1\)/m\\E\\tr M^\{2\}=d\(m\+d\+1\)/mgive the ratio of momentsm​d/\(m\+d\+1\)md/\(m\+d\+1\)\. Concentration of both traces yieldsr2=\(1\+oℙ​\(1\)\)​m​d/\(m\+d\)r\_\{2\}=\(1\+o\_\{\\mathbb\{P\}\}\(1\)\)\\,md/\(m\+d\)\. For multiple layers, the recursion

𝔼⁡\[tr⁡\(Pℓ⊤​Pℓ\)2∣Pℓ−1\]=\(1\+1nℓ\)​tr​\(Pℓ−1⊤​Pℓ−1\)2\+1nℓ​\(tr⁡Pℓ−1⊤​Pℓ−1\)2\\E\[\\tr\(P\_\{\\ell\}^\{\\top\}P\_\{\\ell\}\)^\{2\}\\mid P\_\{\\ell\-1\}\]=\\left\(1\+\\frac\{1\}\{n\_\{\\ell\}\}\\right\)\\tr\(P\_\{\\ell\-1\}^\{\\top\}P\_\{\\ell\-1\}\)^\{2\}\+\\frac\{1\}\{n\_\{\\ell\}\}\\left\(\\tr P\_\{\\ell\-1\}^\{\\top\}P\_\{\\ell\-1\}\\right\)^\{2\}adds1/nℓ1/n\_\{\\ell\}per layer at leading order\. Rank\-one maps \(r2≡1r\_\{2\}\\equiv 1\) show that this equivalent is not a finite identity\.

*Polar decomposition\.*Write

G/m=\(G​G⊤/d\)1/2⋅d/m​R,G/\\sqrt\{m\}=\(GG^\{\\top\}/d\)^\{1/2\}\\cdot\\sqrt\{d/m\}R,whereRRis Haar and independent of the Wishart factor\. For a fixedxx, the Haar stage givesdm​B\\tfrac\{d\}\{m\}BwithB∼Beta⁡\(m2,d−m2\)B\\sim\\mathrm\{Beta\}\(\\tfrac\{m\}\{2\},\\tfrac\{d\-m\}\{2\}\)\. Along the projected direction, the square factor contributesu⊤​\(G​G⊤/d\)​u∼χd2/du^\{\\top\}\(GG^\{\\top\}/d\)u\\sim\\chi^\{2\}\_\{d\}/d\. The beta–gamma algebra then givesdm​B⋅χd2/d​=𝑑​χm2/m\\tfrac\{d\}\{m\}B\\cdot\\chi^\{2\}\_\{d\}/d\\overset\{d\}\{=\}\\chi^\{2\}\_\{m\}/m, which is the full map’s noise\.

*Ensembles\.*Stacking is a linear map of rank≤min⁡\{k​m,d\}\\leq\\min\\\{km,d\\\}, so[theorem6\.1](https://arxiv.org/html/2609.02155#S6.Thmtheorem1)for generalΣ\\Sigmaand[theorem9\.1](https://arxiv.org/html/2609.02155#S9.Thmtheorem1)\(i\) apply with that rank\. Independent Gaussian blocks concatenate into one Gaussian matrix whose row space is Haar, giving equality after whitening\. The average of per\-sketch estimates equals the unwhitened squared\-norm estimate from the concatenatedk​m×dkm\\times dGaussian map, with entriesN⁡\(0,1/\(k​m\)\)N\(0,1/\(km\)\)after scaling\. The single\-stage identity therefore gives correlationk​m/\(k​m\+d\+2\)\\sqrt\{km/\(km\+d\+2\)\}over both map and data randomness\. Dividing this correlation by the HGR ceilingmin⁡\{k​m,d\}/d\\sqrt\{\\min\\\{km,d\\\}/d\}gives the ratio stated in[theorem10\.1](https://arxiv.org/html/2609.02155#S10.Thmtheorem1)\. ∎

## CA Nonasymptotic Neighborhood Coupling

The Gaussian score limit for fixed candidate count in the main article assumes that both coordinate blocks grow\. In contrast,[theoremC\.1](https://arxiv.org/html/2609.02155#S3.Thmtheorem1a)covers fixedmmand gives an explicit, conservative dependence on the candidate count\.

###### Theorem C\.1\(Nonasymptotic chance\-neighborhood coupling\)\.

In the setting of[theorem7\.2](https://arxiv.org/html/2609.02155#S7.Thmtheorem2), letr=d−m≥2r=d\-m\\geq 2anda=log⁡\(2​q\)a=\\log\(2q\)\. Define

cr=112​πΓ⁡\(\(r−1\)/2\)Γ⁡\(r/2\)≍r−1/2c\_\{r\}=\\frac\{1\}\{\\sqrt\{12\\pi\}\}\\frac\{\\Gamma\(\(r\-1\)/2\)\}\{\\Gamma\(r/2\)\}\\asymp r^\{\-1/2\}and

Δq,m,r=min⁡\{1,\(q2\)​cr​\(12​m​a\+16​a\)\}\.\\Delta\_\{q,m,r\}=\\min\\left\\\{1,\\binom\{q\}\{2\}c\_\{r\}\\left\(12\\sqrt\{ma\}\+16a\\right\)\\right\\\}\.There are independent uniformly randomkk\-subsetsSU,SVS\_\{U\},S\_\{V\}of\{1,…,q\}\\\{1,\\ldots,q\\\}, withSU=𝒩~kS\_\{U\}=\\widetilde\{\\mathcal\{N\}\}\_\{k\}, such that

Pr⁡\(𝒩k≠SV\)≤Δq,m,r\.\\Pr\(\\mathcal\{N\}\_\{k\}\\neq S\_\{V\}\)\\leq\\Delta\_\{q,m,r\}\.Consequently,

dTV​\(ℒ⁡\(𝒩~k,𝒩k\),ℒ⁡\(SU,SV\)\)≤Δq,m,r,d\_\{\\mathrm\{TV\}\}\\\!\\left\(\\mathcal\{L\}\(\\widetilde\{\\mathcal\{N\}\}\_\{k\},\\mathcal\{N\}\_\{k\}\),\\mathcal\{L\}\(S\_\{U\},S\_\{V\}\)\\right\)\\leq\\Delta\_\{q,m,r\},\|𝔼⁡\|𝒩k∩𝒩~k\|k−kq\|≤Δq,m,r,\\left\|\\E\\frac\{\\left\|\\mathcal\{N\}\_\{k\}\\cap\\widetilde\{\\mathcal\{N\}\}\_\{k\}\\right\|\}\{k\}\-\\frac\{k\}\{q\}\\right\|\\leq\\Delta\_\{q,m,r\},and, fork=1k=1,

\|Pr⁡\(𝒩1=𝒩~1\)−1q\|≤Δq,m,r\.\\left\|\\Pr\(\\mathcal\{N\}\_\{1\}=\\widetilde\{\\mathcal\{N\}\}\_\{1\}\)\-\\frac\{1\}\{q\}\\right\|\\leq\\Delta\_\{q,m,r\}\.For fixedqqandkk,m=o⁡\(d\)m=o\(d\)impliesΔq,m,d−m→0\\Delta\_\{q,m,d\-m\}\\to 0\.

###### Proof\.

We decomposeDj=Uj\+VjD\_\{j\}=U\_\{j\}\+V\_\{j\}as in the proof of[theorem7\.2](https://arxiv.org/html/2609.02155#S7.Thmtheorem2)\. LetSUS\_\{U\}andSVS\_\{V\}be the indices of thekksmallest coordinates ofUUandVV\. They are independent uniformkk\-subsets\. Set

WU=maxj⁡Uj−minj⁡Uj,GV,k=V\(k\+1\)−V\(k\)\.W\_\{U\}=\\max\_\{j\}U\_\{j\}\-\\min\_\{j\}U\_\{j\},\\qquad G\_\{V,k\}=V\_\{\(k\+1\)\}\-V\_\{\(k\)\}\.IfGV,k\>WUG\_\{V,k\}\>W\_\{U\}, then even after addingUU, every index inSVS\_\{V\}remains ahead of every index outsideSVS\_\{V\}, so𝒩k=SV\\mathcal\{N\}\_\{k\}=S\_\{V\}\.

Fori≠ji\\neq j,

Vi−Vj=\(Zi−Zj\)⊤​\(Zi\+Zj−2​Z0\)​=𝑑​12​∑ℓ=1rgℓ​hℓ,V\_\{i\}\-V\_\{j\}=\(Z\_\{i\}\-Z\_\{j\}\)^\{\\top\}\(Z\_\{i\}\+Z\_\{j\}\-2Z\_\{0\}\)\\overset\{d\}\{=\}\\sqrt\{12\}\\sum\_\{\\ell=1\}^\{r\}g\_\{\\ell\}h\_\{\\ell\},wheregℓg\_\{\\ell\}andhℓh\_\{\\ell\}are independent standard normal variables\. The characteristic function of this difference is\(1\+12t2\)−r/2\(1\+12t^\{2\}\)^\{\-r/2\}\. Fourier inversion of this function therefore gives

supxfVi−Vj​\(x\)≤12​12​π​Γ⁡\(\(r−1\)/2\)Γ⁡\(r/2\)\.\\sup\_\{x\}f\_\{V\_\{i\}\-V\_\{j\}\}\(x\)\\leq\\frac\{1\}\{2\\sqrt\{12\\pi\}\}\\frac\{\\Gamma\(\(r\-1\)/2\)\}\{\\Gamma\(r/2\)\}\.This density bound implies that

Pr⁡\(\|Vi−Vj\|≤t\)≤cr​t,Pr⁡\(GV,k≤t\)≤\(q2\)​cr​t\.\\Pr\(\\left\|V\_\{i\}\-V\_\{j\}\\right\|\\leq t\)\\leq c\_\{r\}t,\\qquad\\Pr\(G\_\{V,k\}\\leq t\)\\leq\\binom\{q\}\{2\}c\_\{r\}t\.SinceUUandVVare independent, conditioning onWUW\_\{U\}yields

Pr⁡\(GV,k≤WU\)≤\(q2\)​cr​𝔼⁡WU\.\\Pr\(G\_\{V,k\}\\leq W\_\{U\}\)\\leq\\binom\{q\}\{2\}c\_\{r\}\\E W\_\{U\}\.Marginally,Uj∼2​χm2U\_\{j\}\\sim 2\\chi\_\{m\}^\{2\}\. Laurent and Massart[Laurent and Massart, 2000](https://arxiv.org/html/2609.02155#bib.bib41)proved the concentration inequality used here; a union bound and tail integration give

𝔼⁡WU≤12​m​log⁡\(2​q\)\+16​log⁡\(2​q\)\.\\E W\_\{U\}\\leq 12\\sqrt\{m\\log\(2q\)\}\+16\\log\(2q\)\.These bounds prove the coupling\. Because two independent uniformkk\-subsets have expected normalized overlapk/qk/q, the remaining statements follow\. ∎

## DClassical Deterministic Ordinal\-Capacity Bounds

While our probabilistic theorems in the main article concern random maps and Gaussian clouds, a classical deterministic question asks whether any embedding can realize an arbitrary ordering in low dimension\. For monotone Euclidean embeddings, Bilu and Linial used sign\-pattern methods to show that almost every finite metric requires linear dimension[Bilu and Linial, 2005](https://arxiv.org/html/2609.02155#bib.bib42)\. We record the corresponding number of full distance orders and a universal dimension bound for realizing them\.

Let𝒪n,m\\mathcal\{O\}\_\{n,m\}be the set of strict total orders of theN=\(n2\)N=\\binom\{n\}\{2\}pairwise distances induced bynnlabeled points inℝm\\mathbb\{R\}^\{m\}\. Each comparison‖xi−xj‖2\>‖xk−xℓ‖2\\left\\lVert x\_\{i\}\-x\_\{j\}\\right\\rVert^\{2\}\>\\left\\lVert x\_\{k\}\-x\_\{\\ell\}\\right\\rVert^\{2\}is a degree\-two polynomial inequality inm​nmnvariables, and there are\(N2\)=O⁡\(n4\)\\binom\{N\}\{2\}=O\(n^\{4\}\)such polynomials\.

###### Theorem D\.1\(Ordinal capacity\)\.

1. \(i\)The sign\-pattern bounds of Warren[Warren, 1968](https://arxiv.org/html/2609.02155#bib.bib12)and Milnor[Milnor, 1964](https://arxiv.org/html/2609.02155#bib.bib13)give \|𝒪n,m\|≤exp⁡\(O⁡\(m​n​log⁡n\)\)\.\\left\|\\mathcal\{O\}\_\{n,m\}\\right\|\\leq\\exp\(O\(mn\\log n\)\)\.
2. \(ii\)Almendra\-Hernández and Martínez\-Sandoval[Almendra\-Hernández and Martínez\-Sandoval, 2022](https://arxiv.org/html/2609.02155#bib.bib14)proved that every strict total ordering of theNNpairwise distances is realizable inℝn−2\\mathbb\{R\}^\{n\-2\}\. Their February 2026 correction, prompted by a construction of Maldonado, Raggi Pérez, and Roldán\-Pensado[Maldonado et al\., 2026](https://arxiv.org/html/2609.02155#bib.bib15), leaves open whether every ordering is realizable inℝn−3\\mathbb\{R\}^\{n\-3\}\. We call the minimum dimension realizing a specifiednn\-point ordering its*Almendra\-Hernández–Martínez\-Sandoval \(AHMS\) dimension*\. Thus every such ordering has AHMS dimension at mostn−2n\-2\.
3. \(iii\)Consequently, a uniformly random abstract ordering satisfies Pr⁡\(realizable in​ℝm\)≤exp⁡\[−Θ⁡\(n2​log⁡n\)\+O⁡\(m​n​log⁡n\)\],\\Pr\(\\text\{realizable in \}\\mathbb\{R\}^\{m\}\)\\leq\\exp\[\-\\Theta\(n^\{2\}\\log n\)\+O\(mn\\log n\)\],which is superexponentially small whenm=o⁡\(n\)m=o\(n\)\.

The maximal AHMS dimension therefore has orderΘ⁡\(n\)\\Theta\(n\), although its exact value remains open\.

### D\.1Proof of[theoremD\.1](https://arxiv.org/html/2609.02155#S4.Thmtheorem1)

For part 1, theO⁡\(n4\)O\(n^\{4\}\)comparison polynomials have degree two inm​nmnvariables\. Warren’s sign\-pattern bound[Warren, 1968](https://arxiv.org/html/2609.02155#bib.bib12)gives\(C​s⋅2/\(m​n\)\)m​n=exp⁡\(O⁡\(m​n​log⁡n\)\)\(Cs\\cdot 2/\(mn\)\)^\{mn\}=\\exp\(O\(mn\\log n\)\)realizable patterns\. For part 2, Almendra\-Hernández and Martínez\-Sandoval[Almendra\-Hernández and Martínez\-Sandoval, 2022](https://arxiv.org/html/2609.02155#bib.bib14)established the universaln−2n\-2realization bound\. For part 3,N\!=exp⁡\(Θ⁡\(n2​log⁡n\)\)N\!=\\exp\(\\Theta\(n^\{2\}\\log n\)\)abstract orderings are possible; dividing the sign\-pattern count byN\!N\!proves the probability bound\. ∎

###### Conjecture D\.2\(Typical AHMS dimension\)\.

For Gaussian point clouds whose ambient dimension is at least proportional tonn, the AHMS dimension of the induced strict distance ordering isΩ⁡\(n\)\\Omega\(n\)with high probability\. Thus Gaussian orderings would have the same linear\-dimensional order as the worst case\. More quantitatively, the minimum Kendall distance to𝒪n,m\\mathcal\{O\}\_\{n,m\}should interpolate between the classical counting obstruction and the pairwisem/d\\sqrt\{m/d\}law\. The counting ratio cannot prove this distribution\-specific statement because Gaussian distance orderings are not uniform\.

## EReproducibility and Artifact Generation

We host the manuscript’s executable companion at

[https://github\.com/piyush314/random\-projection\-geometry](https://github.com/piyush314/random-projection-geometry)\.

This companion contains a reusable Python package, a theorem\-level verification harness, paper\-specific reproduction programs, experiment contracts, tutorials, notebooks, and a documentation site\. To ensure exact reproducibility, our manuscript repository includes the companion as a version\-pinned Git submodule undercompanion/\. The recorded submodule commit identifies the exact executable version used for the reported results\.

### E\.1Environment and theorem checks

To initialize the pinned companion and install its development dependencies, run these commands from the manuscript root:

```
git submodule update --init --recursive
python -m pip install -e "companion[dev]"
```

To run the theorem\-level harness, execute

```
python companion/verification/run_all.py
```

The harness evaluates each principal theorem independently and reports a pass/fail summary\. Its checks combine symbolic or exact\-moment identities, deterministic numerical integration, and seeded Monte Carlo experiments, according to the type of claim\.

### E\.2Manuscript tables and figures

Regenerate the numerical rows used in[Tables4](https://arxiv.org/html/2609.02155#S11.T4)and[5](https://arxiv.org/html/2609.02155#S11.T5)from the manuscript root by running

```
python companion/reproduction/paper/verify_claims.py \
  --seed 42 --full --output-dir data
python companion/reproduction/paper/verify_new_results.py \
  --seed 20260812 --full --output-dir data
```

The first program checks the scalar channel, anisotropy, and Gaussian maps\. The second checks balanced spectral blocks, the Gaussian integral for a common minimum, nearest\-neighbor overlap, and JL–Kendall coexistence\. The\-\-fulloption selects the sample sizes reported in the paper; omitting it gives a faster smoke test\. Together, these programs write the machine\-readable results\. The first also generates theLaTeXrows used in[Table4](https://arxiv.org/html/2609.02155#S11.T4); the compact summary in[Table5](https://arxiv.org/html/2609.02155#S11.T5)is maintained in the manuscript source\.

Run the independent Gaussian replacement experiment, including empirical calibration and the exact disjoint\-pairFm,dF\_\{m,d\}comparison used in[proposition3\.4](https://arxiv.org/html/2609.02155#S3.Thmtheorem4), with

```
python companion/experiments/zero_information_jl/run.py \
  --profile full --output companion/artifacts/zero_information_jl
```

This script writes the paper figure, the complete six\-panel diagnostic, CSV files for individual trials, the comparison ofFFratios, and machine\-readable metadata\. The commands that build the archival paper bundle and publication figures invoke the same experiment automatically\.

To regenerate the five publication plots directly in the manuscript tree, run

```
python companion/scripts/generate_paper_assets.py \
  --output figures/plots
```

The companion repository also provides reproduction notebooks that expose the same calculations interactively\. Its documentation records the expected outputs, experiment contracts, dependency versions, and continuous\-integration checks\.

## References

- V\. H\. Almendra\-Hernández and L\. Martínez\-SandovalOn prescribing total orders and preorders to pairwise distances of points in Euclidean space\.Computational Geometry107,pp\. 101898\.Note:See arXiv:2111\.08895v2 \(February 2026\) for the correction to the sharpness claimExternal Links:[Document](https://dx.doi.org/10.1016/j.comgeo.2022.101898),2111\.08895Cited by:[item \(ii\)](https://arxiv.org/html/2609.02155#S4.I1.i2.p1.1),[§D\.1](https://arxiv.org/html/2609.02155#S4.SS1a.p1.1)\.
- Alon \(2003\)N\. AlonProblems and results in extremal combinatorics—I\.Discrete Mathematics273\(1–3\),pp\. 31–53\.External Links:[Document](https://dx.doi.org/10.1016/S0012-365X%2803%2900227-9)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1)\.
- Baiket al\.\(2005\)J\. Baik, G\. Ben Arous, and S\. PéchéPhase transition of the largest eigenvalue for nonnull complex sample covariance matrices\.The Annals of Probability33\(5\),pp\. 1643–1697\.Cited by:[Conjecture 13\.3](https://arxiv.org/html/2609.02155#S13.Thmtheorem3.p1.1.1)\.
- Bentkus \(2003\)V\. BentkusOn the dependence of the Berry–Esseen bound on dimension\.Journal of Statistical Planning and Inference113\(2\),pp\. 385–402\.External Links:[Document](https://dx.doi.org/10.1016/S0378-3758%2802%2900094-0)Cited by:[§B\.9](https://arxiv.org/html/2609.02155#S2.SS9.p3.1),[§7\.3](https://arxiv.org/html/2609.02155#S7.SS3.p4.1)\.
- Beyeret al\.\(1999\)K\. Beyer, J\. Goldstein, R\. Ramakrishnan, and U\. ShaftWhen is “nearest neighbor” meaningful?\.InInternational Conference on Database Theory \(ICDT\),pp\. 217–235\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1),[§2](https://arxiv.org/html/2609.02155#S2.p2.3)\.
- Bilu and Linial \(2005\)Y\. Bilu and N\. LinialMonotone maps, sphericity and bounded second eigenvalue\.Journal of Combinatorial Theory, Series B95\(2\),pp\. 283–299\.External Links:[Document](https://dx.doi.org/10.1016/j.jctb.2005.04.005)Cited by:[§D](https://arxiv.org/html/2609.02155#S4a.p1.1)\.
- Cannings and Samworth \(2017\)T\. I\. Cannings and R\. J\. SamworthRandom\-projection ensemble classification\.Journal of the Royal Statistical Society: Series B79\(4\),pp\. 959–1035\.Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px4.p1.1)\.
- Chari and Pachter \(2023\)T\. Chari and L\. PachterThe specious art of single\-cell genomics\.PLOS Computational Biology19\(8\),pp\. e1011288\.External Links:[Document](https://dx.doi.org/10.1371/journal.pcbi.1011288)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1)\.
- Charikar \(2002\)M\. CharikarSimilarity estimation techniques from rounding algorithms\.InProceedings of the 34th Annual ACM Symposium on Theory of Computing \(STOC\),pp\. 380–388\.Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px1.p1.1)\.
- Chen and Rubin \(1986\)J\. Chen and H\. RubinBounds for the difference between median and mean of Gamma and Poisson distributions\.Statistics & Probability Letters4\(6\),pp\. 281–283\.External Links:[Document](https://dx.doi.org/10.1016/0167-7152%2886%2990044-1)Cited by:[§B\.1](https://arxiv.org/html/2609.02155#S2.SS1.p1.3)\.
- Cover and Thomas \(2006\)T\. M\. Cover and J\. A\. ThomasElements of information theory\.2nd edition,Wiley\.Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px3.p1.1),[§5\.1](https://arxiv.org/html/2609.02155#S5.SS1.p2.1)\.
- Dasguptaet al\.\(2006\)S\. Dasgupta, D\. Hsu, and N\. VermaA concentration theorem for projections\.InProceedings of the 22nd Conference on Uncertainty in Artificial Intelligence \(UAI\),Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1),[§8\.3](https://arxiv.org/html/2609.02155#S8.SS3.p1.2)\.
- Dasgupta \(1999\)S\. DasguptaLearning mixtures of Gaussians\.In40th Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 634–644\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1),[§8\.2](https://arxiv.org/html/2609.02155#S8.SS2.p3.1),[§8\.3](https://arxiv.org/html/2609.02155#S8.SS3.p1.2)\.
- Dasgupta \(2000\)S\. DasguptaExperiments with random projection\.InProceedings of the 16th Conference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 143–151\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1),[§8\.3](https://arxiv.org/html/2609.02155#S8.SS3.p1.2)\.
- Davidet al\.\(1977\)H\. A\. David, M\. J\. O’Connell, and S\. S\. YangDistribution and expected value of the rank of a concomitant of an order statistic\.The Annals of Statistics5\(1\),pp\. 216–223\.External Links:[Document](https://dx.doi.org/10.1214/aos/1176343756)Cited by:[§7\.3](https://arxiv.org/html/2609.02155#S7.SS3.p5.2)\.
- de Klerket al\.\(2004\)E\. de Klerk, D\. V\. Pasechnik, and J\. P\. WarnersOn approximate graph colouring and MAX\-kk\-CUT algorithms based on theϑ\\vartheta\-function\.Journal of Combinatorial Optimization8\(3\),pp\. 267–294\.External Links:[Document](https://dx.doi.org/10.1023/B%3AJOCO.0000038911.67280.3F)Cited by:[Research Direction 13\.2](https://arxiv.org/html/2609.02155#S13.Thmtheorem2.p1.1)\.
- Demboet al\.\(2001\)A\. Dembo, A\. Kagan, and L\. A\. SheppRemarks on the maximum correlation coefficient\.Bernoulli7\(2\),pp\. 343–350\.Cited by:[§B\.3](https://arxiv.org/html/2609.02155#S2.SS3.p2.1),[§4\.2](https://arxiv.org/html/2609.02155#S4.SS2.p1.3),[§5\.1](https://arxiv.org/html/2609.02155#S5.SS1.p1.1)\.
- Diaconis and Freedman \(1984\)P\. Diaconis and D\. FreedmanAsymptotics of graphical projection pursuit\.The Annals of Statistics12\(3\),pp\. 793–815\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1)\.
- Durrant and Kabán \(2009\)R\. J\. Durrant and A\. KabánWhen is ‘nearest neighbour’ meaningful: a converse theorem and implications\.Journal of Complexity25\(4\),pp\. 385–397\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1)\.
- Edelman \(1988\)A\. EdelmanEigenvalues and condition numbers of random matrices\.SIAM Journal on Matrix Analysis and Applications9\(4\),pp\. 543–560\.External Links:[Document](https://dx.doi.org/10.1137/0609045)Cited by:[§A\.1](https://arxiv.org/html/2609.02155#S1.SS1.p1.3)\.
- Fern and Brodley \(2003\)X\. Z\. Fern and C\. E\. BrodleyRandom projection for high dimensional data clustering: a cluster ensemble approach\.InInternational Conference on Machine Learning \(ICML\),pp\. 186–193\.Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px4.p1.1)\.
- Frieze and Jerrum \(1997\)A\. M\. Frieze and M\. JerrumImproved approximation algorithms for MAXkk\-CUT and MAX BISECTION\.Algorithmica18\(1\),pp\. 67–81\.External Links:[Document](https://dx.doi.org/10.1007/BF02523688)Cited by:[§7\.3](https://arxiv.org/html/2609.02155#S7.SS3.p6.1)\.
- Geet al\.\(2013\)T\. Ge, K\. He, Q\. Ke, and J\. SunOptimized product quantization for approximate nearest neighbor search\.InIEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 2946–2953\.Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px3.p1.1)\.
- Griffiths \(1969\)R\. C\. GriffithsThe canonical correlation coefficients of bivariate gamma distributions\.The Annals of Mathematical Statistics40\(4\),pp\. 1401–1408\.Cited by:[§B\.4](https://arxiv.org/html/2609.02155#S2.SS4.p1.1),[§5\.2](https://arxiv.org/html/2609.02155#S5.SS2.p1.1),[Theorem 5\.2](https://arxiv.org/html/2609.02155#S5.Thmtheorem2.p1.2.1)\.
- Halkoet al\.\(2011\)N\. Halko, P\. Martinsson, and J\. A\. TroppFinding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions\.SIAM Review53\(2\),pp\. 217–288\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1),[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px2.p1.1),[§4\.3](https://arxiv.org/html/2609.02155#S4.SS3.p2.1)\.
- Hanin and Nica \(2020\)B\. Hanin and M\. NicaProducts of many large random matrices and gradients in deep neural networks\.Communications in Mathematical Physics376\(1\),pp\. 287–322\.External Links:[Document](https://dx.doi.org/10.1007/s00220-019-03624-z)Cited by:[§A](https://arxiv.org/html/2609.02155#S1a.p1.1)\.
- Hoeffding \(1963\)W\. HoeffdingProbability inequalities for sums of bounded random variables\.Journal of the American Statistical Association58\(301\),pp\. 13–30\.External Links:[Document](https://dx.doi.org/10.1080/01621459.1963.10500830)Cited by:[§B\.10](https://arxiv.org/html/2609.02155#S2.SS10.p1.3),[§3\.1](https://arxiv.org/html/2609.02155#S3.SS1.p5.1.1),[§7\.4](https://arxiv.org/html/2609.02155#S7.SS4.p3.1)\.
- Indyk and Motwani \(1998\)P\. Indyk and R\. MotwaniApproximate nearest neighbors: towards removing the curse of dimensionality\.InProceedings of the 30th Annual ACM Symposium on Theory of Computing \(STOC\),pp\. 604–613\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1),[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px1.p1.1)\.
- Jégouet al\.\(2011a\)H\. Jégou, M\. Douze, and C\. SchmidProduct quantization for nearest neighbor search\.IEEE Transactions on Pattern Analysis and Machine Intelligence33\(1\),pp\. 117–128\.Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px3.p1.1)\.
- Jégouet al\.\(2011b\)H\. Jégou, R\. Tavenard, M\. Douze, and L\. AmsalegSearching in one billion vectors: re\-rank with source coding\.InIEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\),pp\. 861–864\.External Links:[Document](https://dx.doi.org/10.1109/ICASSP.2011.5946540)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1)\.
- Johnsonet al\.\(2021\)J\. Johnson, M\. Douze, and H\. JégouBillion\-scale similarity search with GPUs\.IEEE Transactions on Big Data7\(3\),pp\. 535–547\.External Links:[Document](https://dx.doi.org/10.1109/TBDATA.2019.2921572)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1)\.
- Johnson and Lindenstrauss \(1984\)W\. B\. Johnson and J\. LindenstraussExtensions of Lipschitz mappings into a Hilbert space\.InConference on Modern Analysis and Probability,Contemporary Mathematics, Vol\.26,pp\. 189–206\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p2.1)\.
- Kendall \(1938\)M\. G\. KendallA new measure of rank correlation\.Biometrika30\(1–2\),pp\. 81–93\.External Links:[Document](https://dx.doi.org/10.1093/biomet/30.1-2.81)Cited by:[§7](https://arxiv.org/html/2609.02155#S7.p2.2)\.
- Khotet al\.\(2007\)S\. Khot, G\. Kindler, E\. Mossel, and R\. O’DonnellOptimal inapproximability results for MAX\-CUT and other 2\-variable CSPs?\.SIAM Journal on Computing37\(1\),pp\. 319–357\.External Links:[Document](https://dx.doi.org/10.1137/S0097539705447372)Cited by:[Research Direction 13\.2](https://arxiv.org/html/2609.02155#S13.Thmtheorem2.p1.1),[Research Direction 13\.2](https://arxiv.org/html/2609.02155#S13.Thmtheorem2.p1.2)\.
- Kusupatiet al\.\(2022\)A\. Kusupati, G\. Bhatt, A\. Rege, M\. Wallingford, A\. Sinha, V\. Ramanujan, W\. Howard\-Snyder, K\. Chen, S\. Kakade, P\. Jain, and A\. FarhadiMatryoshka representation learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§12](https://arxiv.org/html/2609.02155#S12.SS0.SSS0.Px3.p1.1),[Research Direction 13\.5](https://arxiv.org/html/2609.02155#S13.Thmtheorem5.p1.1)\.
- Larsen and Nelson \(2017\)K\. G\. Larsen and J\. NelsonOptimality of the Johnson–Lindenstrauss lemma\.In58th Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 633–638\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2017.64),1609\.02094Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1)\.
- Laurent and Massart \(2000\)B\. Laurent and P\. MassartAdaptive estimation of a quadratic functional by model selection\.The Annals of Statistics28\(5\),pp\. 1302–1338\.External Links:[Document](https://dx.doi.org/10.1214/aos/1015957395)Cited by:[§C](https://arxiv.org/html/2609.02155#S3a.p3.5.1)\.
- Li and Malik \(2016\)K\. Li and J\. MalikFastkk\-nearest neighbour search via Dynamic Continuous Indexing\.InInternational Conference on Machine Learning \(ICML\),pp\. 671–679\.Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p4.1)\.
- Maldonadoet al\.\(2026\)G\. L\. Maldonado, M\. Raggi Pérez, and E\. Roldán\-PensadoTotal orders realizable as the distances between two sets of points\.Discrete Applied Mathematics378,pp\. 755–761\.External Links:[Document](https://dx.doi.org/10.1016/j.dam.2025.10.002),2304\.05535Cited by:[item \(ii\)](https://arxiv.org/html/2609.02155#S4.I1.i2.p1.1)\.
- Marchenko and Pastur \(1967\)V\. A\. Marchenko and L\. A\. PasturDistribution of eigenvalues for some sets of random matrices\.Mathematics of the USSR\-Sbornik1\(4\),pp\. 457–483\.External Links:[Document](https://dx.doi.org/10.1070/SM1967v001n04ABEH001994)Cited by:[§A\.1](https://arxiv.org/html/2609.02155#S1.SS1.p1.1)\.
- Martinsson and Tropp \(2020\)P\. Martinsson and J\. A\. TroppRandomized numerical linear algebra: foundations and algorithms\.Acta Numerica29,pp\. 403–572\.External Links:[Document](https://dx.doi.org/10.1017/S0962492920000021)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1)\.
- Milnor \(1964\)J\. MilnorOn the Betti numbers of real varieties\.Proceedings of the American Mathematical Society15\(2\),pp\. 275–280\.Cited by:[item \(i\)](https://arxiv.org/html/2609.02155#S4.I1.i1.p1.1)\.
- Moonet al\.\(2019\)K\. R\. Moon, D\. van Dijk, Z\. Wang, S\. Gigante, D\. B\. Burkhardt, W\. S\. Chen, K\. Yim, A\. van den Elzen, M\. J\. Hirn, R\. R\. Coifman, N\. B\. Ivanova, G\. Wolf, and S\. KrishnaswamyVisualizing structure and transitions in high\-dimensional biological data\.Nature Biotechnology37\(12\),pp\. 1482–1492\.External Links:[Document](https://dx.doi.org/10.1038/s41587-019-0336-3)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1)\.
- Radovanovićet al\.\(2010\)M\. Radovanović, A\. Nanopoulos, and M\. IvanovićHubs in space: popular nearest neighbors in high\-dimensional data\.Journal of Machine Learning Research11,pp\. 2487–2531\.Cited by:[Research Direction 13\.4](https://arxiv.org/html/2609.02155#S13.Thmtheorem4.p1.1)\.
- Rényi \(1959\)A\. RényiOn measures of dependence\.Acta Mathematica Academiae Scientiarum Hungaricae10\(3–4\),pp\. 441–451\.External Links:[Document](https://dx.doi.org/10.1007/BF02024507)Cited by:[§4\.2](https://arxiv.org/html/2609.02155#S4.SS2.p1.3),[§4\.2](https://arxiv.org/html/2609.02155#S4.SS2.p1.4)\.
- Saelenset al\.\(2019\)W\. Saelens, R\. Cannoodt, H\. Todorov, and Y\. SaeysA comparison of single\-cell trajectory inference methods\.Nature Biotechnology37\(5\),pp\. 547–554\.External Links:[Document](https://dx.doi.org/10.1038/s41587-019-0071-9)Cited by:[§1](https://arxiv.org/html/2609.02155#S1.p1.1)\.
- Sheppard \(1899\)W\. F\. SheppardOn the application of the theory of error to cases of normal distribution and normal correlation\.Philosophical Transactions of the Royal Society of London, Series A192,pp\. 101–167\.Cited by:[§B\.8](https://arxiv.org/html/2609.02155#S2.SS8.p1.1),[§7\.1](https://arxiv.org/html/2609.02155#S7.SS1.p2.1)\.
- van der Vaart \(1998\)A\. W\. van der VaartAsymptotic statistics\.Cambridge Series in Statistical and Probabilistic Mathematics, Vol\.3,Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/CBO9780511802256)Cited by:[§8](https://arxiv.org/html/2609.02155#S8.p2.3)\.
- Warren \(1968\)H\. E\. WarrenLower bounds for approximation by nonlinear manifolds\.Transactions of the American Mathematical Society133\(1\),pp\. 167–178\.Cited by:[item \(i\)](https://arxiv.org/html/2609.02155#S4.I1.i1.p1.1),[§D\.1](https://arxiv.org/html/2609.02155#S4.SS1a.p1.1)\.
- Witsenhausen \(1975\)H\. S\. WitsenhausenOn sequences of pairs of dependent random variables\.SIAM Journal on Applied Mathematics28\(1\),pp\. 100–113\.External Links:[Document](https://dx.doi.org/10.1137/0128010)Cited by:[§B\.7](https://arxiv.org/html/2609.02155#S2.SS7.p1.3),[§6\.2](https://arxiv.org/html/2609.02155#S6.SS2.p3.3)\.
- Zhang and Zhou \(2020\)A\. R\. Zhang and Y\. ZhouOn the non\-asymptotic and sharp lower tail bounds of random variables\.Stat9\(1\),pp\. e314\.External Links:[Document](https://dx.doi.org/10.1002/sta4.314)Cited by:[§B\.1](https://arxiv.org/html/2609.02155#S2.SS1.p1.3),[§3\.3](https://arxiv.org/html/2609.02155#S3.SS3.p2.1)\.