On the complexity of nonnegative-matrix scaling

Bahman Kalantari, Leonid Khachiyan

Research output: Contribution to journalArticle

32 Citations (Scopus)

Abstract

An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.

Original languageEnglish (US)
Pages (from-to)87-103
Number of pages17
JournalLinear Algebra and Its Applications
Volume240
DOIs
StatePublished - Jan 1 1996

Fingerprint

Scaling Factor
Nonnegative Matrices
Scaling
Polynomial-time Complexity
Positive Matrices
Diagonal matrix
Polynomials
Upper bound
Norm
Computing

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this

@article{169d2b03865247f99522dc8b0d304130,
title = "On the complexity of nonnegative-matrix scaling",
abstract = "An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.",
author = "Bahman Kalantari and Leonid Khachiyan",
year = "1996",
month = "1",
day = "1",
doi = "10.1016/0024-3795(94)00188-X",
language = "English (US)",
volume = "240",
pages = "87--103",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",

}

On the complexity of nonnegative-matrix scaling. / Kalantari, Bahman; Khachiyan, Leonid.

In: Linear Algebra and Its Applications, Vol. 240, 01.01.1996, p. 87-103.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the complexity of nonnegative-matrix scaling

AU - Kalantari, Bahman

AU - Khachiyan, Leonid

PY - 1996/1/1

Y1 - 1996/1/1

N2 - An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.

AB - An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.

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

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

U2 - 10.1016/0024-3795(94)00188-X

DO - 10.1016/0024-3795(94)00188-X

M3 - Article

VL - 240

SP - 87

EP - 103

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -