Accelerating operator Sinkhorn iteration with overrelaxation
This work provides incremental improvements to operator Sinkhorn iteration for researchers working on operator scaling problems.
The authors propose overrelaxation-accelerated operator Sinkhorn iterations for operator scaling, proving local convergence rates via linearization and global convergence for a geodesic variant. Numerical experiments show speedups over the standard iteration in some applications.
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 us 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.