Theory Seminar - Alternate Minimization Algorithms for (matrix, operator, tensor) Scaling Problems, Their Analysis and Applications

Title: Alternate Minimization Algorithms for (matrix, operator, tensor) Scaling Problems, Their Analysis and Applications

Abstract: 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 functional analysis, 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 talk, we will describe in detail the scaling problems mentioned above, showing how alternate minimization algorithms naturally arise in this setting, and we shall present a unified (3-step) framework to rigorously analyse such algorithms. 

This framework is based on a non-commutative duality arising from invariant theory, which we will carefully (and gently) define. 

No prior background on Invariant Theory will be needed.

We will also mention recent applications of scaling problems to diverse subfields of mathematics and computer science, and mention some of the myriad future directions which are still open. 

Talk based on joint works with Peter Bürgisser, Ankit Garg, Leonid Gurvits, Michael Walter and Avi Wigderson.