TR18-151 Authors: Ankit Garg, Rafael Oliveira

Publication: 29th August 2018 14:23

Downloads: 705

Keywords:

Scaling problems have a rich and diverse history, and thereby have found numerous

applications in several fields of science and engineering. For instance, the matrix scaling problem

has had applications ranging from theoretical computer science to telephone forecasting,

economics, statistics, optimization, among many other fields. Recently, a generalization of matrix

scaling known as operator scaling has found applications in non-commutative algebra, invariant

theory, combinatorics and algebraic complexity; and a further generalization (tensor scaling)

has found more applications in quantum information theory, geometric complexity theory and

invariant theory.

In this survey, we will describe in detail the scaling problems mentioned above, showing how

alternating minimization algorithms naturally arise in this setting, and we shall present a general

framework to rigorously analyze such algorithms. These simple problems and algorithms are

not just applicable to diverse mathematical and CS areas, but also serve to bring out deep

connections between them. As this framework makes extensive use of concepts from invariant

theory, we also provide a very gentle introduction to basic concepts of invariant theory and how

they are used to analyze alternating minimization algorithms for the scaling problems.

This survey is intended for a general computer science audience, and the only background

required is basic knowledge of calculus and linear algebra, thereby making it accessible to

graduate students and even to advanced undergraduates