Phase transition of the Sinkhorn-Knopp algorithm
This provides theoretical insights into a long-standing algorithm in matrix scaling, with implications for optimization and machine learning applications, though it is incremental in refining bounds.
The paper tackles the problem of understanding the empirical efficiency and establishing tight iteration bounds for the Sinkhorn-Knopp algorithm, showing that it achieves nearly doubly stochastic matrices in O(log n - log ε) iterations for matrices with density γ > 1/2, and requires Ω(n^{1/2}/ε) iterations for γ < 1/2, revealing a sharp phase transition at γ = 1/2.
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\times 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 $\widetilde{O}(n^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, and the $\widetilde{O}(n^2)$ runtime is optimal. For the lower bound, we establish a tight bound of $\widetildeΩ\left(n^{1/2}/\varepsilon\right)$ iterations for positive matrices under the $\ell_2$-norm error measure. Moreover, for every $γ< 1/2$, there exists a matrix with density $γ$ for which the algorithm requires $Ω\left(n^{1/2}/\varepsilon\right)$ iterations. In summary, our results reveal a sharp phase transition in the Sinkhorn-Knopp algorithm at the density threshold $γ= 1/2$.