direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Prof. Dr. Peter Bürgisser


Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Raum MA 317 (3. OG)
Institut für Mathematik


Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771


+49 (0)30 314 - 75902
+49 (0)30 314 - 25839

Während der Vorlesungszeit: Mittwochs 1200-1300.
Während der vorlesungsfreien Zeit: Nach Vereinbarung.


Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
Zitatschlüssel W-Alternating-Minimization-Scaling-Algorithms-And-The-Null-Cone-Problem-From-Invariant-Theory
Autor Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, Avi Wigderson
Jahr 2017
Monat 11
Zusammenfassung 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).
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe