  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.
