On the complexity of general matrix scaling and entropy minimization via the RAS algorithm

DOI10.1007/s10107-006-0021-4zbMath1191.15005OpenAlexW2077575254MaRDI QIDQ2465654

Isabella Lari, Federica Ricca, Bahman Kalantari, Bruno Simeone

Publication date: 7 January 2008

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

Full work available at URL: https://doi.org/10.1007/s10107-006-0021-4

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Determinants, permanents, traces, other special matrix functions (15A15) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Numerical computation of matrix norms, conditioning, scaling (65F35) Matrices of integers (15B36)

Related Items

Network flow methods for electoral systems, Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment, Unnamed Item, An entropy optimizing RAS-equivalent algorithm for iterative matrix balancing, Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm, Apportionment with parity constraints, Matrix Balancing Based Interior Point Methods for Point Set Matching Problems, Balancing of agricultural census data by using discrete optimization, Divisor methods for proportional representation systems: an optimization approach to vector and matrix apportionment problems, On the complexity of general matrix scaling and entropy minimization via the RAS algorithm, Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling, Biproportional scaling of matrices and the iterative proportional fitting procedure, Robust learning in social networks via matrix scaling, Matrix scaling and explicit doubly stochastic limits, Certificates of optimality for minimum norm biproportional apportionments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Matching theory
• Matrix scaling, entropy minimization, and conjugate duality. I: Existence conditions
• On the scaling of multidimensional matrices
• Scalings of matrices which have prespecified row sums and column sums via optimization
• Generalized scalings satisfying linear equations
• On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms
• On linear programming and matrix scaling over the algebraic numbers
• Semidefinite programming and matrix scaling over the semidefinite cone.
• Algorithms for proportional matrices in reals and integers
• A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices
• On the complexity of nonnegative-matrix scaling
• On complexity of matrix scaling
• On the complexity of general matrix scaling and entropy minimization via the RAS algorithm
• Scaling of matrices to achieve specified row and column sums
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• An Axiomatic Approach to Proportionality Between Matrices
• Extensions of Jentzsch's Theorem
• A Comparative Study of Algorithms for Matrix Balancing
• On the Matrix Equation X′X = A
• Diagonal Matrix Scaling and Linear Programming
• A Quadratically Convergent Polynomial Algorithm for Solving Entropy Optimization Problems
• On the Complexity of Matrix Balancing
• Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Reduction of a Matrix with Positive Elements to a Doubly Stochastic Matrix
• Convex Sets of Non-Negative Matrices
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents