Limit points of the iterative scaling procedure

DOI10.1007/S10479-013-1416-2MaRDI QIDQ744663zbMATH OpenOpenAlexFDO

Authors Erik Aas

Publication date 26 September 2014

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

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

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)

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.

Review text

The iterative scaling procedure (ISP) generates a sequence of matrices rescaling alternately its rows and columns to arrive at a matrix with prescribed row and column sums. If the starting matrix \(A\) is connected with nonnegative elements, ISP will converge. However, when this iterative process has two limit points, convergence is slow. This paper gives an efficient algorithm to find both limit points in such a case. The idea is to partition the sets of row and column indices. These define blocks which are then iteratively refined. This gives a decomposition of the matrix, and the iteration can be performed on subblocks. This paper appeared in a special issue of the journal and another paper in that issue discusses a similar problem (cf. [\textit{F. Pukelsheim}, ibid. 215, 269--283 (2014; Zbl 1302.65114)]).

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

Cites work

• Convergence of the Iterative Scaling Procedure for Non-Negative Matrices
• scientific article; zbMATH DE number 3872359 (Why is no real title available?)
• Information Theory and Statistics: A Tutorial
• Matrices and politics
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• The Sinkhorn–Knopp Algorithm: Convergence and Applications

Cited in

(9)

• Limit analysis with the dual affine scaling algorithm
• Termination of the iterative proportional fitting procedure
• On the extended iterative proportional scaling algorithm
• A Parallel Matrix Scaling Algorithm
• Iterated Proportional Fitting Procedure and Infinite Products of Stochastic Matrices
• A permutation code preserving a double Eulerian bistatistic
• Theoretical basis of the iterative process of the joint assessment of difficulties in tasks and levels of training students
• Order independence and factor convergence in iterative scaling
• Biproportional scaling of matrices and the iterative proportional fitting procedure

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)