Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling

DOI10.1007/s10107-020-01503-3OpenAlexW3016365586MaRDI QIDQ2039246

Sanjeev Khanna, Deeparnab Chakrabarty

Publication date: 2 July 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-020-01503-3

zbMATH Keywords

matchingsKL divergencematrix scalingalternate minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Related Items (3)

Semi-discrete optimal transport: hardness, regularization and numerical solution ⋮ Apportionment with parity constraints ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The rate of convergence of Sinkhorn balancing
• On pairs of multidimensional matrices
• An extension of a theorem of Darroch and Ratcliff in loglinear models and its application to scaling multidimensional matrices
• On the scaling of multidimensional matrices
• Scalings of matrices which have prespecified row sums and column sums via optimization
• Approximate distributions of order statistics. With applications to nonparametric statistics
• I-divergence geometry of probability distributions and minimization problems
• On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms
• A geometric interpretation of Darroch and Ratcliff's generalized iterative scaling
• Convergence of the iterative proportional fitting procedure
• On the complexity of nonnegative-matrix scaling
• On the complexity of general matrix scaling and entropy minimization via the RAS algorithm
• Concerning nonnegative matrices and doubly stochastic matrices
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• A User's Guide to Measure Theoretic Probability
• Quantum computing and hidden variables
• The Sinkhorn–Knopp Algorithm: Convergence and Applications
• A parallel approximation algorithm for positive linear programming
• Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel
• Estimating Nonnegative Matrices from Marginal Data
• Reduction of a Matrix with Positive Elements to a Doubly Stochastic Matrix
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents

This page was built for publication: Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling