Published Paper

Inserted: 12 jul 2024

Journal: Journal of Scientific Computing
Year: 2024
Doi: https://doi.org/10.1007/s10915-024-02572-8

Abstract:

We address the numerical solution to multimarginal optimal transport (MMOT) with pairwise costs. MMOT, as a natural extension from the classical two-marginal optimal transport, has many impor- tant applications including image processing, density functional theory and machine learning, but lacks efficient and exact numerical methods. The popular entropy-regularized method may suffer nu- merical instability and blurring issues. Inspired by the back-and-forth method introduced by Jacobs and L ́eger, we investigate MMOT problems with pairwise costs. We show that such problems have a graphical representation and leverage this structure to develop a new computationally gradient ascent algorithm to solve the dual formulation of such MMOT problems. Our method produces ac- curate solutions which can be used for the regularization-free applications, including the computation of Wasserstein barycenters with high resolution imagery.

Keywords: Optimal transport, multimarginal optimal transport, Wasserstein barycenter, graphical structure