High-Dimensional Procrustes Matching via Tree Counts

Suppose we observe two sets of n Gaussian vectors in ℝd, with the promise that, after applying a permutation of [n] and a rotation of ℝ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 dgg 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≥ polylog(n), the algorithm succeeds with high probability for any ρ2>√α, where α≈ 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 maxlog n/d,√log n/n. We also carry out a low-degree advantage calculation, which suggests that the condition ρ2 > √α is necessary for any tree-counting algorithm.