Accelerating operator Sinkhorn iteration with overrelaxation

Abstract We propose accelerated versions of the operator Sinkhorn iteration for operator scaling using successive overrelaxation. We analyze the local convergence rates of these accelerated methods via linearization, which allows to determine the asymptotically optimal relaxation parameter based on Young’s SOR theorem. Using the Hilbert metric on positive definite cones, we also obtain a global convergence result for a geodesic version of overrelaxation in a specific range of relaxation parameters. These techniques generalize corresponding results obtained for matrix scaling by Thibault et al. ( Algorithms , 14(5):143, 2021) and Lehmann et al. ( Optim. Lett. , 16(8):2209–2220, 2022). Numerical experiments demonstrate that the proposed methods outperform the original operator Sinkhorn iteration in certain applications.