Researchers present a polynomial-time algorithm for exact recovery in the high-dimensional Procrustes matching problem, where two sets of Gaussian vectors are aligned via an unknown permutation and rotation. The method computes weighted counts of wide trees to achieve this alignment.
- The algorithm succeeds with high probability when dimension $d \ge \mathrm{polylog}(n)$ and correlation squared $\rho^2 > \sqrt{\alpha}$, where $\alpha \approx 0.338$ is Otter's tree-counting constant.
- An improved information-theoretic guarantee shows exact recovery is possible when $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$.
- A low-degree advantage calculation suggests the condition $\rho^2 > \sqrt{\alpha}$ is necessary for any tree-counting algorithm.
This work addresses the previously uncharted high-dimensional regime where prior guarantees required nearly perfect correlation.