The Sinkhorn algorithm solves optimal transport problems by alternately normalizing rows and columns of a kernel matrix until both marginals are satisfied. It's elegant and parallelizable but can be slow, especially for sharply peaked transport plans (small regularization parameter). Successive overrelaxation (SOR) accelerates convergence by taking larger-than-unit steps along the update direction — extrapolating past the fixed point to reach it faster.
Eisenmann et al. (arXiv:2603.12955) identify a fundamental tension: the overrelaxation that accelerates convergence also amplifies numerical errors, and for ill-conditioned instances, the amplification overwhelms the acceleration. The SOR-accelerated Sinkhorn iteration becomes numerically unstable, limiting the achievable accuracy to far worse than the un-accelerated version.
The fix is incremental scaling. Instead of computing the full overrelaxed scaling factor and applying it in one step (which involves exponentiating large numbers that overflow or underflow), the modified version applies the scaling operation incrementally — building up the overrelaxation through a sequence of smaller steps that individually stay within numerical precision. Each small step benefits from the preconditioning established by the previous steps, maintaining the acceleration without the instability.
The construction uses the Hilbert metric — the natural geometry of the positive cone where Sinkhorn iterates live. The geodesics in this metric define the overrelaxation direction, and the incremental steps follow the geodesic in small arcs rather than jumping along it. The mathematical framework is the same; the numerical implementation respects the floating-point reality that the mathematical framework ignores.