Machine Learning in Montpellier, Theory & Practice
The Procrustes-Wasserstein problem consists in matching two high-dimensional point clouds in an unsupervised setting, and has applications in natural language processing and computer vision. This talk will first introduce and motivate this problem, before considering a planted model with two random datasets $X,Y$ that consist of $n$ datapoints in $\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 as we will show. Focusing 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, and provide geometrical and probabilistic insights to explain the dichotomy between these two regimes. We then study computational aspects and propose intuitive algorithms to approximate solutions for this problem, alternatively estimating the orthogonal transformation and the relabeling, initialized via a convex relaxation.