Matrix Balancing in L_p norms: A New Analysis of Osborne’s Iteration (Yuval Rabani)
Abstract: We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norms. The original algorithm was proposed for balancing rows and columns in the L2 norm, but variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Recently, Schulman and Sinclair (2015), in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne’s algorithm in the L-infinity norm. We study matrix balancing in the L_1 and other L_p norms. We show a few results, resolving in particular a main open problem mentioned by Schulman and Sinclair. The talk is based on two joint papers with Rafail Ostrovsky and Arman Yousefi
