An L-ribbon for large underdetermined linear discrete ill-posed problems

The L-curve is a popular aid for determining a suitable value of the regularization parameter when solving ill-conditioned linear systems of equations with a right-hand side vector, which is contaminated by errors of unknown size. However, for large problems, the computation of the L-curve can be quite expensive, because 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. Recently, an approximation of the L-curve, referred to as the L-ribbon, was introduced to address this difficulty. The present paper discusses how to organize the computation of the L-ribbon when the matrix of the linear system of equations has many more columns than rows. Numerical examples include an application to computerized tomography.     

L-Curve and Curvature Bounds for Tikhonov Regularization

The L-curve is a popular aid for determining a suitable value of the regularization parameter when solving linear discrete ill-posed problems by Tikhonov regularization. However, the computational effort required to determine the L-curve and its curvature can be prohibitive for large-scale problems. Recently, inexpensively computable approximations of the L-curve and its curvature, referred to as the L-ribbon and the curvature-ribbon, respectively, were proposed for the case when the regularization operator is the identity matrix. This note discusses the computation and performance of the L- and curvature-ribbons when the regularization operator is an invertible matrix.     

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.     

Lanczos-Based Exponential Filtering for Discrete Ill-Posed Problems

We describe regularizing iterative methods for the solution of large ill-conditioned linear systems of equations that arise from the discretization of linear ill-posed problems. The regularization is specified by a filter function of Gaussian type. A parameter determines the amount of regularization applied. The iterative methods are based on a truncated Lanczos decomposition and the filter function is approximated by a linear combination of Lanczos polynomials. A suitable value of the regularization parameter is determined by an L-curve criterion. Computed examples that illustrate the performance of the methods are presented.     

Iterative exponential filtering for large discrete ill-posed problems

Summary. We describe a new iterative method for the solution of large, very ill-conditioned linear systems of equations that arise when discretizing linear ill-posed problems. The right-hand side vector represents the given data and is assumed to be contaminated by measurement errors. Our method applies a filter function of the form with the purpose of reducing the influence of the errors in the right-hand side vector on the computed approximate solution of the linear system. Here is a regularization parameter. The iterative method is derived by expanding in terms of Chebyshev polynomials. The method requires only little computer memory and is well suited for the solution of large-scale problems. We also show how a value of and an associated approximate solution that satisfies the Morozov discrepancy principle can be computed efficiently. An application to image restoration illustrates the performance of the method. Received January 25, 1997 / Revised version received February 9, 1998 / Published online July 28, 1999     

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.     

Vector extrapolation enhanced TSVD for linear discrete ill-posed problems

The truncated singular value decomposition (TSVD) is a popular solution method for small to moderately sized linear ill-posed problems. The truncation index can be thought of as a regularization parameter; its value affects the quality of the computed approximate solution. The choice of a suitable value of the truncation index generally is important, but can be difficult without auxiliary information about the problem being solved. This paper describes how vector extrapolation methods can be combined with TSVD, and illustrates that the determination of the proper value of the truncation index is less critical for the combined extrapolation-TSVD method than for TSVD alone. The numerical performance of the combined method suggests a new way to determine the truncation index. In memory of Gene H. Golub.     

Minimal Zero Norm Solutions of Linear Complementarity Problems

In this paper, we study minimal zero norm solutions of the linear complementarity problems, defined as the solutions with smallest cardinality. Minimal zero norm solutions are often desired in some real applications such as bimatrix game and portfolio selection. We first show the uniqueness of the minimal zero norm solution for Z-matrix linear complementarity problems. To find minimal zero norm solutions is equivalent to solve a difficult zero norm minimization problem with linear complementarity constraints. We then propose a p norm regularized minimization model with p in the open interval from zero to one, and show that it can approximate minimal zero norm solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, that can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to get desired sparsity. Based on the theoretical results, we design a sequential smoothing gradient method to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and get minimal zero norm solutions of linear complementarity problems.     

A new variant of L-curve for Tikhonov regularization

In this paper we introduce a new variant of L-curve to estimate the Tikhonov regularization parameter for the regularization of discrete ill-posed problems. This method uses the solution norm versus the regularization parameter. The numerical efficiency of this new method is also discussed by considering some test problems.     

