Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning

We present a new class of preconditioned iterative methods for solving linear systems of the form Ax = b. Our methods are based on constructing a low-rank Nystr\"om approximation to A using sparse random sketching. This approximation is used to construct a preconditioner, which itself is inverted quickly using additional levels of random sketching and preconditioning. We prove that the convergence of our methods depends on a natural average condition number of A, which improves as the rank of the Nystr\"om approximation increases. Concretely, this allows us to obtain faster runtimes for a number of fundamental linear algebraic problems: 1. We show how to solve any n n linear system that is well-conditioned except for k outlying large singular values in O (n^2. 065 + k^) time, improving on a recent result of Derezi\'nski, Yang, STOC 2024 for all k n^0. 78. 2. We give the first O (n² + d_^) time algorithm for solving a regularized linear system (A + I) x = b, where A is positive semidefinite with effective dimension d_. This problem arises in applications like Gaussian process regression. 3. We give faster algorithms for approximating Schatten p-norms and other matrix norms. For example, for the Schatten 1 (nuclear) norm, we give an algorithm that runs in O (n^2. 11) time, improving on an O (n^2. 18) method of Musco et al. , ITCS 2018. Interestingly, previous state-of-the-art algorithms for most of the problems above relied on stochastic iterative methods, like stochastic coordinate and gradient descent. Our work takes a completely different approach, instead leveraging tools from matrix sketching.