Wavelet-based multilevel methods for linear ill-posed problems

The representation of linear operator equations in terms of wavelet bases yields a multilevel framework, which can be exploited for iterative solution. This paper describes cascadic multilevel methods that employ conjugate gradient-type methods on each level. The iterations are on each level terminated by a stopping rule based on the discrepancy principle.     

Decomposition methods for large linear discrete ill-posed problems

The solution of large linear discrete ill-posed problems by iterative methods continues to receive considerable attention. This paper presents decomposition methods that split the solution space into a Krylov subspace that is determined by the iterative method and an auxiliary subspace that can be chosen to help represent pertinent features of the solution. Decomposition is well suited for use with the GMRES, RRGMRES, and LSQR iterative schemes.     

Cascadic multilevel methods for ill-posed problems

Multilevel methods are popular for the solution of well-posed problems, such as certain boundary value problems for partial differential equations and Fredholm integral equations of the second kind. However, little is known about the behavior of multilevel methods when applied to the solution of linear ill-posed problems, such as Fredholm integral equations of the first kind, with a right-hand side that is contaminated by error. This paper shows that cascadic multilevel methods with a conjugate gradient-type method as basic iterative scheme are regularization methods. The iterations are terminated by a stopping rule based on the discrepancy principle.     

Algorithms for range restricted iterative methods for linear discrete ill-posed problems

Range restricted iterative methods based on the Arnoldi process are attractive for the solution of large nonsymmetric linear discrete ill-posed problems with error-contaminated data (right-hand side). Several derivations of this type of iterative methods are compared in Neuman et al. (Linear Algebra Appl. in press). We describe MATLAB codes for the best of these implementations. MATLAB codes for range restricted iterative methods for symmetric linear discrete ill-posed problems are also presented.     

The structure of iterative methods for symmetric linear discrete ill-posed problems

The iterative solution of large linear discrete ill-posed problems with an error contaminated data vector requires the use of specially designed methods in order to avoid severe error propagation. Range restricted minimal residual methods have been found to be well suited for the solution of many such problems. This paper discusses the structure of matrices that arise in a range restricted minimal residual method for the solution of large linear discrete ill-posed problems with a symmetric matrix. The exploitation of the structure results in a method that is competitive with respect to computer storage, number of iterations, and accuracy.     

Implementations of range restricted iterative methods for linear discrete ill-posed problems

This paper is concerned with iterative solution methods for large linear systems of equations with a matrix of ill-determined rank and an error-contaminated right-hand side. The numerical solution is delicate, because the matrix is very ill-conditioned and may be singular. It is natural to require that the computed iterates live in the range of the matrix when the latter is symmetric, because then the iterates are orthogonal to the null space. Computational experience indicates that it can be beneficial to require that the iterates live in the range of the matrix also when the latter is nonsymmetric. We discuss the design and implementation of iterative methods that determine iterates with this property. New implementations that are particularly well suited for use with the discrepancy principle are described.     

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.     

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.     

Preconditioned iterative methods for linear discrete ill-posed problems from a Bayesian inversion perspective

In this paper we revisit the solution of ill-posed problems by preconditioned iterative methods from a Bayesian statistical inversion perspective. After a brief review of the most popular Krylov subspace iterative methods for the solution of linear discrete ill-posed problems and some basic statistics results, we analyze the statistical meaning of left and right preconditioners, as well as projected-restarted strategies. Computed examples illustrating the interplay between statistics and preconditioning are also presented.     

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.     

Subspace-restricted singular value decompositions for linear discrete ill-posed problems

The truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. These problems are numerically underdetermined. Therefore, it can be beneficial to incorporate information about the desired solution into the solution process. This paper describes a modification of the singular value decomposition that permits a specified linear subspace to be contained in the solution subspace for all truncations. Modifications that allow the range to contain a specified subspace, or that allow both the solution subspace and the range to contain specified subspaces also are described.     

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.     

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.     

An iterative method for linear discrete ill-posed problems with box constraints

