TCS+ Talk
Please join us this TCS+ video seminar. Coffee and pastries will be served.
Sinkhorn in 1964 studied the problem of matrix scaling, given a non-negative matrix A, find diagonal matrices with positive entries (if exist) D_1 and D_2 s.t. D_1 A D_2 is doubly stochastic. He proved that a natural iterative algorithm finds this scaling if entries of A are strictly positive. Matrix scaling has since found applications in various fields such as statistics, numerical analysis, operations research, combinatorial geometry and approximating the permanent. Gurvits in 2004 found a striking generalization of matrix scaling, called operator scaling, where one wants to "scale" completely positive operators to make them "doubly stochastic". Gurvits proved that a natural iterative algorithm converges, and, in fact, in polynomial number of iterations in some special cases. We analyze Gurvits' algorithm completely and prove that it always converges in polynomial number of iterations. Our analysis is simple, providing explicit bounds on the "capacity" measure of completely positive operators introducted by Gurvits. Using this we obtain the first deterministic polynomial time algorithm for computing rank of a symbolic matrix in non-commuting variables. Previous algorithms required exponential time (with or without randomness). This problem (of computing rank of a symbolic matrix) has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. Besides non-commutative algebra, it also has various connections to computational complexity and de-randomizatio