Tikhonov Regularization of Large Linear Problems

Many numerical methods for the solution of linear ill-posed problems apply Tikhonov regularization. This paper presents a new numerical method, based on Lanczos bidiagonalization and Gauss quadrature, for Tikhonov regularization of large-scale problems. An estimate of the norm of the error in the data is assumed to be available. This allows the value of the regularization parameter to be determined by the discrepancy principle.     

Estimation of the L-Curve via Lanczos Bidiagonalization

The L-curve criterion is often applied to determine a suitable value of the regularization parameter when solving ill-conditioned linear systems of equations with a right-hand side contaminated by errors of unknown norm. However, the computation of the L-curve is quite costly for large problems; the determination of a point on the L-curve requires that both the norm of the regularized approximate solution and the norm of the corresponding residual vector be available. Therefore, usually only a few points on the L-curve are computed and these values, rather than the L-curve, are used to determine a value of the regularization parameter. We propose a new approach to determine a value of the regularization parameter based on computing an L-ribbon that contains the L-curve in its interior. An L-ribbon can be computed fairly inexpensively by partial Lanczos bidiagonalization of the matrix of the given linear system of equations. A suitable value of the regularization parameter is then determined from the L-ribbon, and we show that an associated approximate solution of the linear system can be computed with little additional work.     

On the choice of solution subspace for nonstationary iterated Tikhonov regularization

Tikhonov regularization is a popular method for the solution of linear discrete ill-posed problems with error-contaminated data. Nonstationary iterated Tikhonov regularization is known to be able to determine approximate solutions of higher quality than standard Tikhonov regularization. We investigate the choice of solution subspace in iterative methods for nonstationary iterated Tikhonov regularization of large-scale problems. Generalized Krylov subspaces are compared with Krylov subspaces that are generated by Golub–Kahan bidiagonalization and the Arnoldi process. Numerical examples illustrate the effectiveness of the methods.     

Arnoldi–Tikhonov regularization methods

Tikhonov regularization for large-scale linear ill-posed problems is commonly implemented by determining a partial Lanczos bidiagonalization of the matrix of the given system of equations. This paper explores the possibility of instead computing a partial Arnoldi decomposition of the given matrix. Computed examples illustrate that this approach may require fewer matrix–vector product evaluations and, therefore, less arithmetic work. Moreover, the proposed range-restricted Arnoldi–Tikhonov regularization method does not require the adjoint matrix and, hence, is convenient to use for problems for which the adjoint is difficult to evaluate.     

On the computation of a truncated SVD of a large linear discrete ill-posed problem

The singular value decomposition is commonly used to solve linear discrete ill-posed problems of small to moderate size. This decomposition not only can be applied to determine an approximate solution but also provides insight into properties of the problem. However, large-scale problems generally are not solved with the aid of the singular value decomposition, because its computation is considered too expensive. This paper shows that a truncated singular value decomposition, made up of a few of the largest singular values and associated right and left singular vectors, of the matrix of a large-scale linear discrete ill-posed problems can be computed quite inexpensively by an implicitly restarted Golub–Kahan bidiagonalization method. Similarly, for large symmetric discrete ill-posed problems a truncated eigendecomposition can be computed inexpensively by an implicitly restarted symmetric Lanczos method.     

A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations

An iterative method based on Lanczos bidiagonalization is developed for computing regularized solutions of large and sparse linear systems, which arise from discretizations of ill-posed problems in partial differential or integral equations. Determination of the regularization parameter and termination criteria are discussed. Comments are given on the computational implementation of the algorithm.Dedicated to Peter Naur on the occasion of his 60th birthday     

A Modified Tikhonov Regularization for Linear Operator Equations

We construct with the aid of regularizing filters a new class of improved regularization methods, called modified Tikhonov regularization (MTR), for solving ill-posed linear operator equations. Regularizing properties and asymptotic order of the regularized solutions are analyzed in the presence of noisy data and perturbation error in the operator. With some accurate estimates in the solution errors, optimal convergence order of the regularized solutions is obtained by a priori choice of the regularization parameter. Furthermore, numerical results are given for several ill-posed integral equations, which not only roughly coincide with the theoretical results but also show that MTR can be more accurate than ordinary Tikhonov regularization (OTR).     

The fractional Tikhonov regularization method for simultaneous inversion of the source term and initial value in a space-fractional Allen-Cahn equation

