A Joint Bidiagonalization Based Algorithm for Large Scale Linear Discrete Ill-posed Problems in General-Form Regularization

Abstract

Based on the joint bidiagonalization process of a large matrix pair $\{A,L\}$, we propose and develop an iterative regularization algorithm for the large scale linear discrete ill-posed problems in general-form regularization: $\min\|Lx\| \ \mbox{\rm subject to} \ x\in\mathcal{S} = \{x|\ \|Ax-b\|\leq τ\|e\|\}$ with a Gaussian white noise $e$ and $\tau >1$ slightly, where $L$ is a regularization matrix. Our algorithm is different from the hybrid one proposed by Kilmer {\em et al.}, which is based on the same process but solves the general-form Tikhonov regularization problem: ${\min }_x\left\{\Vert Ax-b{\Vert }^2+{\lambda }^2\Vert Lx{\Vert }^2\right\}$. We prove that the iterates take the form of attractive filtered generalized singular value decomposition (GSVD) expansions, where the filters are given explicitly. This result and the analysis on it show that the method must have the desired semi-convergence property and get insight into the regularizing effects of the method. We use the L-curve criterion or the discrepancy principle to determine $k^{\ast }$. The algorithm is simple and effective, and numerical experiments illustrate that it often computes more accurate regularized solutions than the hybrid one.

25 pages, 4 figures

References in corpus (4)

• Approximation Accuracy of the Krylov Subspaces for Linear Discrete Ill-Posed Problems
• The Low Rank Approximations and Ritz Values in LSQR For Linear Discrete Ill-Posed Problems
• Regularization Properties of the Krylov Iterative Solvers CGME and LSMR For Linear Discrete Ill-Posed Problems with an Application to Truncated Randomized SVDs
• The Krylov Subspaces, Low Rank Approximations and Ritz Values of LSQR for Linear Discrete Ill-Posed Problems: the Multiple Singular Value Case

Cited by in corpus (7)

• On choices of formulations of computing the generalized singular value decomposition of a large matrix pair
• The joint bidiagonalization process with partial reorthogonalization
• The joint bidiagonalization method for large GSVD computations in finite precision
• A cross-product free Jacobi-Davidson type method for computing a partial generalized singular value decomposition (GSVD) of a large matrix pair
• Two harmonic Jacobi--Davidson methods for computing a partial generalized singular value decomposition of a large matrix pair
• A CJ-FEAST GSVDsolver for computing a partial GSVD of a large matrix pair with the generalized singular values in a given interval
• On inner iterations of the joint bidiagonalization based algorithms for solving large scale ill-posed problems