Phase transition of the Sinkhorn-Knopp algorithm

The matrix scaling problem, particularly the Sinkhorn-Knopp algorithm, has been studied for over 60 years. In practice, the algorithm often yields high-quality approximations within just a few iterations. Theoretically, however, the best known upper bound on its iteration count scales polynomially with the accuracy parameter 𝜀, placing it in the class of pseudopolynomial-time approximation algorithms. Meanwhile, the lower-bound landscape remains largely unexplored. Two fundamental questions persist: what accounts for the algorithm's strong empirical performance, and can a tight bound on its iteration count be established?

For an 𝑛 × 𝑛 matrix, its normalized version is obtained by dividing each entry by the largest entry in the matrix. We say that a normalized matrix has a density 𝛾 if there exists a constant 𝜌 > 0 such that one row or column has exactly ⌈𝛾𝑛⌉ entries with values at least 𝜌, and every other row and column has at least ⌈𝛾𝑛⌉ such entries.

For the upper bound, we show that the Sinkhorn-Knopp algorithm produces a nearly doubly stochastic matrix in 𝑂 (log 𝑛log 𝜀) iterations and Õ (𝑛 2 ) time for all nonnegative square matrices whose normalized version has a density 𝛾 > 1/2. Such matrices cover both the algorithm's principal practical inputs and its typical theoretical regime. This Õ (𝑛 2 ) runtime is optimal, as merely reading the input requires Ω(𝑛 2 ) time. In fact, the algorithm is optimal for nearly all nonnegative matrices with entries bounded above by a constant, demonstrating its practical efficiency.

For the lower bound, we establish a tight bound of Ω √ 𝑛/𝜀 iterations for positive matrices under the ℓ 2 -norm error measure. Moreover, for every 𝛾 < 1/2, there exists a matrix with density 𝛾 for which the Sinkhorn-Knopp algorithm requires Ω √ 𝑛/𝜀 iterations. In summary, our results reveal a sharp phase transition in the Sinkhorn-Knopp algorithm at the density threshold 𝛾 = 1/2. Moreover, we demonstrate that convergence improves as matrix density increases, thereby accounting for prior observations in entropically regularised optimal transport that larger inverse temperature slows convergence.