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 places 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 n× n matrix, its normalized version is obtained by dividing each entry by its largest entry. We say that a normalized matrix has a density γ if there exists a constant ρ > 0 such that one row or column has exactly lceil γ n rceil entries with values at least ρ, and every other row and column has at least lceil γ n rceil such entries. For the upper bound, we show that the Sinkhorn-Knopp algorithm produces a nearly doubly stochastic matrix in O(log n - log varepsilon) iterations and widetildeO(n2) 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, and the widetildeO(n2) runtime is optimal. For the lower bound, we establish a tight bound of widetildeOmegaleft(n1/2/varepsilonright) iterations for positive matrices under the ℓ2-norm error measure. Moreover, for every γ < 1/2, there exists a matrix with density γ for which the algorithm requires Omegaleft(n1/2/varepsilonright) iterations. In summary, our results reveal a sharp phase transition in the Sinkhorn-Knopp algorithm at the density threshold γ = 1/2.