Many questions in science and engineering give rise to linear discrete ill-posed problems. Often it is desirable that the computed approximate solution satisfies certain constraints, e.g., that some or all elements of the computed solution be nonnegative. This paper describes an iterative method of active set-type for the solution of large-scale problems of this kind. The method employs conjugate gradient iteration with a stopping criterion based on the discrepancy principle and allows updates of the active set by more than one index at a time.     

The discrete picard condition for discrete ill-posed problems

We investigate the approximation properties of regularized solutions to discrete ill-posed least squares problems. A necessary condition for obtaining good regularized solutions is that the Fourier coefficients of the right-hand side, when expressed in terms of the generalized SVD associated with the regularization problem, on the average decay to zero faster than the generalized singular values. This is the discrete Picard condition. We illustrate the importance of this condition theoretically as well as experimentally.This work was carried out during a visit to Dept. of Mathematics, UCLA, and was supported by the Danish Natural Science Foundation, by the National Science Foundation under contract NSF-DMS87-14612, and by the Army Research Office under contract No. DAAL03-88-K-0085.     

An extrapolated TSVD method for linear discrete ill-posed problems with Kronecker structure

This paper describes a new numerical method for the solution of large linear discrete ill-posed problems, whose matrix is a Kronecker product. Problems of this kind arise, for instance, from the discretization of Fredholm integral equations of the first kind in two space-dimensions with a separable kernel. The available data (right-hand side) of many linear discrete ill-posed problems that arise in applications is contaminated by measurement errors. Straightforward solution of these problems generally is not meaningful because of severe error propagation. We discuss how to combine the truncated singular value decomposition (TSVD) with reduced rank vector extrapolation to determine computed approximate solutions that are fairly insensitive to the error in the data. Exploitation of the structure of the problem keeps the computational effort quite small.     

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     

An interior-point method for large constrained discrete ill-posed problems

Ill-posed problems are numerically underdetermined. It is therefore often beneficial to impose known properties of the desired solution, such as nonnegativity, during the solution process. This paper proposes the use of an interior-point method in conjunction with truncated iteration for the solution of large-scale linear discrete ill-posed problems with box constraints. An estimate of the error in the data is assumed to be available. Numerical examples demonstrate the competitiveness of this approach.     

GKB-FP: an algorithm for large-scale discrete ill-posed problems

We describe an algorithm for large-scale discrete ill-posed problems, called GKB-FP, which combines the Golub-Kahan bidiagonalization algorithm with Tikhonov regularization in the generated Krylov subspace, with the regularization parameter for the projected problem being chosen by the fixed-point method by Bazán (Inverse Probl. 24(3), 2008). The fixed-point method selects as regularization parameter a fixed-point of the function ‖r _λ ‖₂/‖f _λ ‖₂, where f _λ is the regularized solution and r _λ is the corresponding residual. GKB-FP determines the sought fixed-point by computing a finite sequence of fixed-points of functions ||r_l^(k)||₂/||f_l^(k)||₂\|r_{\lambda}^{(k)}\|_{2}/\|f_{\lambda}^{(k)}\|_{2}, where f_l^(k)f_{\lambda}^{(k)} approximates f _λ in a k-dimensional Krylov subspace and r_l^(k)r_{\lambda}^{(k)} is the corresponding residual. Based on this and provided the sought fixed-point is reached, we prove that the regularized solutions f_l^(k)f_{\lambda}^{(k)} remain unchanged and therefore completely insensitive to the number of iterations. This and the performance of the method when applied to well-known test problems are illustrated numerically.     

A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization

Summary. An additive Schwarz iteration is described for the fast resolution of linear ill-posed problems which are stabilized by Tikhonov regularization. The algorithm and its analysis are presented in a general framework which applies to integral equations of the first kind discretized either by spline functions or Daubechies wavelets. Numerical experiments are reported on to illustrate the theoretical results and to compare both discretization schemes. Received March 6, 1995 / Revised version received December 27, 1995