On the Linear Convergence of the Multimarginal Sinkhorn Algorithm
Guillaume Carlier
Abstract
The aim of this note is to give an elementary proof of linear convergence of the Sinkhorn algorithm for the entropic regularization of multimarginal optimal transport in the setting of general probability spaces. The proof simply relies on (i) the fact that Sinkhorn iterates are bounded, (ii) the strong convexity of the exponential on bounded intervals, and (iii) the convergence analysis of the coordinate descent (Gauss--Seidel) method of Beck and Tetruashvili [SIAM J. Optim, 23 (2013), pp. 2037--2060].
Topics & Concepts
MathematicsIterated functionBounded functionConvexityConvergence (economics)Applied mathematicsDiscrete mathematicsMathematical analysisFinanceEconomic growthEconomicsGeometric Analysis and Curvature FlowsOptimization and Variational AnalysisNonlinear Partial Differential Equations