In this paper, we consider the inverse problem for identifying the source term and initial value simultaneously in a space-fractional Allen-Cahn equation. This problem is ill-posed, i.e., the solution of this problem does not depend continuously on the data. The fractional Tikhonov method is used to solve this problem. Under the a priori and the a posteriori regularization parameter choice rules, the error estimates between the regularization solutions and the exact solutions are obtained, respectively. Different numerical examples are presented to illustrate the validity and effectiveness of our method.     

双调和方程柯西问题的修正的Tikhonov正则化方法

本文研究了双调和方程柯西问题,这类是不适定的,即问题的解(如果存在)不连续依赖于测量数据.首先在精确解的先验假设下给出问题的条件稳定性结果.接着利用修正的Tikhonov正则化方法求解此不适定问题.在先验和后验正则化参数选取规则下,给出正则解和精确解之间的误差估计式.最后给出几个数值例子验证此正则化方法求解此类反问题的有效性.     

A regularization method for solving the Cauchy problem for the Helmholtz equation

In this paper, we investigate a Cauchy problem associated with Helmholtz-type equation in an infinite “strip”. This problem is well known to be severely ill-posed. The optimal error bound for the problem with only nonhomogeneous Neumann data is deduced, which is independent of the selected regularization methods. A framework of a modified Tikhonov regularization in conjunction with the Morozov’s discrepancy principle is proposed, it may be useful to the other linear ill-posed problems and helpful for the other regularization methods. Some sharp error estimates between the exact solutions and their regularization approximation are given. Numerical tests are also provided to show that the modified Tikhonov method works well.     

The tensor Golub–Kahan–Tikhonov method applied to the solution of ill-posed problems with a t-product structure

This paper discusses an application of partial tensor Golub–Kahan bidiagonalization to the solution of large-scale linear discrete ill-posed problems based on the t-product formalism for third-order tensors proposed by Kilmer and Martin (M. E. Kilmer and C. D. Martin, Factorization strategies for third order tensors, Linear Algebra Appl., 435 (2011), pp. 641-658). The solution methods presented first reduce a given (large-scale) problem to a problem of small size by application of a few steps of tensor Golub–Kahan bidiagonalization and then regularize the reduced problem by Tikhonov's method. The regularization operator is a third-order tensor, and the data may be represented by a matrix, that is, a tensor slice, or by a general third-order tensor. A regularization parameter is determined by the discrepancy principle. This results in fully automatic solution methods that neither require a user to choose the number of bidiagonalization steps nor the regularization parameter. The methods presented extend available methods for the solution for linear discrete ill-posed problems defined by a matrix operator to linear discrete ill-posed problems defined by a third-order tensor operator. An interlacing property of singular tubes for third-order tensors is shown and applied. Several algorithms are presented. Computed examples illustrate the advantage of the tensor t-product approach, in comparison with solution methods that are based on matricization of the tensor equation.     

Some results on the regularization of LSQR for large-scale discrete ill-posed problems

LSQR, a Lanczos bidiagonalization based Krylov subspace iterative method, and its mathematically equivalent conjugate gradient for least squares problems (CGLS) applied to normal equations system, are commonly used for large-scale discrete ill-posed problems. It is well known that LSQR and CGLS have regularizing effects, where the number of iterations plays the role of the regularization parameter. However, it has long been unknown whether the regularizing effects are good enough to find best possible regularized solutions. Here a best possible regularized solution means that it is at least as accurate as the best regularized solution obtained by the truncated singular value decomposition (TSVD) method. We establish bounds for the distance between the k-dimensional Krylov subspace and the k-dimensional dominant right singular space. They show that the Krylov subspace captures the dominant right singular space better for severely and moderately ill-posed problems than for mildly ill-posed problems. Our general conclusions are that LSQR has better regularizing effects for the first two kinds of problems than for the third kind, and a hybrid LSQR with additional regularization is generally needed for mildly ill-posed problems. Exploiting the established bounds, we derive an estimate for the accuracy of the rank k approximation generated by Lanczos bidiagonalization. Numerical experiments illustrate that the regularizing effects of LSQR are good enough to compute best possible regularized solutions for severely and moderately ill-posed problems, stronger than our theory predicts, but they are not for mildly ill-posed problems and additional regularization is needed.     

关于一类广义Tikhonov 正则化方法的饱和效应分析

Tikhonov正则化方法是研究不适定问题最重要的正则化方法之一,但由于这种方法的饱和效应出现的太早,使得无法随着对解的光滑性假设的提高而提高正则逼近解的收敛率,也即对高的光滑性假设,正则解与准确解的误差估计不可能达到阶数最优.Schrroter T 和Tautenhahn U给出了一类广义Tikhonov正则化方法并重点讨论了它的最优误差估计, 但却未能对该方法的饱和效应进行研究.本文对此进行了仔细分析,并发现此方法可以防止饱和效应,而且数值试验结果表明此方法计算效果良好.     

