Fast and Near-Optimal Diagonal Preconditioning

The convergence rates of iterative methods for solving a linear system A x = b typically depend on the condition number of the matrix A. Preconditioning is a common way of speeding up these methods by reducing that condition number in a computationally inexpensive way. In this paper, we revisit the decades-old problem of how to best improve A's condition number by left or right diagonal rescaling. We make progress on this problem in several directions. First, we provide new bounds for the classic heuristic of scaling A by its diagonal values (a.k.a. Jacobi preconditioning). We prove that this approach reduces A's condition number to within a quadratic factor of the best possible scaling. Second, we give a solver for structured mixed packing and covering semidefinite programs (MPC SDPs) which computes a constant-factor optimal scaling for A in widetildeO(nnz(A) · poly(kappa^star)) time; this matches the cost of solving the linear system after scaling up to a widetildeO(poly(kappa^star)) factor. Third, we demonstrate that a sufficiently general width-independent MPC SDP solver would imply near-optimal runtimes for the scaling problems we consider, and natural variants concerned with measures of average conditioning. Finally, we highlight connections of our preconditioning techniques to semi-random noise models, as well as applications in reducing risk in several statistical regression models.