direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Leitung

Prof. Dr. Peter Bürgisser

Lupe

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

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

Kontakt

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

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Forschungssemester (siehe unten).
Während der vorlesungsfreien Zeit: Forschungssemester.

Forschungsfreisemester

Im WS 2018/19 hat Prof. Bürgisser ein Forschungsfreisemester und ist deshalb nur unregelmäßig an der TU anzutreffen. Die Studierenden, welche nicht bereits eine Abschlussarbeit bei Prof. Bürgisser schreiben, werden gebeten, Ihre Anfrage an Beate Nießen zu richten.

Publikationen

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 and Ankit Garg and Rafael Oliveira and Michael Walter and Avi Wigderson
Buchtitel 9th Innovations in Theoretical Computer Science
Seiten 24:1–24:20
Jahr 2017
DOI 10.4230/LIPIcs.ITCS.2018.24
Jahrgang 94
Monat 11
Herausgeber Anna R. Karlin
Serie Leibniz International Proceedings in Informatics (LIPIcs)
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 Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe