Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport
DOSSAL, Charles
Institut National des Sciences Appliquées - Toulouse [INSA Toulouse]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
See more >
Institut National des Sciences Appliquées - Toulouse [INSA Toulouse]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
DOSSAL, Charles
Institut National des Sciences Appliquées - Toulouse [INSA Toulouse]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
< Reduce
Institut National des Sciences Appliquées - Toulouse [INSA Toulouse]
Institut de Mathématiques de Toulouse UMR5219 [IMT]
Language
en
Communication dans un congrès
This item was published in
NIPS Workshop on Optimal Transport & Machine Learning (OTML'17), 2017-12-09, Long Beach.
English Abstract
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 ...Read more >
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.Read less <
ANR Project
Generalized Optimal Transport Models for Image processing - ANR-16-CE33-0010
Origin
Hal imported