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

arXiv: https://arxiv.org/abs/1804.01076 · HTML: https://mlsanity.com/paper/1804.01076/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2018.

## Built on by (most cited first, 8 of 8)

- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory](https://mlsanity.com/paper/2109.01080/) (2021)
- [No-go Theorem for Acceleration in the Hyperbolic Plane](https://mlsanity.com/paper/2101.05657/) (2021)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties](https://mlsanity.com/paper/2305.16186/) (2023)
- [On a class of geodesically convex optimization problems solved via Euclidean MM methods](https://mlsanity.com/paper/2206.11426/) (2022)
- [Extragradient Type Methods for Riemannian Variational Inequality Problems](https://mlsanity.com/paper/2309.14155/) (2023)

## Abstract (arXiv)

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.