Comparative Analysis of Computational Methods for Optimal Transport

Abstract

This thesis presents a comparative and experimental study of computational methods for discrete optimal transport under the squared-Euclidean cost. We benchmark the exact simplex method, the Sinkhorn algorithm, first-order and quasi-Newton dual ascent, a chi-square-regularized primal-dual hybrid gradient (PDHG) method, and the Back-and-Forth method, across dimensions d in {1, 2, 3}, a range of grid resolutions and regularization levels, and a family of distributions varying in modality, tail thickness, skewness, and anisotropy. Solvers are assessed against three criteria - stability, runtime, and accuracy - and the conclusions are validated on a colour-transfer application. There we find that in RGB colour space the exact solver is not always preferable to a smoother, slightly biased map, which scores better on the structure-preservation metrics of SSIM, gradient correlation, and Laplacian sharpness. Beyond the comparison, we introduce a new method for the outer-regularized 2-Wasserstein barycenter based on Sobolev gradient ascent on the dual functionals combined with the Back-and-Forth c-transform, the simplest case of a broader Back-and-Forth Flow framework.