High-Dimensional Procrustes Matching via Tree Counts

arXiv:2607.08538v1 Announce Type: cross Abstract: Suppose we observe two sets of n Gaussian vectors in R^d, with the promise that, after applying a permutation of [n] and a rotation of R^d, the two sets are rho-correlated. The Procrustes matching problem asks us to recover the unknown permutation of [n] that aligns the two sets. The problem is well-studied in the low-dimensional regime d=O(log n), but the high-dimensional regime dgg log n has remained largely uncharted: prior matching guarantees require nearly perfect correlation rho=1-o(1), even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide'' trees. So long as dge polylog(n), the algorithm succeeds with high probability for any rho^2>sqrt{alpha}, where alphaapprox 0.338 is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when rho^2 gtrsim max{log n/d,sqrt{log n/n}}. We also carry out a low-degree advantage calculation, which suggests that the condition rho^2 > sqrt{alpha} is necessary for any tree-counting algorithm.

Source: arXiv cs.LG | 2026-07-10