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.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

Regularization Using QR Factorization and the Estimation of the Optimal Parameter

In this paper we propose a direct regularization method using QR factorization for solving linear discrete ill-posed problems. The decomposition of the coefficient matrix requires less computational cost than the singular value decomposition which is usually used for Tikhonov regularization. This method requires a parameter which is similar to the regularization parameter of Tikhonov's method. In order to estimate the optimal parameter, we apply three well-known parameter choice methods for Tikhonov regularization.This revised version was published online in October 2005 with corrections to the Cover Date.     

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.     

Error estimates for large-scale ill-posed problems

The computation of an approximate solution of linear discrete ill-posed problems with contaminated data is delicate due to the possibility of severe error propagation. Tikhonov regularization seeks to reduce the sensitivity of the computed solution to errors in the data by replacing the given ill-posed problem by a nearby problem, whose solution is less sensitive to perturbation. This regularization method requires that a suitable value of the regularization parameter be chosen. Recently, Brezinski et al. (Numer Algorithms 49, 2008) described new approaches to estimate the error in approximate solutions of linear systems of equations and applied these estimates to determine a suitable value of the regularization parameter in Tikhonov regularization when the approximate solution is computed with the aid of the singular value decomposition. This paper discusses applications of these and related error estimates to the solution of large-scale ill-posed problems when approximate solutions are computed by Tikhonov regularization based on partial Lanczos bidiagonalization of the matrix. The connection between partial Lanczos bidiagonalization and Gauss quadrature is utilized to determine inexpensive bounds for a family of error estimates. In memory of Gene H. Golub. This work was supported by MIUR under the PRIN grant no. 2006017542-003 and by the University of Cagliari.     

A study on the influence of measurement location and regularization on the evaluation of boundary tractions by inverse finite element method

This work is concerned with an inverse approach to determine boundary tractions from displacements measured on a remote surface. The influence of measurement location and regularization on the evaluation of unknown tractions is mainly investigated through numerical experiments. The finite element method is employed in the inversion process, and the Tikhonov and the truncated singular value decomposition techniques are used to regularize an ill-conditioned system. The analytical relation between measurement location and the conditioning of a spring inverse problem is presented in this paper. Numerical results show that the solutions of inverse problems using the finite element method are very sensitive to measurement location. In addition, the effects of regularization and noise added to measured displacements are discussed through numerical examples.     

Pin-pointing solution of ill-conditioned square systems of linear equations

A new method is proposed for an accurate solution of nearly singular systems of linear equations. The method uses the truncated singular value decomposition of the initial coefficient matrix at the first stage and the Gaussian elimination procedure for a well-conditioned reduced system of linear equations at the last stage. In contrast to various regularization techniques, the method does not require any additional physical information on the problem.     

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 numerical study of the SVD–MFS solution of inverse boundary value problems in two‐dimensional steady‐state linear thermoelasticity

We study the reconstruction of the missing thermal and mechanical data on an inaccessible part of the boundary in the case of two‐dimensional linear isotropic thermoelastic materials from overprescribed noisy measurements taken on the remaining accessible boundary part. This inverse problem is solved by using the method of fundamental solutions together with the method of particular solutions. The stabilization of this inverse problem is achieved using several singular value decomposition (SVD)‐based regularization methods, such as the Tikhonov regularization method (Tikhonov and Arsenin, Methods for solving ill‐posed problems, Nauka, Moscow, 1986), the damped SVD and the truncated SVD (Hansen, Rank‐deficient and discrete ill‐posed problems: numerical aspects of linear inversion, SIAM, Philadelphia, 1998), whilst the optimal regularization parameter is selected according to the discrepancy principle (Morozov, Sov Math Doklady 7 (1966), 414–417), generalized cross‐validation criterion (Golub et al. Technometrics 22 (1979), 1–35) and Hansen's L‐curve method (Hansen and O'Leary, SIAM J Sci Comput 14 (1993), 1487–503). © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 168–201, 2015     

Structured linear algebra problems in adaptive optics imaging

A main problem in adaptive optics is to reconstruct the phase spectrum given noisy phase differences. We present an efficient approach to solve the least-squares minimization problem resulting from this reconstruction, using either a truncated singular value decomposition (TSVD)-type or a Tikhonov-type regularization. Both of these approaches make use of Kronecker products and the generalized singular value decomposition. The TSVD-type regularization operates as a direct method whereas the Tikhonov-type regularization uses a preconditioned conjugate gradient type iterative algorithm to achieve fast convergence.     

A truncated projected SVD method for linear discrete ill-posed problems

Truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. However, since the singular value decomposition of the matrix is independent of the right-hand side, there are linear discrete ill-posed problems for which this method fails to yield an accurate approximate solution. This paper describes a new approach to incorporating knowledge about properties of the desired solution into the solution process through an initial projection of the linear discrete ill-posed problem. The projected problem is solved by truncated singular value decomposition. Computed examples illustrate that suitably chosen projections can enhance the accuracy of the computed solution.     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

