Limit points of the iterative scaling procedure

DOI10.1007/S10479-013-1416-2zbMATH Open1302.65112arXiv1207.5462OpenAlexW1972855724MaRDI QIDQ744663FDOQ744663

Authors: Erik Aas 

Publication date: 26 September 2014

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: The iterative scaling procedure (ISP) is an algorithm which computes a sequence of matrices, starting from some given matrix. The objective is to find a matrix 'proportional' to the given matrix, having given row and column sums. In many cases, for example if the initial matrix is strictly positive, the sequence is convergent. In the general case, it is known that the sequence has at most two limit points. When these are distinct, convergence can be slow. We give an efficient algorithm which finds these limit points, invoking the ISP only on instances for which the procedure is convergent.

Full work available at URL: https://arxiv.org/abs/1207.5462

Recommendations

• Accumulation points of the iterative proportional fitting procedure
• Biproportional scaling of matrices and the iterative proportional fitting procedure
• Order independence and factor convergence in iterative scaling
• Convergence of the iterative proportional fitting procedure
• Matrix scaling limits in finitely many iterations

zbMATH Keywords

algorithmalternating divergence minimizationbiproportional fittingiterative scaling procedure

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35)

Cites Work

• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• Matrices and politics
• Title not available (Why is that?)
• The Sinkhorn–Knopp Algorithm: Convergence and Applications
• Information Theory and Statistics: A Tutorial
• Convergence of the Iterative Scaling Procedure for Non-Negative Matrices

Cited In (7)

• Order independence and factor convergence in iterative scaling
• On the extended iterative proportional scaling algorithm
• Limit analysis with the dual affine scaling algorithm
• Termination of the iterative proportional fitting procedure
• A Parallel Matrix Scaling Algorithm
• Iterated Proportional Fitting Procedure and Infinite Products of Stochastic Matrices
• A permutation code preserving a double Eulerian bistatistic

This page was built for publication: Limit points of the iterative scaling procedure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744663)