Randomized algorithms for Tikhonov regularization in linear least squares

MaRDI QIDQ6393664zbMATH OpenFDO

Authors Maike Meier, Yuji Nakatsukasa

Publication date 14 March 2022

Mathematics Subject Classification ID

Preconditioners for iterative methods (65F08) Ill-posedness and regularization problems in numerical linear algebra (65F22) Randomized algorithms (68W20)

Abstract: 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 $Ainmathbb{R}^{mimesn}$ and $lambda>0$ is a regularization parameter, such that LSQR converges in $mathcalO(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 $mlln$ and the overdetermined $mggn$ 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 $mathcalO(mnlog(max(m,n))+N(min(m,n{)}^3+mnlog(1/epsilon)))$. Secondly, we introduce an algorithm that uses a sketch of size $mathcalO(ext{sd}_{lambda}(A))$ for the case where the statistical dimension $ext{sd}_{lambda}(A)llmin(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 $lambd{a}_i$ in $mathcalO(mnlog(max(m,n))+min(m,n),ext{sd}_{minlambd{a}_i}(A{)}^2+Nmnlog(1/epsilon))$ operations.

This page was built for publication: Randomized algorithms for Tikhonov regularization in linear least squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6393664)