  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.
  As a consequence, we solve the equivalence problem for the left-right group
action underlying the operator scaling problem. This yields a deterministic
polynomial-time algorithm for a new class of Polynomial Identity Testing (PIT)
problems, which was the original motivation for studying operator scaling.
