Adaptive LSQR Preconditioning from One Small Sketch
This work addresses the computational bottleneck of constructing costly preconditioners for large-scale linear systems, offering a robust and efficient solution for practitioners dealing with sparse or low-rank matrices, though it appears incremental as it builds on existing randomized preconditioning methods.
The authors tackled the problem of efficiently solving large-scale linear least-squares problems by proposing APLICUR, an adaptive preconditioning framework that uses a single small sketch to incrementally refine a preconditioner during iteration, achieving competitive or improved time-to-accuracy performance with low setup costs across various test problems.
We propose APLICUR, an adaptive preconditioning framework for large-scale linear least-squares (LLS) problems. Using a single small sketch computed once at initialization, APLICUR incrementally refines a CUR-based preconditioner throughout the Krylov solve, interleaving preconditioning with iteration. This enables early convergence without the need to construct a costly high-quality preconditioner upfront. With a modest sketch dimension (typically 5 - 250), largely independent of both the problem size and numerical rank, APLICUR achieves convergence guarantees that are likewise independent of the sketch size. The method is applicable to general matrices without structural assumptions (e.g. need not be heavily overdetermined) and is well suited to large, sparse, or numerically low-rank problems. We conduct extensive numerical studies to examine the behavior of the proposed framework and guide the effective algorithmic design choices. Across a range of test problems, \mainalg{} achieves competitive or improved time-to-accuracy performance compared with established randomized preconditioners, including Blendenpik and Nyström PCG, while maintaining low setup cost and robustness across problem regimes.