  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. Hence, we next propose a new algorithm with
convergence guarantees. The idea is to overrelax the Bregman projection
operators, allowing for faster convergence. 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.
