{"ID":6267231,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-13T01:02:08.706470581Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08538","arxiv_id":"2607.08538","title":"High-Dimensional Procrustes Matching via Tree Counts","abstract":"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 $ρ$-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 $ρ=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 $ρ^2\u003e\\sqrtα$, where $α\\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 $ρ^2 \\gtrsim \\max\\{\\log n/d,\\sqrt{\\log n/n}\\}$. We also carry out a low-degree advantage calculation, which suggests that the condition $ρ^2 \u003e \\sqrtα$ is necessary for any tree-counting algorithm.","short_abstract":"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 $ρ$-correlated. The Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets. The problem...","url_abs":"https://arxiv.org/abs/2607.08538","url_pdf":"https://arxiv.org/pdf/2607.08538v1","authors":"[\"Xiaochun Niu\",\"Tselil Schramm\",\"Jiaming Xu\"]","published":"2026-07-09T14:33:47Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.IT\",\"cs.LG\",\"math.ST\"]","methods":"[]","has_code":false}