Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Joint Bidiagonalization Based Algorithm for Large Scale Linear Discrete Ill-posed Problems in General-Form Regularization
117
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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}} xinmathcal{S} = {x| |Ax-b|leq tau|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_xleft{|Ax-b|^2+lambda^2|Lx|^2right}$. 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^*$. The algorithm is simple and effective, and numerical experiments illustrate that it often computes more accurate regularized solutions than the hybrid one.
rate research
Read More
In this paper, we propose new randomization based algorithms for large scale linear discrete ill-posed problems with general-form regularization: ${min} |Lx|$ subject to ${min} |Ax - b|$, where $L$ is a regularization matrix. Our algorithms are inspired 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 approximation 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 experiments 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.
Many applications in science and engineering require the solution of large linear discrete ill-posed problems that are obtained by the discretization of a Fredholm integral equation of the first kind in several space-dimensions. The matrix that defines these problems is very ill-conditioned and generally numerically singular, and the right-hand side, which represents measured data, typically is contaminated by measurement error. Straightforward solution of these problems generally is not meaningful due to severe error propagation. Tikhonov regularization seeks to alleviate this difficulty by replacing the given linear discrete ill-posed problem by a penalized least-squares problem, whose solution is less sensitive to the error in the right-hand side and to round-off errors introduced during the computations. This paper discusses the construction of penalty terms that are determined by solving a matrix-nearness problem. These penalty terms allow partial transformation to standard form of Tikhonov regularization problems that stem from the discretization of integral equations on a cube in several space-dimensions.
GMRES is one of the most popular iterative methods for the solution of large linear systems of equations that arise from the discretization of linear well-posed problems, such as Dirichlet boundary value problems for elliptic partial differential equations. The method is also applied to iteratively solve linear systems of equations that are obtained by discretizing linear ill-posed problems, such as many inverse problems. However, GMRES does not always perform well when applied to the latter kind of problems. This paper seeks to shed some light on reasons for the poor performance of GMRES in certain situations, and discusses some remedies based on specific kinds of preconditioning. The standard implementation of GMRES is based on the Arnoldi process, which also can be used to define a solution subspace for Tikhonov or TSVD regularization, giving rise to the Arnoldi-Tikhonov and Arnoldi-TSVD methods, respectively. The performance of the GMRES, the Arnoldi-Tikhonov, and the Arnoldi-TSVD methods is discussed. Numerical examples illustrate properties of these methods.
Block coordinate descent (BCD) methods approach optimization problems by performing gradient steps along alternating subgroups of coordinates. This is in contrast to full gradient descent, where a gradient step updates all coordinates simultaneously. BCD has been demonstrated to accelerate the gradient method in many practical large-scale applications. Despite its success no convergence analysis for inverse problems is known so far. In this paper, we investigate the BCD method for solving linear inverse problems. As main theoretical result, we show that for operators having a particular tensor product form, the BCD method combined with an appropriate stopping criterion yields a convergent regularization method. To illustrate the theory, we perform numerical experiments comparing the BCD and the full gradient descent method for a system of integral equations. We also present numerical tests for a non-linear inverse problem not covered by our theory, namely one-step inversion in multi-spectral X-ray tomography.
Ill-posed linear inverse problems appear in many image processing applications, such as deblurring, super-resolution and compressed sensing. Many restoration strategies involve minimizing a cost function, which is composed of fidelity and prior terms, balanced by a regularization parameter. While a vast amount of research has been focused on different prior models, the fidelity term is almost always chosen to be the least squares (LS) objective, that encourages fitting the linearly transformed optimization variable to the observations. In this paper, we examine a different fidelity term, which has been implicitly used by the recently proposed iterative denoising and backward projections (IDBP) framework. This term encourages agreement between the projection of the optimization variable onto the row space of the linear operator and the pseudo-inverse of the linear operator (back-projection) applied on the observations. We analytically examine the difference between the two fidelity terms for Tikhonov regularization and identify cases (such as a badly conditioned linear operator) where the new term has an advantage over the standard LS one. Moreover, we demonstrate empirically that the behavior of the two induced cost functions for sophisticated convex and non-convex priors, such as total-variation, BM3D, and deep generative models, correlates with the obtained theoretical analysis.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
