TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Page Content

to Navigation


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: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.


Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
Citation key W-Efficient-Algorithms-For-Tensor-Scaling-Quantum-Marginals-And-Moment-Polytopes
Author Peter Bürgisser and Cole Franks and Ankit Garg and Rafael Oliveira and Michael Walter and Avi Wigderson
Title of Book Proceedings 59th Annual IEEE Symposium on Foundations of Computer Science
Pages 883-897
Year 2018
DOI 10.1109/FOCS.2018.00088
Month 04
Note Accepted for FOCS 2018
Abstract We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensortrain decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of numerical methods for classical problems in invariant theory that are significantly faster than symbolic methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomialtime convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe