
On the linear convergence of the multi-marginal Sinkhorn algorithm
Carlier, Guillaume (2022), On the linear convergence of the multi-marginal Sinkhorn algorithm, SIAM Journal on Optimization, 32, 2. 10.1137/21M1410634
View/ Open
Type
Article accepté pour publication ou publiéDate
2022Journal name
SIAM Journal on OptimizationVolume
32Number
2Publisher
SIAM - Society for Industrial and Applied Mathematics
Publication identifier
Metadata
Show full item recordAbstract (EN)
The aim of this short note is to give an elementary proof of linear convergence of the Sinkhorn algorithm for the entropic regularization of multi-marginal optimal transport. The proof simply relies on: i) the fact that Sinkhorn iterates are bounded, ii) strong convexity of the exponential on bounded intervals and iii) the convergence analysis of the coordinate descent (Gauss-Seidel) method of Beck and Tetruashvili [1].Subjects / Keywords
Block coordinate descent; Linear convergence; Sinkhorn algorithm; Multi-marginal entropic optimal transportRelated items
Showing items related by title and author.
-
Benamou, Jean-David; Carlier, Guillaume; Nenna, Luca (2019) Article accepté pour publication ou publié
-
Carlier, Guillaume; Laborde, Maxime (2020) Article accepté pour publication ou publié
-
Benamou, Jean-David; Carlier, Guillaume; Nenna, Luca (2017) Chapitre d'ouvrage
-
Abraham, Isabelle; Abraham, Romain; Bergounioux, Maïtine; Carlier, Guillaume (2017) Article accepté pour publication ou publié
-
Bleyer, Jérémy; Carlier, Guillaume; Duval, Vincent; Mirebeau, Jean-Marie; Peyré, Gabriel (2016) Article accepté pour publication ou publié