# High-Dimensional Procrustes Matching via Tree Counts

arXiv: https://arxiv.org/abs/2607.08538 · HTML: https://mlsanity.com/paper/2607.08538/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 51 references that are in the map.
- First posted on arXiv 9 Jul 2026.

## Builds on (most cited first, 2 of 2)

- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)

## Abstract (arXiv)

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.