Randomized algorithms for Tikhonov regularization in linear least squares

Maike Meier, Yuji Nakatsukasa

We describe two algorithms to efficiently solve regularized linear least squares systems based on sketching. The algorithms compute preconditioners for $\min \|Ax-b\|^2_2 + λ\|x\|^…