Randomized algorithms for Tikhonov regularization in linear least squares

03/14/2022
by   Maike Meier, et al.
0

We describe two algorithms to efficiently solve regularized linear least squares systems based on sketching. The algorithms compute preconditioners for minAx-b^2_2 + λx^2_2, where A∈ℝ^m× n and λ>0 is a regularization parameter, such that LSQR converges in 𝒪(log(1/ϵ)) iterations for ϵ accuracy. We focus on the context where the optimal regularization parameter is unknown, and the system must be solved for a number of parameters λ. Our algorithms are applicable in both the underdetermined m≪ n and the overdetermined m≫ 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 λ. The complexity of solving for N parameters is 𝒪(mnlog(max(m,n)) +N(min(m,n)^3 + mnlog(1/ϵ))). Secondly, we introduce an algorithm that uses a sketch of size 𝒪(sd_λ(A)) for the case where the statistical dimension sd_λ(A)≪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 λ_i in 𝒪(mnlog(max(m,n)) + min(m,n) sd_minλ_i(A)^2 + Nmnlog(1/ϵ)) operations.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset