Thumbnail

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

Voir/Ouvrir
Type
Document de travail / Working paper
Lien vers un document non conservé dans cette base
https://hal.archives-ouvertes.fr/hal-03176512
Date
2021
Titre de la collection
Cahier de recherche du CEREMADE
Pages
10
Métadonnées
Afficher la notice complète
Auteur(s)
Carlier, Guillaume
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Résumé (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].
Mots-clés
Block coordinate descent; Linear convergence; Sinkhorn algorithm; Multi-marginal entropic optimal transport