Computer Science/Discrete Mathematics Seminar II

Topic: Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing (Continued)

Speaker: Yuanzhi Li

Affiliation: Princeton University

Date & Time: Tuesday March 20th, 2018, 10:30am - 7:00pm

Location: Simonyi Hall 101

Video: https://video.ias.edu/csdm/2018/0320-YuanzhiLi

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, “commutative” metric (for which the above problem is not convex).   As a consequence, we solve the equivalence problem for the left-right group action underlying the operator scaling problem. We give a deterministic polynomial time algorithm for a new class of Polynomial Identity Testing (PIT) problems, which was the original motivation for studying operator scaling.