Para peneliti menyajikan algoritma waktu polinomial untuk pemulihan eksak dalam masalah pencocokan Procrustes berdimensi tinggi, di mana dua himpunan vektor Gaussian disejajarkan melalui permutasi dan rotasi yang tidak diketahui. Metode ini menghitung hitungan pohon lebar berbobot untuk mencapai penyelarasan ini.
- Algoritma berhasil dengan probabilitas tinggi ketika dimensi $d \ge \mathrm{polylog}(n)$ dan kuadrat korelasi $\rho^2 > \sqrt{\alpha}$, di mana $\alpha \approx 0.338$ adalah konstanta penghitungan pohon Otter.
- Jaminan teori informasi yang ditingkatkan menunjukkan bahwa pemulihan eksak mungkin terjadi ketika $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$.
- Perhitungan keunggulan derajat rendah menyarankan bahwa kondisi $\rho^2 > \sqrt{\alpha}$ diperlukan untuk setiap algoritma penghitungan pohon.
Karya ini mengatasi rezim berdimensi tinggi yang sebelumnya belum terjamah di mana jaminan sebelumnya memerlukan korelasi hampir sempurna.