Other
Sinkhorn–Knopp
1967ActivePublished: 29 September 2026Updated: 29 September 2026Published
Key
innovation
An iterative algorithm that scales a matrix to doubly stochastic form by alternately normalising rows and columns — the basis of entropic optimal transport in ML.
Category
Other
Abstraction level
Primitive
Operation level
TrainingInference
Use cases
Entropic optimal transport (Sinkhorn distances)Expert routing in mixtures-of-experts (MoE)Self-supervised clustering (SwAV)Differentiable matching and assignmentNormalising matrices to doubly stochastic
How it works
Starting from a kernel matrix K = exp(−C/ε) (C = cost, ε = regularisation), the algorithm alternately scales rows and columns by vectors u, v so the marginals match the target distributions. On convergence, diag(u)·K·diag(v) is the transport matrix. The iterations are simple matrix–vector products, ideal for GPUs and differentiable.
Problem solved
Exact optimal transport is expensive (linear programming). Sinkhorn–Knopp gives a fast, differentiable, parallelisable approximation via entropic regularisation.
Components
Entropic kernel K = exp(−C/ε)Iteration input
Exponential transform of the cost matrix with regularisation ε.
Alternating row/column scalingCore of the algorithm
Updating vectors u, v to match the marginals.
Evolution
1967
Sinkhorn–Knopp theorem on doubly stochastic matrices
Inflection point2013
Cuturi: Sinkhorn distances — fast, differentiable optimal transport in ML
Inflection point2020
SwAV uses Sinkhorn for self-supervised clustering