Pesquisadores apresentam um algoritmo em tempo polinomial para recuperação exata no problema de correspondência de Procrustes de alta dimensão, onde dois conjuntos de vetores gaussianos são alinhados por meio de uma permutação e rotação desconhecidas. O método calcula contagens ponderadas de árvores largas para alcançar esse alinhamento.
- O algoritmo tem sucesso com alta probabilidade quando a dimensão $d \ge \mathrm{polylog}(n)$ e o quadrado da correlação $\rho^2 > \sqrt{\alpha}$, onde $\alpha \approx 0.338$ é a constante de contagem de árvores de Otter.
- Uma garantia teórico-informacional aprimorada mostra que a recuperação exata é possível quando $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$.
- Um cálculo de vantagem de baixo grau sugere que a condição $\rho^2 > \sqrt{\alpha}$ é necessária para qualquer algoritmo de contagem de árvores.
Este trabalho aborda o regime de alta dimensão anteriormente inexplorado onde garantias anteriores exigiam correlação quase perfeita.