Regularization of linear least squares problems is necessary in a variety of contexts. However, the optimal regularization parameter is usually unknown a priori and is often to be determined in an ad hoc manner, which may involve solving the problem for multiple regularization parameters. In this talk, we will discuss three randomized algorithms, building on the sketch-and-precondition framework in randomized numerical linear algebra (RNLA), to efficiently solve this set of problems. In particular, we consider preconditioners for a set of Tikhonov regularization problems to be solved iteratively. The first algorithm is a Cholesky-based algorithm employing a single sketch for multiple parameters; the second algorithm is SVD-based and improves the computational complexity by requiring a single decomposition of the sketch for multiple parameters. Finally, we introduce an algorithm capable of exploiting low-rank structure (specifically, low statistical dimension), requiring a single sketch and a single decomposition to compute multiple preconditioners with low-rank structure. This algorithm avoids the Gram matrix, resulting in improved stability as compared to related work.