L1 regularization method in electrical impedance tomography by using the L1-curve (Pareto frontier curve)

Electrical impedance tomography (EIT), as an inverse problem, aims to calculate the internal conductivity distribution at the interior of an object from current-voltage measurements on its boundary. Many inverse problems are ill-posed, since the measurement data are limited and imperfect. To overcome ill-posedness in EIT, two main types of regularization techniques are widely used. One is categorized as the projection methods, such as truncated singular value decomposition (SVD or TSVD). The other categorized as penalty methods, such as Tikhonov regularization, and total variation methods. For both of these methods, a good regularization parameter should yield a fair balance between the perturbation error and regularized solution. In this paper a new method combining the least absolute shrinkage and selection operator (LASSO) and the basis pursuit denoising (BPDN) is introduced for EIT. For choosing the optimum regularization we use the L1-curve (Pareto frontier curve) which is similar to the L-curve used in optimising L2-norm problems. In the L1-curve we use the L1-norm of the solution instead of the L2 norm. The results are compared with the TSVD regularization method where the best regularization parameters are selected by observing the Picard condition and minimizing generalized cross validation (GCV) function. We show that this method yields a good regularization parameter corresponding to a regularized solution. Also, in situations where little is known about the noise level σ, it is also useful to visualize the L1-curve in order to understand the trade-offs between the norms of the residual and the solution. This method gives us a means to control the sparsity and filtering of the ill-posed EIT problem. Tracing this curve for the optimum solution can decrease the number of iterations by three times in comparison with using LASSO or BPDN separately.     

Regularization of differential-algebraic equations

Linear systems of ordinary differential equations with an identically singular or rectangular matrix multiplying the derivative of the unknown vector function are numerically solved by applying the least squares method and Tikhonov regularization. The deviation of the solution of the regularized problem from the solution set of the original problem is estimated depending on the regularization parameter.     

重构高阶导数的磨光方法

考虑由扰动数据重构原函数的导数问题．基于L-广义解正则化理论,提出了一个新的磨光方法的框架．给出一个具体的求解前3阶导数的算法,其中正则化策略选择了一种改进的TSVD(truncated singular value decomposition)方法(典则TSVD方法)．数值结果进一步验证了理论结果及新方法的有效性．     

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.     

Old and new parameter choice rules for discrete ill-posed problems

Linear discrete ill-posed problems are difficult to solve numerically because their solution is very sensitive to perturbations, which may stem from errors in the data and from round-off errors introduced during the solution process. The computation of a meaningful approximate solution requires that the given problem be replaced by a nearby problem that is less sensitive to disturbances. This replacement is known as regularization. A regularization parameter determines how much the regularized problem differs from the original one. The proper choice of this parameter is important for the quality of the computed solution. This paper studies the performance of known and new approaches to choosing a suitable value of the regularization parameter for the truncated singular value decomposition method and for the LSQR iterative Krylov subspace method in the situation when no accurate estimate of the norm of the error in the data is available. The regularization parameter choice rules considered include several L-curve methods, Regińska’s method and a modification thereof, extrapolation methods, the quasi-optimality criterion, rules designed for use with LSQR, as well as hybrid methods.     

Fractional Tikhonov regularization for linear discrete ill-posed problems

Tikhonov regularization is one of the most popular methods for solving linear systems of equations or linear least-squares problems with a severely ill-conditioned matrix A. This method replaces the given problem by a penalized least-squares problem. The present paper discusses measuring the residual error (discrepancy) in Tikhonov regularization with a seminorm that uses a fractional power of the Moore-Penrose pseudoinverse of AA ^T as weighting matrix. Properties of this regularization method are discussed. Numerical examples illustrate that the proposed scheme for a suitable fractional power may give approximate solutions of higher quality than standard Tikhonov regularization.     

Asymptotic L-based comparison of Tikhonov regularization and Landweber iteration

The distance between the Tikhonov and Landweber regularized solutions of a linear inverse problem is partly controlled by the L^∞-norm of the difference in their corresponding singular value filters. For large Landweber iteration number, the regularization parameter of the closest Tikhonov filter to a given Landweber filter is determined. This asymptotically computed parameter compares well with the numerically computed value even for moderate sized iteration number. A consequence of the analysis is to determine the range of singular values to which the difference in regularized solutions is most sensitive.     

The truncatedSVD as a method for regularization

The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in cases of ill-conditioned matrices with well-determined numerical rank.This work was carried out while the author visited the Dept. of Computer Science, Stanford University, California, U.S.A., and was supported in part by National Science Foundation Grant Number DCR 8412314, by a Fulbright Supplementary Grant, and by the Danish Space Board.