Adaptive preconditioning for linear least-squares problems via iterative CUR
Abstract
Large-scale linear least-squares problems arise in many areas of computational science and data analysis, where efficiency and scalability are crucial. In this talk, we introduce a randomized preconditioning framework for iterative solvers based on low-rank approximations of small sketches of the original problem. The key idea is to iteratively construct low-rank preconditioners that reshape the singular value distribution in a favorable way. By tightly coupling the preconditioning and Krylov solving phases within an iterative CUR decomposition -- a low-rank approximation built from selected of columns and rows of the original matrix -- the proposed algorithm achieves faster and earlier convergence than existing methods. The algorithm performs particularly well on problems that are large in both dimensions, as well as on sparse and ill-conditioned systems. This is a joint work with Coralia Cartis and Yuji Nakatsukasa.