Search papers, labs, and topics across Lattice.
This paper addresses the high-dimensional Procrustes matching problem, where two sets of Gaussian vectors are aligned through an unknown permutation and rotation, focusing on the case where the correlation is constant rather than near-perfect. The authors introduce a polynomial-time algorithm that leverages weighted counts of a specific family of "wide" trees to achieve exact recovery under these conditions, succeeding with high probability when the dimensionality is sufficiently large. Additionally, they provide an improved information-theoretic guarantee for exact recovery, establishing necessary conditions for the algorithm's success.
Exact recovery of high-dimensional Procrustes matching is achievable with a polynomial-time algorithm, even at constant correlation levels.
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 $\rho$-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 $\rho=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 \mathrm{polylog}(n)$, the algorithm succeeds with high probability for any $\rho^2>\sqrt{\alpha}$, where $\alpha\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 $\rho^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$. We also carry out a low-degree advantage calculation, which suggests that the condition $\rho^2>\sqrt{\alpha}$ is necessary for any tree-counting algorithm.
