On the Convergence of the Sinkhorn-Knopp Algorithm with Sparse Cost Matrices

This paper presents a theoretical analysis of the convergence rate of the Sinkhorn-Knopp algorithm when the cost matrix is sparse. We derive bounds on the convergence rate that depend on the sparsity pattern and the degree of nonsparsity of the cost matrix. We also explore connections to existing convergence results for dense cost matrices. Our analysis provides new insights into the behavior of the Sinkhorn-Knopp algorithm in the presence of sparsity and highlights potential avenues for algorithmic improvements.