The Sinkhorn-Knopp Algorithm: Convergence and Applications

By Philip A. Knight. 2008

468 citations recorded by the source corpus.

As long as a square nonnegative matrix $A$ contains sufficient nonzero elements, the Sinkhorn-Knopp algorithm can be used to balance the matrix, that is, to find a diagonal scaling of $A$ that is doubly stochastic. We relate balancing to problems in traffic flow and describe how balancing algorithms can be used to give a two sided measure of nodes in a graph. We show that with an appropriate modification, the Sinkhorn-Knopp algorithm is a natural candidate for computing the measure on enormous data sets.

Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Condensed Matter Physics

In Statistics and Probability

Citations in the corpus

Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “Given a decentralized network G, there are many approaches to obtain a doubly stochastic W, for example, Sinkhorn matrix scaling [21].”
Sinkhorn Distances: Lightspeed Computation of Optimal Transport (2013, background): “Such algorithms include Sinkhorn’s celebrated ﬁxed point iteration (1967), which is known to have a linear convergence (Franklin and Lorenz, 1989; Knight, 2008).”
Computational Optimal Transport (2018, background): “We refer to [Knight, 2008] for more details in the bistochastic (assignment) case.”
Optimal Transport for Domain Adaptation (2014, methodology): “Another appealing outcome of the regularized OT formulation given in Equation (9) is the derivation of a computationally efficient algorithm based on Sinkhorn-Knopp’s scaling matrix approach [30].”
A Tour of Modern Image Filtering: New Insights and Methods, Both Practical and Theoretical (2013, methodology): “W K = Z W That is to say, applying Sinkhorn's algorithm to either k or its row-sum normalized version w yields the very same SPD doubly stochastic) result, .”
A Fast Algorithm for Matrix Balancing (2013, background): “in solving the large scale balancing problems discussed in [12], where a rank one correction is applied implicitly to A.”
A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps (2016, methodology): “Algorithm 5.9 (Knight 2008).”
Entropic regularization of continuous optimal transport problems (2019, methodology): “Furthermore, in the discrete setting, this allows to solve the problem numerically by the very simple Sinkhorn algorithm [23, 17, 4].”
Domain Adaptation with Regularized Optimal Transport (2014, methodology): “This iterative algorithm is of particular interest in our case as it consists in iteratively using an efficient Sinkhorn-Knopp matrix scaling approach.”
DeepPermNet: Visual Permutation Learning (2017, background): “Sinkhorn [40, 41] showed that any non-negative square matrix (with full support [22]) can be converted to a DSM by alternating between rescaling its rows and columns to one.”
Low-Shot Learning with Large-Scale Diffusion (2017, background): “As discussed by Knight [26], the convergence of this algorithm is fast.”
Fast Exact Hyper-graph Matching with Dynamic Programming for Spatio-temporal Data (2014, unknown): “They extended the Sinkhorn algorithm [23], which is used for soft assignment in combinatorial problems, to obtain a global optimum in the special case when the two graphs have the same number of vertices and an exact matching is desired.”
Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Experts (2021, methodology): “As an alternative to generating balanced samples, we can balance the distribution in expectation by using a generalization of the Sinkhorn algorithm [39, 40, 21] to non-square matrices, which iteratively normalizes the columns and rows of the probability matrix pij = pθ(zi = j|xi) to sum to nk and 1”