提出高维点集匹配新算法，常数相关下可精确恢复排列。
High-Dimensional Procrustes Matching via Tree Counts
- 通过计数特殊‘宽树’的加权结构实现匹配
- 在d≥polylog(n)时，ρ²>√α≈0.58可成功恢复
- 适用于高维数据对齐，尤其适合相关性不高的场景
假设在ℝ^d中观测到两组各n个高斯向量，存在一个[𝑛]上的未知排列和ℝ^d上的旋转，使两组向量具有ρ-相关性。Procrustes匹配问题旨在恢复该未知排列。在低维情形𝑑=𝑂(𝑙𝑜𝑔𝑛)已有充分研究，但高维情形𝑑≫𝑙𝑜𝑔𝑛仍不明确：此前匹配保证需近乎完美相关性𝜌=1−𝑜(1)，即便信息论上也如此。本文提出一种多项式时间算法，在常数相关性下实现精确恢复。该算法通过计算并比较一组特殊‘宽树’的加权计数完成。当𝑑≥𝑝𝑜𝑙𝑦𝑙𝑜𝑔(𝑛)时，只要𝜌²>√𝛼（𝛼≈0.338为Otter树计数常数），算法以高概率成功。我们还给出了改进的信息论下界：精确恢复在𝜌²≳max{𝑙𝑜𝑔𝑛/𝑑,√𝑙𝑜𝑔𝑛/𝑛}时可行。此外，低度优势分析表明，对任何树计数类算法，𝜌²>√𝛼是必要的。
原文摘要 · Abstract (English)
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>\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 > \sqrtα$ is necessary for any tree-counting algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。