L-曲线估计确定正则参数的双网格迭代法

本文考虑对不适定问题离散化得到的大规模不适定线性方程组进行Tiknonov正则化,然后用双网格迭代法求解得到的Tikhonov正则化方程组,并用L-曲线估计法来确定正则参数.试验问题的数值结果表明双网格迭代法求解正则化后的对称正定线性方程组效果很好,且L-曲线估计法确定正则参数计算量很小.     

Regularization of Ill-Posed Problems by Envelope Guided Conjugate Gradients

Abstract

We propose a new way to iteratively solve large scale ill-posed problems by exploiting the relation between Tikhonov regularization and multiobjective optimization to obtain, iteratively, approximations to the Tikhonov L-curve and its corner. Monitoring the change of the approximate L-curves allows us to adjust the regularization parameter adaptively during a preconditioned conjugate gradient iteration, so that the desired solution can be reconstructed with a low number of iterations. We apply the technique to an idealized image reconstruction problem in positron emission tomography.     

A new L-curve for ill-posed problems

The truncated singular value decomposition is a popular method for the solution of linear ill-posed problems. The method requires the choice of a truncation index, which affects the quality of the computed approximate solution. This paper proposes that an L-curve, which is determined by how well the given data (right-hand side) can be approximated by a linear combination of the first (few) left singular vectors (or functions), be used as an aid for determining the truncation index.     

Application of denoising methods to regularizationof ill-posed problems

Linear systems of equations and linear least-squares problems with a matrix whose singular values “cluster” at the origin and with an error-contaminated data vector arise in many applications. Their numerical solution requires regularization, i.e., the replacement of the given problem by a nearby one, whose solution is less sensitive to the error in the data. The amount of regularization depends on a parameter. When an accurate estimate of the norm of the error in the data is known, this parameter can be determined by the discrepancy principle. This paper is concerned with the situation when the error is white Gaussian and no estimate of the norm of the error is available, and explores the possibility of applying a denoising method to both reduce this error and to estimate its norm. Applications to image deblurring are presented.     

An approximate solution of a Fredholm integral equation of the first kind by the residual method

A Tikhonov finite-dimensional approximation is applied to a Fredholm integral equation of the first kind. This allows using a variational regularization method with a regularization parameter from the residual principle and reducing the problem to a system of linear algebraic equations. The accuracy of the approximate solution is estimated with allowance for the error of the finitedimensional approximation of the problem. The use of this approach is illustrated by solving an inverse boundary value problem for the heat conduction equation.     

On the almost rank deficient case of the least squares problem

This paper studies properties of the solutions to overdetermined systems of linear equations whose matrices are almost rank deficient. Let such a system be approximated by the system of rankr which is closest in the euclidean matrix norm. The residual of the approximate solution depends on the scaling of the independent variable. Sharp bounds are given for the sensitivity of the residual to the scaling of the independent variable. It turns out that these bounds depend critically on a few factors which can be computed in connection with the singular value decomposition. Further the influence from the scaling on the pseudo-inverse solution of a rank deficient system is estimated.This work was sponsored by the Swedish Institute of Applied Mathematics.     

An iterative method with error estimators

Iterative methods for the solution of linear systems of equations produce a sequence of approximate solutions. In many applications it is desirable to be able to compute estimates of the norm of the error in the approximate solutions generated and terminate the iterations when the estimates are sufficiently small. This paper presents a new iterative method based on the Lanczos process for the solution of linear systems of equations with a symmetric matrix. The method is designed to allow the computation of estimates of the Euclidean norm of the error in the computed approximate solutions. These estimates are determined by evaluating certain Gauss, anti-Gauss, or Gauss–Radau quadrature rules.     

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.     

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.     

The approximate regularization of index-2 differential-algebraic problems

The approximate regularization method is introduced for the solution of index-2 Hessenberg systems of differential-algebraic equations. This approach is based on using a Taylor-series-type method, which results in a singular perturbation ordinary differential systems. For linear problems, it is shown that this approach is stable. To compare with a partial regularization, the approximate regularization appears to be promising.