Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing

Understand

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).
• Our method is general and applicable to other settings.