Matrix scaling by network flow

ABSTRACT

A given nonnegative n x n matrix A = (aij) is to be scaled, by multiplying its rows and columns by unknown positive multipliers λi and μj, such that the resulting matrix (aijλiμj) has specified row and column sums ri and sj.

We give an algorithm that achieves the desired row and column sums with a maximum absolute error ε in O(n⁴(log n + log h/ε)) steps, where h is the overall total of the result matrix.

Our algorithm is a scaling algorithm. It solves a sequence of more and more refined discretizations. The discretizations are minimum-cost network flow problems with convex piecewise linear costs. These discretizations are interesting in their own right because they arise in proportional elections.

REFERENCES

• 1: M. Bacharach. Biproportional Matrices and Input-Output Change. Cambridge University Press, 1970.
• 2: M. L. Balinski , G. Demange, Algorithms for proportional matrices in reals and integers, Mathematical Programming: Series A and B, v.45 n.2, p.193-210, Oct. 1989 [doi>10.1007/BF01589103]
• 3: Michel Balinski and Svetlozar T. Rachev. Rounding proportions: methods of rounding. Math. Scientist, 22:1--26, 1997.
• 4: William J. Cook , William H. Cunningham , William R. Pulleyblank , Alexander Schrijver, Combinatorial optimization, John Wiley & Sons, Inc., New York, NY, 1998
• 5: Martin Fürer. Quadratic convergence for scaling of matrices. In Lars Arge, Giuseppe F. Italiano, and Robert Sedgewick, editors, Proc. ALENEX/ANALC 2004, 6th Workshop on Algorithm Engineering and Experiments and 1st Workshop on Analytic Algorithmics and Combinatorics, New Orleans, pages 216--223. SIAM, January 2004.
• 6: Norbert Gaffke and Friedrich Pukelsheim. Divisor methods for proportional representation systems: an optimization approach to vector and matrix problems. Technical Report (Preprint) 06--18, Universität Magdeburg, Fakultät für Mathematik, March 2006. http://www.math.uni-magdeburg.de/preprints/shadows/06-18report.html.
• 7: Dorit Hochbaum. Complexity and algorithms for convex network optimization and other nonlinear problems. 4OR, 3(3):171--216, 2005.
• 8: Bahman Kalantari and Leonid Khachiyan. On the complexity of nonnegative-matrix scaling. Linear Algebra Appl., 240:87--104, 1996.
• 9: Alexander V. Karzanov , S. Thomas McCormick, Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications, SIAM Journal on Computing, v.26 n.4, p.1245-1275, Aug. 1997 [doi>10.1137/S0097539794263695]
• 10: Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica, 20(4):545--568, 2000.
• 11: U. Rothblum and H. Schneider. Scaling of matrices which have prespecified row sums and column sums via optimization. Linear Algebra Appl., 114--115:737--764, 1989.
• 12: Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist., 35:876--879, 1964.
• 13: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 14: George W. Soules. The rate of convergence of Sinkhorn balancing. Linear Algebra Appl., 150:3--40, 1991.