Stabilized Krylov Subspace Recurrences via Randomized Sketching

Recurrences building orthonormal bases for polynomial Krylov spaces have been classically used for approximation purposes in various numerical linear algebra contexts. Variants aiming to limit memory and computational costs by using truncated recurrences often have convergence constraints. Recently, randomized linear algebra strategies have been devised that drastically improve the performance of these variants, while keeping the costs low. We provide a unifying framework for analyzing a large class of Krylov subspace methods, including randomization-enhanced strategies, based on Krylov decompositions. This framework allows us to identify the key quantities—the canonical angles among the Krylov subspace basis vectors—for assessing the effectiveness of the randomized strategy. Moreover, it also allows us to analyze the spectral properties of the projected problem. Our results are illustrated with experiments using the nonsymmetric Lanczos iteration, which is an inherently three-term recurrence, so that no truncation needs to be performed. Hence, randomized procedures applied to the Lanczos method may be viewed as a way to stabilize the approximation.