# Phase transition of the Sinkhorn-Knopp algorithm

arXiv: https://arxiv.org/abs/2507.09711 · HTML: https://mlsanity.com/paper/2507.09711/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 13 Jul 2025.

## Builds on (most cited first, 7 of 7)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [Much Faster Algorithms for Matrix Scaling](https://mlsanity.com/paper/1704.02315/) (2017)
- [Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods](https://mlsanity.com/paper/1704.02310/) (2017)
- [Ensemble Quadratic Assignment Network for Graph Matching](https://mlsanity.com/paper/2403.06457/) (2024)

## Built on by (most cited first, 1 of 1)

- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

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.