Исследователи представляют алгоритм полиномиального времени для точного восстановления в задаче высокоразмерного прокрустова сопоставления, где два набора гауссовых векторов выравниваются посредством неизвестной перестановки и вращения. Метод вычисляет взвешенные подсчёты широких деревьев для достижения этого выравнивания.

  • Алгоритм успешно работает с высокой вероятностью, когда размерность $d \ge \mathrm{polylog}(n)$ и квадрат корреляции $\rho^2 > \sqrt{\alpha}$, где $\alpha \approx 0.338$ — константа подсчёта деревьев Оттера.
  • Улучшенная информационно-теоретическая гарантия показывает, что точное восстановление возможно при $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$.
  • Расчёт преимущества низкой степени предполагает, что условие $\rho^2 > \sqrt{\alpha}$ необходимо для любого алгоритма подсчёта деревьев.

Эта работа решает ранее неисследованный высокоразмерный режим, в котором предыдущие гарантии требовали почти идеальной корреляции.