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

Bahman Kalantari, I. Lari, F. Ricca, B. Simeone

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r ∈ Rn and c ∈ Rm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij /a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the ε-approximate (r,c)-scaling problem, polynomial in n,m,h, /ε, and ln {V} v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln (1&\epsi; , not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an approximate solution within complexity polynomial in n, m, h, In V/ν and 1/ε.

Original languageEnglish (US)
Pages (from-to)371-401
Number of pages31
JournalMathematical Programming
Volume112
Issue number2
DOIs
StatePublished - Apr 1 2008

Fingerprint

Entropy
Scaling
Nonnegative Matrices
Polynomials
Square matrix
Minimization Problem
Upper and Lower Bounds
Norm
Polynomial Complexity
Positive Matrices
Entropy Function
Polynomial
Diagonal matrix
Polynomial-time Algorithm
Theoretical Analysis
Approximate Solution
Interval
Alternatives
Zero
Term

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Cite this

@article{f265a348547d4e4186d057168ed00f9b,
title = "On the complexity of general matrix scaling and entropy minimization via the RAS algorithm",
abstract = "Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r ∈ Rn and c ∈ Rm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij /a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the ε-approximate (r,c)-scaling problem, polynomial in n,m,h, /ε, and ln {V} v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln (1&\epsi; , not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an approximate solution within complexity polynomial in n, m, h, In V/ν and 1/ε.",
author = "Bahman Kalantari and I. Lari and F. Ricca and B. Simeone",
year = "2008",
month = "4",
day = "1",
doi = "10.1007/s10107-006-0021-4",
language = "English (US)",
volume = "112",
pages = "371--401",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2",

}

On the complexity of general matrix scaling and entropy minimization via the RAS algorithm. / Kalantari, Bahman; Lari, I.; Ricca, F.; Simeone, B.

In: Mathematical Programming, Vol. 112, No. 2, 01.04.2008, p. 371-401.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Kalantari, Bahman

AU - Lari, I.

AU - Ricca, F.

AU - Simeone, B.

PY - 2008/4/1

Y1 - 2008/4/1

N2 - Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r ∈ Rn and c ∈ Rm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij /a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the ε-approximate (r,c)-scaling problem, polynomial in n,m,h, /ε, and ln {V} v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln (1&\epsi; , not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an approximate solution within complexity polynomial in n, m, h, In V/ν and 1/ε.

AB - Given an n × m nonnegative matrix A = (a ij ) and positive integral vectors r ∈ Rn and c ∈ Rm having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n × m matrix z = (z ij ) having the same zero pattern as A, the sum of whose entries is a given number h, its row and column sums are within given integral vectors of lower and upper bounds, and such that the entropy function consisting of the sum of the terms z ij ln (z ij /a ij ) is minimized. When the lower and upper bounds coincide, matrix scaling and entropy minimization are closely related. In this paper we present several complexity bounds for the ε-approximate (r,c)-scaling problem, polynomial in n,m,h, /ε, and ln {V} v, where V and v are the largest and the smallest positive entries of A, respectively. These bounds, although not polynomial in ln (1&\epsi; , not only provide alternative complexities for the polynomial time algorithms, but could result in better overall complexities. In particular, our theoretical analysis supports the practicality of the well-known RAS algorithm. In our analysis we obtain bounds on the norm of scaling vectors which will be used in deriving not only some of the above complexities, but also a complexity for square nonnegative matrices having positive permanent. In particular, our results extend, nontrivially, many bounds for the doubly stochastic scaling of square nonnegative matrices previously given by Kalantari and Khachiyan to the case of general (r,c)-scaling. Finally, we study a more general entropy minimization problem where row and column sums are constrained to lie in prescribed intervals, and the sum of all entries is also prescribed. Balinski and Demange described an RAS type algorithm for its continuous version, but did not analyze its complexity. We show that this algorithm produces an approximate solution within complexity polynomial in n, m, h, In V/ν and 1/ε.

UR - http://www.scopus.com/inward/record.url?scp=36749081649&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36749081649&partnerID=8YFLogxK

U2 - 10.1007/s10107-006-0021-4

DO - 10.1007/s10107-006-0021-4

M3 - Article

VL - 112

SP - 371

EP - 401

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -