新算法实现恒定相关性下的高维普鲁克雷斯匹配

研究人员提出了一种用于高维普鲁克雷斯（Procrustes）匹配问题精确恢复的多项式时间算法，其中两组高斯向量通过未知的排列和旋转进行对齐。该方法通过计算宽树的加权计数来实现此对齐。

• 当维度 $d \ge \mathrm{polylog}(n)$ 且相关性平方 $\rho^2 > \sqrt{\alpha}$ 时，该算法以高概率成功，其中 $\alpha \approx 0.338$ 是 Otter 的树计数常数。
• 改进的信息论保证表明，当 $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$ 时，精确恢复是可能的。
• 低阶优势计算表明，对于任何树计数算法，条件 $\rho^2 > \sqrt{\alpha}$ 是必要的。

这项工作解决了以前未探索的高维区域，此前的保证需要近乎完美的相关性。