Strongly Polynomial Frame Scaling to High Precision

The frame scaling problem is: given vectors U := u1, ..., un ⊆ R d , marginals c ∈ R n ++ , and precision ε > 0, find left and right scalings L ∈ R d×d , r ∈ R n ++ such that (v1, . . . , vn) := (Lu1r1, ..., Lunrn) simultaneously satisfies n i=1 viv T i = I d and ∥vj∥ 2 2 = cj, ∀j ∈ [n], up to error ε. This problem has appeared in a variety of fields throughout linear algebra and computer science. In this work, we give a strongly polynomial algorithm for frame scaling with log(1/ε) convergence. This answers a question of Diakonikolas, Tzamos and Kane (STOC 2023), who gave the first strongly polynomial randomized algorithm with poly(1/ε) convergence for Forster transformation, the special case c = d n 1n. Our algorithm is deterministic, applies for general marginals c ∈ R n ++ , and requires O(n 3 log(n/ε)) iterations as compared to the O(n 5 d 11 /ε 5 ) iterations of DTK. By lifting the framework of Linial, Samorodnitsky and Wigderson (Combinatorica 2000) for matrix scaling to the frame setting, we are able to simplify both the algorithm and analysis. Our main technical contribution is to generalize the potential analysis of LSW to the frame setting and compute an update step in strongly polynomial time that achieves geometric progress in each iteration. In fact, we can adapt our results to give an improved analysis of strongly polynomial matrix scaling, reducing the O(n 5 log(n/ε)) iteration bound of LSW to O(n 3 log(n/ε)). Additionally, we give a bound on the size of approximate scaling solutions, which involves condition measure χ studied in the linear programming literature, and may be of independent interest.

We say (U, c) is feasible if this is the case, and otherwise we say it is infeasible.

• The full version of the paper can be accessed at https://arxiv.org/abs/XXX.XXXX (will have link in a few days!) † Centrum Wiskunde and Informatica. ‡ Centrum Wiskunde and Informatica.