A regularization method for solving the radially symmetric backward heat conduction problem

This work is devoted to solving the radially symmetric backward heat conduction problem, starting from the final temperature distribution. The problem is ill-posed: the solution (if it exists) does not depend continuously on the given data. A modified Tikhonov regularization method is proposed for solving this inverse problem. A quite sharp estimate of the error between the approximate solution and the exact solution is obtained with a suitable choice of regularization parameter. A numerical example is presented to verify the efficiency and accuracy of the method.     

Optimal order results for a class of regularization methods using unbounded operators

A class of regularization methods using unbounded regularizing operators is considered for obtaining stable approximate solutions for ill-posed operator equations. With an a posteriori as well as an a priori parameter choice strategy, it is shown that the method yields the optimal order. Error estimates have also been obtained under stronger assumptions on the generalized solution. The results of the paper unify and simplify many of the results available in the literature. For example, the optimal results of the paper include, as particular cases for Tikhonov regularization, the main result of Mair (1994) with an a priori parameter choice, and a result of Nair (1999) with an a posteriori parameter choice. Thus the observations of Mair (1994) on Tikhonov regularization of ill-posed problems involving finitely and infinitely smoothing operators is applicable to various other regularization procedures as well. Subsequent results on error estimates include, as special cases, an optimal result of Vainikko (1987) and also some recent results of Tautenhahn (1996) in the setting of Hilbert scales.     

An iterative Lavrentiev regularization method

This paper presents an iterative method for the computation of approximate solutions of large linear discrete ill-posed problems by Lavrentiev regularization. The method exploits the connection between Lanczos tridiagonalization and Gauss quadrature to determine inexpensively computable lower and upper bounds for certain functionals. This approach to bound functionals was first described in a paper by Dahlquist, Eisenstat, and Golub. A suitable value of the regularization parameter is determined by a modification of the discrepancy principle. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65R30, 65R32, 65F10     

On a terminal value problem for a generalization of the fractional diffusion equation with hyper-Bessel operator

In this paper, we consider an inverse problem of recovering the initial value for a generalization of time-fractional diffusion equation, where the time derivative is replaced by a regularized hyper-Bessel operator. First, we investigate the existence and regularity of our terminal value problem. Then we show that the backward problem is ill-posed, and we propose a regularizing scheme using a fractional Tikhonov regularization method. We also present error estimates between the regularized solution and the exact solution using two parameter choice rules.     

Combining approximate solutions for linear discrete ill-posed problems

Linear discrete ill-posed problems of small to medium size are commonly solved by first computing the singular value decomposition of the matrix and then determining an approximate solution by one of several available numerical methods, such as the truncated singular value decomposition or Tikhonov regularization. The determination of an approximate solution is relatively inexpensive once the singular value decomposition is available. This paper proposes to compute several approximate solutions by standard methods and then extract a new candidate solution from the linear subspace spanned by the available approximate solutions. We also describe how the method may be used for large-scale problems.     

Regularization of Discrete Ill-Posed Problems

The paper concerns conditioning aspects of finite-dimensional problems arising when the Tikhonov regularization is applied to discrete ill-posed problems. A relation between the regularization parameter and the sensitivity of the regularized solution is investigated. The main conclusion is that the condition number can be decreased only to the square root of that for the nonregularized problem. The convergence of solutions of regularized discrete problems to the exact generalized solution is analyzed just in the case when the regularization corresponds to the minimal condition number. The convergence theorem is proved under the assumption of the suitable relation between the discretization level and the data error. As an example the method of truncated singular value decomposition with regularization is considered. This revised version was published online in July 2006 with corrections to the Cover Date.     

Minimization of functionals on the solution of a large-scale discrete ill-posed problem

In this work we study the minimization of a linear functional defined on a set of approximate solutions of a discrete ill-posed problem. The primary application of interest is the computation of confidence intervals for components of the solution of such a problem. We exploit the technique introduced by Eldén in 1990, utilizing a parametric programming reformulation involving the solution of a sequence of quadratically constrained least squares problems. Our iterative method, which uses the connection between Lanczos bidiagonalization and Gauss-type quadrature rules to bound certain matrix functionals, is well-suited for large-scale problems, and offers a significant reduction in matrix-vector product evaluations relative to available methods.