Les chercheurs présentent un algorithme en temps polynomial pour la récupération exacte dans le problème de mise en correspondance de Procrustes à haute dimension, où deux ensembles de vecteurs gaussiens sont alignés via une permutation et une rotation inconnues. La méthode calcule des comptes pondérés d'arbres larges pour réaliser cet alignement.
- L'algorithme réussit avec une forte probabilité lorsque la dimension $d \ge \mathrm{polylog}(n)$ et le carré de la corrélation $\rho^2 > \sqrt{\alpha}$, où $\alpha \approx 0.338$ est la constante de comptage d'arbres d'Otter.
- Une garantie informationnelle-théorique améliorée montre que la récupération exacte est possible lorsque $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$.
- Un calcul d'avantage de bas degré suggère que la condition $\rho^2 > \sqrt{\alpha}$ est nécessaire pour tout algorithme de comptage d'arbres.
Ce travail traite du régime à haute dimension auparavant inexploré où les garanties antérieures nécessitaient une corrélation quasi parfaite.