Strongly polynomial frame scaling to high precision

The frame scaling problem is: given vectors U := {u1, ..., un} ⊆ Rd, marginals c ∈ Rn++, and precision ε > 0, find left and right scalings L ∈ Rd×d, r ∈ Rn++ such that (v1, ..., vn):= (Lu1r1, ..., Lunrn) simultaneously satisfies (Equation presented) and ∥vj∥22 = 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 = nd 1n. Our algorithm is deterministic, applies for general marginals c ∈ Rn++, and requires O(n3 log(n/ε)) iterations as compared to the O(n5d11/ε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(n5 log(n/ε)) iteration bound of LSW to O(n3 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.

• View at Publisher

Free Full Text ( Final Version , 666kb )