High-Dimensional Procrustes Matching via Tree Counts

Suppose we observe two sets of n Gaussian vectors in \mathbb{R}^d, with the promise that, after applying a permutation of [n] and a rotation of \mathbb{R}^d, the two sets are ρ-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 d\gg \log n has remained largely uncharted: prior matching guarantees require nearly perfect correlation ρ=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 d\ge polylog(n), the algorithm succeeds with high probability for any ρ^2>\sqrtα, where α\approx 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 ρ^2 \gtrsim \max{\log n/d,\sqrt{\log n/n}}. We also carry out a low-degree advantage calculation, which suggests that the condition ρ^2 > \sqrtα is necessary for any tree-counting algorithm.