Algorithms For Large Scale Discrete Linear Ill-Posed Problems With General-form Regularization

First,we propose new randomization based algorithms for large scale linear discrete ill-posed problems with general-form regularization:min?Lx?subject to x?={x|?Ax-b????e?},?2?where L is a regularization matrix,e is the noise,and?>1 slightly.Our algorithms are in-spired by the modified truncated singular value decomposition?MTSVD?method,which suits only for small to medium scale problems,and randomized SVD?RSVD?algorithms that generate good low rank approximations to A.We use rank-k truncated randomized SVD?TRSVD?approximations to A by truncating the rank-?k+q?RSVD approximations to A,where q is an oversampling parameter.The resulting algorithms are called modified TRSVD?MTRSVD?methods.At every step,we use the LSQR algorithm to solve the resulting inner least squares problem,which is proved to become better conditioned as k increases so that LSQR converges faster.We present sharp bounds for the approxima-tion accuracy of the RSVDs and TRSVDs for severely,moderately and mildly ill-posed problems,and substantially improve a known basic bound for TRSVD approximations.We prove how to choose the stopping tolerance for LSQR in order to guarantee that the computed and exact best regularized solutions have the same accuracy.Numerical exper-iments illustrate that the best regularized solutions by MTRSVD are as accurate as the ones by the truncated generalized singular value decomposition?TGSVD?algorithm,and at least as accurate as those by some existing truncated randomized generalized singular value decomposition?TRGSVD?algorithms.We further consider iterative regularization algorithms for large scale discrete ill-posed problems with general-form regularization,since MTRSVD algorithms are fast and efficient when the singular values of the problem decay fast but they are not generally efficient when the singular values of the problems decay slowly.Based on the joint bidi-agonalization process of a large matrix pair{A,L},we propose and develop an iterative regularization algorithm for the large scale linear discrete ill-posed problem in general-form regularization.Our algorithm JBDQR has been shown to have the desired semi-convergence property that any single regularization method must possess and is different from the hybrid one proposed by Kilmer et al.,which is based on the same process but solves the general-form Tikhonov regularization problem:min_x^{??Ax-b?²+?²?Lx?^2}?.We prove that the iterates take the form of attractive filtered generalized singular value decomposition?GSVD?expansions,which get insight into the regularizing effects of the proposed method.We use the L-curve criterion or the discrepancy principle to determine the optimal regularization parameter k^*.JBDQR is simple and effective,and numerical experiments illustrate that it often computes more accurate regularized solutions than the hybrid one.To improve the performance of JBDQR and meanwhile maintain the solution accu-racy,we present a new Krylov subspace projected based algorithm for large scale discrete ill-posed problems with regularization in general form.We first use a subspace project-ed method,where the matrix A is projected onto a lower-dimensional Krylov subspace.Then we use the LSQR algorithm to solve the resulting inner least squares problems.The projection is typically implemented via Lanczos bidiagonalization process applied to A,with starting vector b,and generates a rank-k approximation to A where P_k+1+1 and Q_kare orthonormal columns and B_k is a lower bidiagonalization.At every step,we use the LSQR algorithm to solve the resulting inner least squares problem,which is proved to become better conditioned as k increases so that LSQR converges faster.The result-ing algorithm we called projected LSQR?pLSQR?.We prove how to choose the stopping tolerance for the LSQR algorithm to solve the resulting inner least squares problems in order to guarantee that the computed regularized solutions and exact best regularized so-lutions have the same accuracy.Numerical experiments illustrate that the best regularized solutions by our algorithm are as accurate as JBDQR,and our algorithm uses much less time than JBDQR does for the same test problems.