On the Wasserstein alignment problem

Abstract

Suppose we are given two metric spaces and a family of continuous transformations from one to the other. Given a probability distribution on each of these two spaces -- namely the source and the target measures -- the Wasserstein alignment problem seeks the transformation that minimizes the optimal transport cost between the pushforward of the source distribution and the target distribution, ensuring the closest possible alignment in a probabilistic sense. Examples of interest include two distributions on two Euclidean spaces ${\mathbb{R}}^n$ and ${\mathbb{R}}^d$, and we want a spatial embedding of the $n$-dimensional source measure in ${\mathbb{R}}^d$ that is closest in some Wasserstein metric to the target distribution on ${\mathbb{R}}^d$. Similar data alignment problems also commonly arise in shape analysis and computer vision. In this paper, we show that this nonconvex optimal transport projection problem admits a convex Kantorovich-type dual that exploits statistical independence. This allows us to characterize the set of projections and devise a linear programming algorithm. For certain special examples, such as orthogonal transformations on Euclidean spaces of unequal dimensions and the $2$-Wasserstein cost, we characterize the covariance of the optimal projections. Our results also cover the generalization when we penalize each transformation by a function. An example is the inner product Gromov--Wasserstein distance minimization problem which has recently gained popularity.

34 pages, 4 figures. To appear in SIAM Journal on Mathematics of Data Science