The Procrustes-Wasserstein problem consists in matching two high-dimensional
point clouds in an unsupervised setting, and has many applications in natural
language processing and computer vision. We consider a planted model with two
datasets $X,Y$ that consist of $n$ datapoints in $\mathbb{R}^d$, where $Y$ is a
noisy version of $X$, up to an orthogonal transformation and a relabeling of
the data points. This setting is related to the graph alignment problem in
geometric models. In this work, we focus on the euclidean transport cost
between the point clouds as a measure of performance for the alignment. We
first establish information-theoretic results, in the high ($d \gg \log n$) and
low ($d \ll \log n$) dimensional regimes. We then study computational aspects
and propose the Ping-Pong algorithm, alternatively estimating the orthogonal
transformation and the relabeling, initialized via a Franke-Wolfe convex
relaxation. We give sufficient conditions for the method to retrieve the
planted signal after one single step. We provide experimental results to
compare the proposed approach with the state-of-the-art method of Grave et al.
(2019).

我们研究了 Procrustes-Wasserstein 问题，使用欧几里得传输成本作为性能度量，提出了 Ping-Pong 算法，用于匹配高维点云，并与现有方法进行比较。