Generalized scalings satisfying linear equations

AbstractWe unify and generalize a broad class of problems referred in the literature as “scaling problems,” by extending the applicability of a formulation suggested recently by Bapat and Raghavan. Specifically, let a ∈ Rn,b ∈Rm, and C ∈ Rm × n be given, where a is strictly positive. A C-scaling of the vector a is defined to be a vector a'∈Rn with a'i= aiΠmk=1uCkjk for some strictly positive vector u Rm. The problem of finding a C-scaling of the vector a which satisfies the linear system Cx = b will be called a generalized scaling problem. In this paper it is shown that previously studied matrix-scaling problems, (e.g., finding scalings with prespecified row sums and column sums, or finding scalings with row sums equaling the corresponding column sums, or finding scalings of multidimensional matrices with prespecified margins) are special instances of generalized scaling problems. Generalized scaling problems are reduced to convex optimization problems, and the reduction is used to characterize solutions, to develop necessary and sufficient conditions for their existence, to establish uniqueness results and to characterize approximate solutions