Randomized algorithms for Tikhonov regularization in linear least squares

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 + \lambda \|x\|^2_2$, where $A\in\mathbb{R}^{m\times n}$ and $\lambda>0$ is a regularization parameter, such that LSQR converges in $\mathcal{O}(\log(1/\epsilon))$ iterations for $\epsilon$ accuracy. We focus on the context where the optimal regularization parameter is unknown, and the system must be solved for a number of parameters $\lambda$. Our algorithms are applicable in both the underdetermined $m\ll n$ and the overdetermined $m\gg n$ setting. Firstly, we propose a Cholesky-based sketch-to-precondition algorithm that uses a `partly exact' sketch, and only requires one sketch for a set of $N$ regularization parameters $\lambda$. The complexity of solving for $N$ parameters is $\mathcal{O}(mn\log(\max(m,n)) +N(\min(m,n)^3 + mn\log(1/\epsilon)))$. Secondly, we introduce an algorithm that uses a sketch of size $\mathcal{O}(\text{sd}_{\lambda}(A))$ for the case where the statistical dimension $\text{sd}_{\lambda}(A)\ll\min(m,n)$. The scheme we propose does not require the computation of the Gram matrix, resulting in a more stable scheme than existing algorithms in this context. We can solve for $N$ values of $\lambda_i$ in $\mathcal{O}(mn\log(\max(m,n)) + \min(m,n)\,\text{sd}_{\min\lambda_i}(A)^2 + Nmn\log(1/\epsilon))$ operations.