Title: Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory,
Abstract: Alternating minimization heuristics seek to solve a (difficult) global
optimization task through iteratively solving a sequence of (much easier) local
optimization tasks on different parts (or blocks) of the input parameters.
While popular and widely applicable, very few examples of this heuristic are
rigorously shown to converge to optimality, and even fewer to do so
efficiently.
In this paper we present a general framework which is amenable to rigorous
analysis, and expose its applicability. Its main feature is that the local
optimization domains are each a group of invertible matrices, together
naturally acting on tensors, and the optimization problem is minimizing the
norm of an input tensor under this joint action. The solution of this
optimization problem captures a basic problem in Invariant Theory, called the
null-cone problem.
This algebraic framework turns out to encompass natural computational
problems in combinatorial optimization, algebra, analysis, quantum information
theory, and geometric complexity theory. It includes and extends to high
dimensions the recent advances on (2-dimensional) operator scaling.
Our main result is a fully polynomial time approximation scheme for this
general problem, which may be viewed as a multi-dimensional scaling algorithm.
This directly leads to progress on some of the problems in the areas above, and
a unified view of others. We explain how faster convergence of an algorithm for
the same problem will allow resolving central open problems.
Our main techniques come from Invariant Theory, and include its rich
non-commutative duality theory, and new bounds on the bitsizes of coefficients
of invariant polynomials. They enrich the algorithmic toolbox of this very
computational field of mathematics, and are directly related to some challenges
in geometric complexity theory (GCT).