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 \(\varepsilon\), 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?