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

arXiv:2405.05865v1 Announce Type: cross
Abstract: 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 …

abstract approximation arxiv class construct cs.ds cs.lg cs.na faster form iterative linear low math.na math.oc matrix norm random systems type via