Optimal transport problems regularized by generic convex functions: A geometric and algorithmic approach

Abstract

In order to circumvent the difficulties in solving numerically the discrete optimal transport problem, in which one minimizes the linear target function $P\mapsto ⟨C,P⟩:={\sum }_{i,j}{C}_{ij}{P}_{ij}$, Cuturi introduced a variant of the problem in which the target function is altered by a convex one $\Phi (P)=⟨C,P⟩-\lambda \mathcal{H}(P)$, where $\mathcal{H}$ is the Shannon entropy and $\lambda$ is a positive constant. We herein generalize their formulation to a target function of the form $\Phi (P)=⟨C,P⟩+\lambda f(P)$, where $f$ is a generic strictly convex smooth function. We also propose an iterative method for finding a numerical solution, and clarify that the proposed method is particularly efficient when $f(P)=\frac{1}{2}\Vert P{\Vert }^2$.

References in corpus (1)

• Learning with a Wasserstein Loss