Search papers, labs, and topics across Lattice.
This paper conducts a thorough local convergence analysis of the Sinkhorn-Knopp (SK) algorithm for matrix scaling, addressing a significant gap in the understanding of its local linear convergence behavior. By establishing a nonasymptotic framework that aligns with asymptotic Jacobian-based results, the authors demonstrate that SK operates as a polynomial-time algorithm under specific connectivity conditions. Additionally, they present accelerated variants and improve the complexity of existing first-order matrix scaling algorithms for dense matrices, achieving a notable reduction from \(O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})\) to \(O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})\).
Local convergence of the Sinkhorn-Knopp algorithm can be achieved with polynomial-time efficiency, challenging previous assumptions about its scaling limits.
We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We show that under certain connectivity conditions, SK is a polynomial-time algorithm for doubly stochastic matrix scaling. With the developed tools, we showcase the local suboptimality of SK and provide accelerated variants. Finally, for dense matrices, we improve the complexity of existing first-order matrix scaling algorithms from $O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})$ to $O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})$.
