
On the linear convergence of the multi-marginal Sinkhorn algorithm
Carlier, Guillaume (2021), On the linear convergence of the multi-marginal Sinkhorn algorithm. https://basepub.dauphine.psl.eu/handle/123456789/22372
View/ Open
Type
Document de travail / Working paperExternal document link
https://hal.archives-ouvertes.fr/hal-03176512Date
2021Series title
Cahier de recherche du CEREMADEPages
10
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 (2018) Document de travail / Working paper
-
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é