Theory and the methods of solution of ill-posed problems

One gives a survey of the fundamental directions and results up to 1981, inclusively, regarding the topic mentioned in the title.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 20, pp. 116–178, 1982.     

Relationship of several variational methods for the approximate solution of ill-posed problems

A study is made of the relationship among three known methods for the approximate solution of linear operator equations of the first kind.Translated from Matematicheskie Zametki, Vol. 7, No. 3, pp. 265–272, March, 1970.I wish to express my deep gratitude to V. K. Ivanov for his interest in my work and for valuable remarks.     

On the optimization of projection-iterative methods for the approximate solution of ill-posed problems

We consider a new version of the projection-iterative method for the solution of operator equations of the first kind. We show that it is more economical in the sense of amount of used discrete information.     

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.     

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.     

On the conditions of convergence for one class of methods used for the solution of ill-posed problems

We propose a new class of projection methods for the solution of ill-posed problems with inaccurately specified coefficients. For methods from this class, we establish the conditions of convergence to the normal solution of an operator equation of the first kind. We also present additional conditions for these methods guaranteeing the convergence with a given rate to normal solutions from a certain set. Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 6, pp. 843–850, June, 2008.     

Kernel polynomials for the solution of indefinite and ill-posed problems

We introduce a new family of semiiterative schemes for the solution of ill-posed linear equations with selfadjoint and indefinite operators. These schemes avoid the normal equation system and thus benefit directly from the structure of the problem. As input our method requires an enclosing interval of the spectrum of the indefinite operator, based on some a priori knowledge. In particular, for positive operators the schemes are mathematically equivalent to the so-called -methods of Brakhage. In a way, they can therefore be seen as appropriate extensions of the -methods to the indefinite case. This extension is achieved by substituting the orthogonal polynomials employed by Brakhage in the definition of the -methods by appropriate kernel polynomials. We determine the rate of convergence of the new methods and establish their regularizing properties.     

Iterative methods for ill-posed problems and semiconvergent sequences

Iterative schemes, such as LSQR and RRGMRES, are among the most efficient methods for the solution of large-scale ill-posed problems. The iterates generated by these methods form semiconvergent sequences. A meaningful approximation of the desired solution of an ill-posed problem often can be obtained by choosing a suitable member of this sequence. However, it is not always a simple matter to decide which member to choose. Semiconvergent sequences also arise when approximating integrals by asymptotic expansions, and considerable experience and analysis of how to choose a suitable member of a semiconvergent sequence in this context are available. The present note explores how the guidelines developed within the context of asymptotic expansions can be applied to iterative methods for ill-posed problems.     

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.     

The instability of some gradient methods for ill-posed problems

Summary For the solution of linear ill-posed problems some gradient methods like conjugate gradients and steepest descent have been examined previously in the literature. It is shown that even though these methods converge in the case of exact data their instability makes it impossible to base a-priori parameter choice regularization methods upon them.     

V-cycle convergence of some multigrid methods for ill-posed problems

For ill-posed linear operator equations we consider some V-cycle multigrid approaches, that, in the framework of Bramble, Pasciak, Wang, and Xu (1991), we prove to yield level independent contraction factor estimates. Consequently, we can incorporate these multigrid operators in a full multigrid method, that, together with a discrepancy principle, is shown to act as an iterative regularization method for the underlying infinite-dimensional ill-posed problem. Numerical experiments illustrate the theoretical results.

     

Noise-reducing cascadic multilevel methods for linear discrete ill-posed problems

Cascadic multilevel methods for the solution of linear discrete ill-posed problems with noise-reducing restriction and prolongation operators recently have been developed for the restoration of blur- and noise-contaminated images. This is a particular ill-posed problem. The multilevel methods were found to determine accurate restorations with fairly little computational work. This paper describes noise-reducing multilevel methods for the solution of general linear discrete ill-posed problems.     

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.     

Iteration methods for convexly constrained ill-posed problems in hilbert space

Minimization problems in Hilbert space with quadratic objective function and closed convex constraint set C are considered. In case the minimum is not unique we are looking for the solution of minimal norm. If a problem is ill-posed, i.e. if the solution does not depend continuously on the data, and if the data are subject to errors then it has to be solved by means of regularization methods. The regularizing properties of some gradient projection methods—i.e. convergence for exact data, order of convergence under additional assumptions on the solution and stability for perturbed data—are the main issues of this paper.     

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.     

Asymptotics of orthogonal polynomials and the numerical solution of ill-posed problems

The paper reviews the impact of modern orthogonal polynomial theory on the analysis of numerical algorithms for ill-posed problems. Of major importance are uniform bounds for orthogonal polynomials on the support of the weight function, the growth of the extremal zeros, and asymptotics of the Christoffel functions.     

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.