Concerning nonnegative matrices and doubly stochastic matrices

By Richard Sinkhorn, Paul Knopp. 1967

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

Unified Scaling Laws for Routed Language Models (2022, methodology): “2 SMoE with Sinkhorn redistribution (S-BASE) Our implementation of S-BASE differs from that proposed in Lewis et al. [2021] in two ways.”
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).”
Co-Transport for Class-Incremental Learning (2021, methodology): “However, with the smoothness of entropy regularization term, OT can be solved through Sinkhorn algorithm [8, 38], which is much faster.”
Sinkhorn Distances: Lightspeed Computation of Optimal Transport (2013, background): “iew, this regularization has multiple virtues, among which that of turning this LP into a strictly convex problem that can be solved extremely quickly with the SinkhornKnopp matrix scaling algorithm (Sinkhorn and Knopp, 1967; Knight, 2008). This algorithm exhibits linear convergence and can be trivi”
Theoretical Analysis of Domain Adaptation with Optimal Transport (2016, methodology): “Here, the second term E(γ) = − ∑NS ,NT i,j γi,j log(γi,j) is the regularization term that allows one to solve optimal transportation problem efficiently using Sinkhorn-Knopp matrix scaling algorithm [25].”
The Sinkhorn-Knopp Algorithm: Convergence and Applications (2008, background): “This work was supported in part by a grant from the Carnegie Trust for the Universities of Scotland.”
Iterative Bregman Projections for Regularized Transportation Problems (2014, methodology): “This algorithm was later studied in detail by Sinkhorn in [54, 56, 55] and its convergence proof was extended to continuous measures in [51].”
SuperGlue: Learning Feature Matching With Graph Neural Networks (2019, methodology): “Related to graph matching is the problem of optimal transport [57] – it is a generalized linear assignment with an efficient yet simple approximate solution, the Sinkhorn algorithm [49, 11, 36].”
Bregman Alternating Direction Method of Multipliers (2013, methodology): “We present promising preliminary empirical resultsfor BADMM applied to optimization over doubly stochastic matrices.”
Fast Differentiable Sorting and Ranking (2020, methodology): “Their method is based on differentiating through the iterates of the Sinkhorn algorithm (Sinkhorn & Knopp, 1967), thereby costing O ( Tn 2 ) time, where T is the number of Sinkhorn iterations.”
Differentiable Top-k with Optimal Transport (2020, unknown): “The KKT condition implies that ⇤,✏ can be formulated using the optimal dual variables ⇠⇤ and ⇣⇤ as (Sinkhorn’s scaling theorem, Sinkhorn and Knopp (1967)), ⇤,✏ = diag(e ⇠⇤ ✏ )e C ✏ diag(e ⇣⇤ ✏ ).”
CoFiNet: Reliable Coarse-to-fine Correspondences for Robust Point Cloud Registration (2021, methodology): “On S (cid:48) we run the Sinkhorn Algorithm [37, 38, 39], seeking an optimal solution for the optimal transport problem.”
Word Alignment by Fine-tuning Embeddings on Parallel Corpora (2021, methodology): “The optimal transition matrix Sxy to Equation 1 can be calculated using the Sinkhorn-Knopp matrix scaling algorithm (Sinkhorn and Knopp, 1967).”
Entropic Approximation of Wasserstein Gradient Flows (2015, methodology): “He shows that this corresponds to the application of the well-known iterative diagonal scaling algorithm, which is sometimes referred to as Sinkhorn’s algorithm [63, 65, 64] or iterative proportional fitting procedure [36].”
A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps (2016, methodology): “The RAS method converges and the product of the diagonal matrices of the iteration also converges to positive diagonal matrices (Sinkhorn and Knopp 1967).”
Low-Shot Learning with Large-Scale Diffusion (2017, methodology): “For this purpose, we adopt a strategy similar to that of Cuturi [9] in his work on optimal transport, in which he shows that the Sinkhorn-Knopp algorithm [32] provides an efficient and theoretically grounded way to project a matrix so that it satisfies such marginals.”