• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport

Thumbnail
View/Open
hal_(1).pdf (330.4Kb)
Date
2017
Dewey
Traitement du signal
Sujet
Sinkhorn-Knopp Algorithm
Conference name
NIPS'17 Workshop on Optimal Transport & Machine Learning
Conference date
12-2017
Conference city
Long Beach
Conference country
United States
Year
2017
URI
https://basepub.dauphine.fr/handle/123456789/20514
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Thibault, Alexis
91477 Ecole Normale Supérieure
Chizat, Lénaïc
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Dossal, Charles
1954 Institut de Mathématiques de Toulouse UMR5219 [IMT]
Papadakis, Nicolas
27730 Institut de Mathématiques de Bordeaux [IMB]
Type
Communication / Conférence
Abstract (EN)
This article describes a method for quickly computing the solution to the regularized optimal transport problem. It generalizes and improves upon the widely-used iterative Bregman projections algorithm (or Sinkhorn-Knopp algorithm). The idea is to overrelax the Bregman projection operators, allowing for faster convergence. In practice this corresponds to elevating the diagonal scaling factors to a given power, at each step of the algorithm. We propose a simple method for establishing global convergence by ensuring the decrease of a Lyapunov function at each step. An adaptive choice of overrelaxation parameter based on the Lyapunov function is constructed. We also suggest a heuristic to choose a suitable asymptotic overrelaxation parameter, based on a local convergence analysis. Our numerical experiments show a gain in convergence speed by an order of magnitude in certain regimes.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.