Fast Alignment of Embeddings: Computational Guarantees for Anisotropic Procrustes-Wasserstein

The Procrustes-Wasserstein problem asks to match the vectors in two unlabeled point clouds $X$ and $Y$, which are related via a latent orthogonal transformation. This problem appears in unsupervised representation alignment, domain adaptation, and geometric matching, but its computational theory remains limited. We study a planted Gaussian model in which $Y$ is obtained from $X$ via an unknown relabeling, an unknown orthogonal transformation, and additive noise. Departing from the isotropic setting considered in prior work, we assume that the covariance of $X$ is anisotropic, with a power-law spectrum. While closer to real-world data, this structure also enables a directions-first approach: Estimate the dominant eigenspaces of both point clouds, then recover the matching. We prove that a polynomial-time version of this procedure exactly recovers the true relabeling with high probability under explicit scaling conditions. To our knowledge, this is the first computational recovery guarantee for Procrustes-Wasserstein with nontrivial observational noise and dimensions beyond $\log n$, where $n$ is the number of points. Experiments on synthetic data and 3D shapes support the theory, showing that anisotropy favors directions-first methods, can lower runtime and improve recovery.