On the complexity of nonnegative-matrix scaling. (English) Zbl 0849.15003
The authors derive an upper bound on the norms of the scaling factors of an \(n \times n\) nonnegative double stochastic (scalable) matrix. A polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy is also given.
Reviewer: P.Narain (Bombay)
MSC:
| 15A12 | Conditioning of matrices |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65Y20 | Complexity and performance of numerical algorithms |
| 15B51 | Stochastic matrices |
References:
| [1] | Bacharach, M., Biproportional Matrices and Input-Output Change (1970), Cambridge U.P · Zbl 0195.49705 |
| [2] | Bachem, A.; Korte, B., On the RAS algorithm, Computing, 23, 189-198 (1979) · Zbl 0403.90074 |
| [3] | Birkoff, G., Extensions of Jentzsch’s theorem, Trans. Amer. Math Soc., 85, 219-227 (1957) · Zbl 0079.13502 |
| [4] | Bregman, L. M., Proof of the convergence of Sheleikhovskii’s method for a problem with transportation constraints, USSR Comput. Math. and Math. Phys., 7, 191-204 (1967) |
| [5] | Brualdi, R. A.; Parter, S. V.; Schneider, H., The diagonal equivalence of a nonnegative matrix to a stochastic matrix, J. Math. Ann. Appl., 16, 31-50 (1966) · Zbl 0231.15017 |
| [6] | Brualdi, R. A., Convex sets of nonnegative matrices, Canad. J. Math., 20, 144-157 (1968) · Zbl 0155.06501 |
| [7] | Djoković, D. Z., Note on nonnegative matrices, (Proc. Amer. Math. Soc., 25 (1970)), 80-82 · Zbl 0198.35102 |
| [8] | Franklin, J.; Lorenz, J., On the scaling of multidimensional matrices, Linear Algebra Appl., 114/115, 717-735 (1989) · Zbl 0674.15001 |
| [9] | Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum-flow problem, J. Assoc. Comput. Mach., 35, 921-940 (1988) · Zbl 0661.90031 |
| [10] | Kalantari, B., A Theorem of the Alternative for Multihomogeneous Functions and Its Relationship to Diagonal Scaling of Matrices, (Technical Report LCSR-TR-202 (1993), Dept. of Computer Science, Rutgers Univ: Dept. of Computer Science, Rutgers Univ New Brunswick, N.J), Linear Algebra Appl. (in press) · Zbl 0846.15003 |
| [11] | Kalantari, B.; Khachiyan, L., On the rate of convergence of deterministic and randomized RAS matrix scaling method, Oper. Res. Lett., 14, 237-244 (1993) · Zbl 0795.65022 |
| [12] | Khachiyan, L.; Kalantari, B., Diagonal matrix scaling and linear programming, SIAM J. Optim., 2, 668-672 (1992) · Zbl 0770.90043 |
| [13] | London, D., On matrices with a doubly stochastic pattern, J. Math. Anal. Appl., 34, 648-652 (1971) · Zbl 0224.15022 |
| [14] | Marcus, M.; Newman, M., The permanent of a symmetric matrix, Notices Amer. Math. Soc., 8, 595 (1961) |
| [15] | Marshall, A. W.; Olkin, I., Scaling of matrices to achieve specified row and column sums, Numer. Math., 12, 83-90 (1968) · Zbl 0165.17401 |
| [16] | Maxfield, J.; Minc, H., A doubly stochastic matrix equivalent to a given matrix, Notices Amer. Math. Soc., 9, 309 (1962) |
| [17] | Menon, M. V., Reduction of matrix with positive elements to a doubly stochastic matrix, (Proc. Amer. Math. Soc., 18 (1967)), 244-247 · Zbl 0153.05301 |
| [18] | Minc, H., Nonnegative Matrices (1988), Wiley: Wiley New York · Zbl 0638.15008 |
| [19] | Mirsky, L.; Perfect, H., The distribution of positive elements in doubly stochastic matrices, J. London Math. Soc., 49, 689-698 (1965) · Zbl 0166.03501 |
| [20] | Nesterov, Ju. E.; Nemirovsky, A. S., Self-Concordant Functions and Polynomial-Time Methods in Convex Programming (1989), USSR Acad. of Sciences, Central Economics and Mathematics Inst |
| [21] | Rothblum, U. G.; Schneider, H., Scaling of matrices which have prescribed row sums and column sums via optimization, Linear Algebra Appl., 114/115, 737-764 (1989) · Zbl 0678.15004 |
| [22] | Schneider, M. H.; Zenios, S. A., A comparative study of algorithms for matrix balancing, Oper. Res., 38, 439-455 (1989) · Zbl 0703.90094 |
| [23] | Schneider, M. H., Matrix scaling, entropy minimization, and conjugate duality. I. Positivity conditions, Linear Algebra Appl., 114/115, 785-813 (1989) · Zbl 0673.15003 |
| [24] | Sinkhorn, R., A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Statist., 35, 876-879 (1964) · Zbl 0134.25302 |
| [25] | Sinkhorn, R.; Knopp, P., Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math., 21, 343-348 (1967) · Zbl 0152.01403 |
| [26] | Y. Ye and F. Potra, An Interior-Point Algorithm for Solving Entropy Optimization Problems with Globally Linear and Locally Quadratic Convergence Rate, Working Paper Ser. 90-22.; Y. Ye and F. Potra, An Interior-Point Algorithm for Solving Entropy Optimization Problems with Globally Linear and Locally Quadratic Convergence Rate, Working Paper Ser. 90-22. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
