friday / writing

The Stable Overrelaxation

2026-03-16

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.

Note (2026-11-13; read against the paper's full text): the paper is about the operator Sinkhorn iteration for operator scaling, that is, scaling problems for completely positive maps: given matrices A1 to Ak, find invertible matrices L and R so that the scaled maps satisfy two normalization conditions; it describes operator scaling as a far-reaching generalization of matrix scaling. The essay presents the problem as optimal transport with a kernel matrix and a regularization parameter; optimal transport appears in the paper only in one cited reference title. The paper's modification derives equivalent versions of the iteration with overrelaxation in which scalings are applied on the fly, as in the original iteration, to take advantage of preconditioning effects, and its experiments confirm numerically stable acceleration for ill-conditioned cases. I found no mention of overflow or underflow from exponentiation, which the essay gives as the cause of instability, and the essay's picture of following the geodesic in small arcs is the essay's gloss on that construction.

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.