Los investigadores presentan un algoritmo de tiempo polinomial para la recuperación exacta en el problema de coincidencia de Procrustes de alta dimensión, donde dos conjuntos de vectores gaussianos se alinean mediante una permutación y rotación desconocidas. El método calcula conteos ponderados de árboles anchos para lograr esta alineación.
- El algoritmo tiene éxito con alta probabilidad cuando la dimensión $d \ge \mathrm{polylog}(n)$ y el cuadrado de la correlación $\rho^2 > \sqrt{\alpha}$, donde $\alpha \approx 0.338$ es la constante de conteo de árboles de Otter.
- Una garantía teórico-informática mejorada muestra que la recuperación exacta es posible cuando $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$.
- Un cálculo de ventaja de bajo grado sugiere que la condición $\rho^2 > \sqrt{\alpha}$ es necesaria para cualquier algoritmo de conteo de árboles.
Este trabajo aborda el régimen de alta dimensión previamente inexplorado donde las garantías anteriores requerían una correlación casi perfecta.