A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices

By Richard Sinkhorn. 1964

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

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

In Numerical Methods & Scientific Computing

Citations in the corpus

Beyond English-Centric Multilingual Machine Translation (2020, methodology): “To identify a feasible solution to this problem, we use the Sinkhorn-Knopp algorithm (Sinkhorn, 1964; Sinkhorn and Knopp, 1967).”
Efficient Transformers: A Survey (2020, methodology): “Sinkhorn Sorting φ is the Sinkhorn balancing operator (Sinkhorn, 1964; Adams and Zemel, 2011) which converts the n B × n B matrix into a soft permutation matrix.”
Wireless Network Intelligence at the Edge (2018, methodology): “By utilizing the knowledge of the parametric representation of Gd(x′), the function F du u can be derived, while α (Q) is calculated using the Sinkhorn algorithm [154].”
Model Fusion via Optimal Transport (2019, methodology): “The regularized problem is then solved efficiently using Sinkhorn iterations (Sinkhorn, 1964).”
Sparse Sinkhorn Attention (2020, background): “Concretely, at the heart of our sorting network lives a differentiable Sinkhorn balancing mechanism (Adams & Zemel, 2011; Mena et al., 2018), which normalizes permutation matrices to belong to the Birkhoff polytope, the set of doubly stochastic matrices (Sinkhorn, 1964).”
Learning Generative Models with Sinkhorn Divergences (2017, methodology): “One major advantage of regularizing the optimal transport problem is that it becomes solvable efficiently using Sinkhorn’s algorithm [32] (when dealing with discrete measures), and leads to a differentiable loss function (as first noticed in [9, 10]).”
Computational Optimal Transport (2018, background): “Note that the basic Sinkhorn iterations described in Equation (4.15) are intrinsically GPU friendly, since they only consist in matrix-vector products, and this was exploited, for instance, to solve matching problems in Slomp et al. [2011]).”
Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes (2007, methodology): “s section, we recall bounds for #(R,C) obtained in [Ba07] and [Ba08]. (6.1) Matrix scaling. Our estimates for the number #(R,C) of contingency tables essentially use the theory of matrix scaling, see [Si64], [MO68], [RS89]. Let us ﬁx non-negative vectors R = (r1,... ,rm), C = (c1,... ,cn), such that”
Context Mover's Distance & Barycenters: Optimal transport of contexts for building representations (2018, methodology): “The regularized problem can then be solved efficiently using Sinkhorn iterations (Sinkhorn, 1964), albeit at the cost of some approximation error.”
A Scaling Algorithm to Equilibrate Both Rows and Columns Norms in Matrices 1 (2001, background): “Sinkhorn ( 1964 ) originally showed that : Any positive square matrix of order n is diagonally equivalent to a unique doubly stochastic matrix of order n , and the diagonal matrices which take part in the equivalence are unique up to scalar factors .”
Much Faster Algorithms for Matrix Scaling (2017, methodology): “The matrix ( r, c )-scaling problem is so natural and important that it was discovered independently by many diﬀerent scientiﬁc communities, starting in 1937 with the work of Kruithof [20] in telephone forecasting, Deming and Stephan [10] in transportation science, Brown [8] in engineering, Stone [3”
The Concave-Convex Procedure (2003, methodology): “Then Sinkhorn’s theorem states: Theorem (Sinkhorn, 1964).”
Vision-Based Pose Estimation From Points With Unknown Correspondences (2014, methodology): “Since the summation of each row and each column of M should be 1, a technique due to Sinkhorn is applied to normalize a square correspondence matrix [31].”
A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps (2016, background): “k to at least the 30s and Kruithof’s use of the method in telephone forecasting (Kruithof1937). At a similar time, according to Bregman1967, the Soviet architect Sheleikhovskii considered the method. Sinkhorn 1964claims that when he started to evaluate the method, it had already been proposed and in”
The Concave-Convex Procedure (CCCP) (2001, methodology): “This algorithm was reported by Kosowsky and Yuille in [5] where it was also shown to correspond to the well-known Sinkhorn algorithm [9].”
Fast geometric learning with symbolic matrices (2020, unknown): “…� � To demonstrate this, we solver [13, 42] against several variants and implementations of the Sinkhorn algorithm: a vanilla Sinkhorn loop [27, 29, 34, 41, 44, 94, 98, 112, 117]; an accelerated algorithm with simulated annealing [71]; and a fast multiscale scheme with kernel truncation [10, 96].”