Tree-counting algorithm solves high-dimensional Procrustes matching
Polynomial-time exact recovery at constant correlation ρ² > 0.581, even in high dimensions...
The Procrustes matching problem asks: given two sets of n Gaussian vectors in ℝ^d, find the unknown permutation that aligns them after an optimal rotation. Until now, exact recovery was only possible in low dimensions (d = O(log n)) or with nearly perfect correlation. In their latest arXiv preprint (2607.08538), Xiaochun Niu, Tselil Schramm, and Jiaming Xu crack the high-dimensional regime (d ≫ log n) with a polynomial-time algorithm. Their key insight: compute and compare weighted counts of specially designed 'wide' trees. The algorithm succeeds with high probability as long as ρ² > √α, where α ≈ 0.338 is Otter's tree-counting constant, and d ≥ polylog(n). This achieves constant correlation recovery—a leap from prior constraints requiring ρ = 1 - o(1). The authors also derive an improved information-theoretic lower bound, showing exact recovery is possible when ρ² ≳ max{log n/d, √(log n/n)}. Additionally, they present a low-degree advantage calculation suggesting that the ρ² > √α condition is necessary for any tree-counting method.
- Polynomial-time exact recovery at constant correlation ρ² > 0.581 (√0.338)
- Works when dimension d ≥ polylog(n), far beyond the low-dimensional regime
- Uses weighted counts of wide trees; information-theoretic bound ρ² ≳ √(log n/n) also achieved
Why It Matters
Enables robust alignment of high-dimensional datasets, with applications in genomics, computer vision, and network analysis.