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

DOI10.1007/S41884-021-00062-6zbMATH Open1495.90109OpenAlexW3217042118MaRDI QIDQ2154656FDOQ2154656

Authors Daiji Tsutsui 

Publication date 20 July 2022

Published in Information Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.13683

zbMATH Keywords

discrete optimal transportconvex optimizationinformation geometryWasserstein barycenterentropic regularization

Mathematics Subject Classification ID

Convex programming (90C25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Abstract: In order to circumvent the difficulties in solving numerically the discrete optimal transport problem, in which one minimizes the linear target function $PmapstolangleC,Pangle:=su{m}_{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)=langleC,Pangle-lambdamathcalH(P)$, where $mathcalH$ is the Shannon entropy and $lambda$ is a positive constant. We herein generalize their formulation to a target function of the form $Phi(P)=langleC,Pangle+lambdaf(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)=frac12|P{|}^2$.

Recommendations

• Optimal transport via a Monge-Ampère optimization problem
• Iterative Bregman projections for regularized transportation problems
• Discrete optimal transport: complexity, geometry and applications
• Entropic regularization of continuous optimal transport problems
• Quadratically regularized optimal transport

Cites Work

• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• A smoothed dual approach for variational Wasserstein problems
• Barycenters in the Wasserstein space
• Computational optimal transport. With applications to data sciences
• Information geometry connecting Wasserstein distance and Kullback-Leibler divergence via the entropy-relaxed transportation problem
• Iterative Bregman projections for regularized transportation problems
• On the scaling of multidimensional matrices
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Quadratically regularized optimal transport on graphs
• The geometry of proper scoring rules

Cited In (18)

• Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
• Randomized methods for computing optimal transport without regularization and their convergence analysis
• Optimal transport via a Monge-Ampère optimization problem
• A geometric variational framework for computing spherical optimal transportation maps. II
• Minimizing optimal transport for functions with fixed-size nodal sets
• Orlicz space regularization of continuous optimal transport problems
• Generalized unnormalized optimal transport and its fast algorithms
• An iterative scheme for solving the optimal transportation problem
• Iterative Bregman projections for regularized transportation problems
• The GenCol Algorithm for High-Dimensional Optimal Transport: General Formulation and Application to Barycenters and Wasserstein Splines
• Quadratically regularized optimal transport
• A stable alternative to Sinkhorn's algorithm for regularized optimal transport
• A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
• When optimal transport meets information geometry
• Discrete optimal transport: complexity, geometry and applications
• A geometric view of optimal transportation and generative model
• Computations of optimal transport distance with Fisher information regularization
• Optimal transport with proximal splitting

This page was built for publication: Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2154656)