2017

Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport

Thibault, Alexis, Chizat, Lénaïc, Dossal, Charles et al.

Understand

This article describes a set of methods 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).
We first propose to rely on regularized nonlinear acceleration schemes.
In practice, such approaches lead to fast algorithms, but their global convergence is not ensured.

Built on

Ix. the approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam
L. F. Richardson · 1911
Earlier work this paper cites.
Some methods of speeding up the convergence of iteration methods
B. Polyak · 1964
Earlier work this paper cites.
A relationship between arbitrary positive matrices and doubly stochastic matrices
R. Sinkhorn · 1964
Earlier work this paper cites.
Iterative procedures for nonlinear integral equations
D. G. Anderson · 1965
Earlier work this paper cites.
The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
L. M. Bregman · 1967
Earlier work this paper cites.
Introduction à l’analyse numérique matricielle et à l’optimisation
P. Ciarlet · 1982
Earlier work this paper cites.
On the optimization of the classical iterative schemes for the solution of complex singular linear systems
A. Hadjidimos · 1985
Earlier work this paper cites.
Heavy-ball method in nonconvex optimization problems
S. K. Zavriev and F. V. Kostyuk · 1993
Earlier work this paper cites.
The Earth Mover’s Distance as a metric for image retrieval
Y. Rubner, C. Tomasi, and L. J. Guibas · 2000
Earlier work this paper cites.
The Sinkhorn–Knopp algorithm: convergence and applications
P. A. Knight · 2008
Earlier work this paper cites.
Sinkhorn distances: Lightspeed computation of optimal transport
M. Cuturi · 2013
Earlier work this paper cites.
Global convergence of the Heavy-ball method for convex optimization
Original
E. Ghadimi, H. R. Feyzmahdavian, and M. Johansson · 2014
Earlier work this paper cites.
Non-convex relaxation of optimal transport for color transfer between images
J. Rabin and N. Papadakis · 2014
Earlier work this paper cites.

Similar

Iterative solution of large linear systems
D. M. Young · 2014
Cited alongside, same era.
Iterative Bregman projections for regularized transportation problems
J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré · 2015
Cited alongside, same era.
Optimal Transport for Domain Adaptation
Original
N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy · 2015
Cited alongside, same era.
Learning with a Wasserstein Loss
Original
C. Frogner, C. Zhang, H. Mobahi, M. Araya-Polo, and T. Poggio · 2015
Cited alongside, same era.
Principal geodesic analysis for probability measures under the optimal transport metric
V. Seguy and M. Cuturi · 2015
Cited alongside, same era.
Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains
J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas · 2015
Cited alongside, same era.
Scaling Algorithms for Unbalanced Transport Problems
Original
L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard · 2016
Cited alongside, same era.
Wasserstein training of restricted boltzmann machines
G. Montavon, K.-R. Müller, and M. Cuturi · 2016
Cited alongside, same era.
Local Convergence of the Heavy-ball Method and iPiano for Non-convex Optimization
Original
P. Ochs · 2016
Cited alongside, same era.
Quantum optimal transport for tensor field processing
Original
G. Peyré, L. Chizat, F.-X. Vialard, and J. Solomon · 2016
Cited alongside, same era.
Fast dictionary learning with a smoothed Wasserstein loss
A. Rolet, M. Cuturi, and G. Peyré · 2016
Cited alongside, same era.
Stabilized sparse scaling algorithms for entropy regularized transport problems
Original
B. Schmitzer · 2016
Cited alongside, same era.

Then

Regularized Nonlinear Acceleration
Original
D. Scieur, A. d’Aspremont, and F. Bach · 2016
Later among the works it cites.
Near-linear time approximation algorithms for optimal transport via sinkhorn iteration
Original
J. Altschuler, J. Weed, and P. Rigollet · 2017
Closest in time.
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
Original
J. Altschuler, J. Weed, and P. Rigollet · 2017
Closest in time.
Unbalanced optimal transport: models, numerical methods, applications
L. Chizat · 2017
Closest in time.
Overrelaxed sinkhorn-knopp algorithm for regularized optimal transport
Original
A. Thibault, L. Chizat, C. Dossal, and N. Papadakis · 2017
Closest in time.
Regularized optimal transport and the rot mover’s distance
A. Dessein, N. Papadakis, and J.-L. Rouas · 2018
Closest in time.
Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learning
M. A. Schmitz, M. Heitz, N. Bonneel, F. Ngole, D. Coeurjolly, M. Cuturi, G. Peyré, and J.-L. Starck · 2018
Closest in time.
Online regularized nonlinear acceleration
Original
D. Scieur, E. Oyallon, A. d’Aspremont, and F. Bach · 2018
Closest in time.
Screening sinkhorn algorithm for regularized optimal transport
Original
M. Z. Alaya, M. Berar, G. Gasso, and A. Rakotomamonjy · 2019
Closest in time.
A generic online acceleration scheme for optimization algorithms via relaxation and inertia
F. Iutzeler and J. M. Hendrickx · 2019
Closest in time.
Computational optimal transport
G. Peyré and M. Cuturi · 2019
Closest in time.
A note on overrelaxation in the sinkhorn algorithm
Original
T. Lehmann, M.-K. von Renesse, A. Sambale, and A. Uschmajew · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…