A note on overrelaxation in the Sinkhorn algorithm - Tobias Lehmann; Max-K. von Renesse; Alexander Sambale; André Uschmajew (Optimization Letters, 2021)
We derive an a priori parameter range for overrelaxation of the Sinkhorn algorithm, which guarantees global convergence and a strictly faster asymptotic local convergence. Guided by the spectral analysis of the linearized problem we pursue a zero cost procedure to choose a near optimal relaxation parameter.
Keywords: 510; Sinkhorn algorithm; Matrix scaling; Overrelaxation; Optimal transport