@inproceedings{W-Efficient-Algorithms-For-Tensor-Scaling-Quantum-Marginals-And-Moment-Polytopes,
Title = {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},
Booktitle = {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.},
Url = {http://arxiv.org/abs/1804.04739},
Url2 = {http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f883.pdf}
}