The discretized discrepancy principle under general source conditions

We discuss adaptive strategies for choosing regularization parameters in Tikhonov–Phillips regularization of discretized linear operator equations. Two rules turn out to be based entirely on data from the underlying regularization scheme. Among them, only the discrepancy principle allows us to search for the optimal regularization parameter from the easiest problem. This potential advantage cannot be achieved by the standard projection scheme. We present a modified scheme, in which the discretization level varies with the successive regularization parameters, which has the advantage, mentioned before.     

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.     

On the regularization of projection methods for solving III-posed problems

Summary In this paper we consider a class of regularization methods for a discretized version of an operator equation (which includes the case that the problem is ill-posed) with approximately given right-hand side. We propose an a priori- as well as an a posteriori parameter choice method which is similar to the discrepancy principle of Ivanov-Morozov. From results on fractional powers of selfadjoint operators we obtain convergence rates, which are (in many cases) the same for both parameter choices.     

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.

     

On the discrepancy principle for iterative and parametric methods to solve linear ill-posed equations

Summary. For the numerical solution of (non-necessarily well-posed) linear equations in Banach spaces we consider a class of iterative methods which contains well-known methods like the Richardson iteration, if the associated resolvent operator fulfils a condition with respect to a sector. It is the purpose of this paper to show that for given noisy right-hand side the discrepancy principle (being a stopping rule for the iteration methods belonging to the mentioned class) defines a regularization method, and convergence rates are proved under additional smoothness conditions on the initial error. This extends similar results obtained for positive semidefinite problems in Hilbert spaces. Then we consider a class of parametric methods which under the same resolvent condition contains the method of the abstract Cauchy problem, and (under a weaker resolvent condition) the iterated method of Lavrentiev. A modified discrepancy principle is formulated for them, and finally numerical illustrations are presented. Received August 29, 1994 / Revised version received September 19, 1995     

Morozov's discrepancy principle for tikhonov

In this paper severely ill-posed problems are studied which are represented in the form of linear operator equations with infinitely smoothing operators but with solutions having only a finite smoothness. It is well known, that the combination of Morozov's discrepancy principle and a finite dimensional version of the ordinary Tikhonov regularization is not always optimal because of its saturation property. Here it is shown, that this combination is always order-optimal in the case of severely ill-posed problems.     

On the second-order asymptotical regularization of linear ill-posed inverse problems

ABSTRACT

In this paper, we establish an initial theory regarding the second-order asymptotical regularization (SOAR) method for the stable approximate solution of ill-posed linear operator equations in Hilbert spaces, which are models for linear inverse problems with applications in the natural sciences, imaging and engineering. We show the regularizing properties of the new method, as well as the corresponding convergence rates. We prove that, under the appropriate source conditions and by using Morozov's conventional discrepancy principle, SOAR exhibits the same power-type convergence rate as the classical version of asymptotical regularization (Showalter's method). Moreover, we propose a new total energy discrepancy principle for choosing the terminating time of the dynamical solution from SOAR, which corresponds to the unique root of a monotonically non-increasing function and allows us to also show an order optimal convergence rate for SOAR. A damped symplectic iterative regularizing algorithm is developed for the realization of SOAR. Several numerical examples are given to show the accuracy and the acceleration effect of the proposed method. A comparison with other state-of-the-art methods are provided as well.     

On the quasi-optimal rules for the choice of the regularization parameter in case of a noisy operator

A usual way to characterize the quality of different a posteriori parameter choices is to prove their order-optimality on the different sets of solutions. In paper by Raus and H?marik (J Inverse Ill-Posed Probl 15(4):419–439, 2007) we introduced the property of the quasi-optimality to characterize the quality of the rule of the a posteriori choice of the regularization parameter for concrete problem Au = f in case of exact operator and discussed the quasi-optimality of different well-known rules for the a posteriori parameter choice as the discrepancy principle, the modification of the discrepancy principle, balancing principle and monotone error rule. In this paper we generalize the concept of the quasi-optimality for the case of a noisy operator and concretize results for the mentioned parameter choice rules.     

Direct Implementation of Tikhonov Regularization for the First Kind Integral Equation

A common way to handle the Tikhonov regularization method for the first kind Fredholm integral equations, is first to discretize and then to work with the final linear system. This unavoidably inflicts discretization errors which may lead to disastrous results, especially when a quadrature rule is used. We propose to regularize directly the integral equation resulting in a continuous Tikhonov problem. The Tikhonov problem is reduced to a simple least squares problem by applying the Golub-Kahan bidiagonalization (GKB) directly to the integral operator. The regularization parameter and the iteration index are determined by the discrepancy principle approach. Moreover, we study the discrete version of the proposed method resulted from numerical evaluating the needed integrals. Focusing on the nodal values of the solution results in a weighted version of GKB-Tikhonov method for linear systems arisen from the Nyström discretization. Finally, we use numerical experiments on a few test problems to illustrate the performance of our algorithms.     

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.     

Regularization properties of the sequential discrepancy principle for Tikhonov regularization in Banach spaces

The stable solution of ill-posed non-linear operator equations in Banach space requires regularization. One important approach is based on Tikhonov regularization, in which case a one-parameter family of regularized solutions is obtained. It is crucial to choose the parameter appropriately. Here, a sequential variant of the discrepancy principle is analysed. In many cases, such parameter choice exhibits the feature, called regularization property below, that the chosen parameter tends to zero as the noise tends to zero, but slower than the noise level. Here, we shall show such regularization property under two natural assumptions. First, exact penalization must be excluded, and secondly, the discrepancy principle must stop after a finite number of iterations. We conclude this study with a discussion of some consequences for convergence rates obtained by the discrepancy principle under the validity of some kind of variational inequality, a recent tool for the analysis of inverse problems.     

Multi-parameter Tikhonov regularization and model function approach to the damped Morozov principle for choosing regularization parameters

In this paper, we study the multi-parameter Tikhonov regularization method which adds multiple different penalties to exhibit multi-scale features of the solution. An optimal error bound of the regularization solution is obtained by a priori choice of multiple regularization parameters. Some theoretical results of the regularization solution about the dependence on regularization parameters are presented. Then, an a posteriori parameter choice, i.e., the damped Morozov discrepancy principle, is introduced to determine multiple regularization parameters. Five model functions, i.e., two hyperbolic model functions, a linear model function, an exponential model function and a logarithmic model function, are proposed to solve the damped Morozov discrepancy principle. Furthermore, four efficient model function algorithms are developed for finding reasonable multiple regularization parameters, and their convergence properties are also studied. Numerical results of several examples show that the damped discrepancy principle is competitive with the standard one, and the model function algorithms are efficient for choosing regularization parameters.     

Multi-parameter Tikhonov Regularization—An Augmented Approach

We study multi-parameter regularization （multiple penalties） for solving linear inverse problems to promote simultaneously distinct features of the sought-for objects. We revisit a balancing principle for choosing regularization parameters from the viewpoint of augmented Tikhonov regularization, and derive a new parameter choice strategy called the balanced discrepancy principle. A priori and a posteriori error estimates are provided to theoretically justify the principles, and numerical algorithms for efficiently implementing the principles are also provided. Numerical results on deblurring are presented to illustrate the feasibility of the balanced discrepancy principle.     

Using the L--curve for determining optimal regularization parameters

Summary. The ``L--curve' is a plot (in ordinary or doubly--logarithmic scale) of the norm of (Tikhonov--) regularized solutions of an ill--posed problem versus the norm of the residuals. We show that the popular criterion of choosing the parameter corresponding to the point with maximal curvature of the L--curve does not yield a convergent regularization strategy to solve the ill--posed problem. Nevertheless, the L--curve can be used to compute the regularization parameters produced by Morozov's discrepancy principle and by an order--optimal variant of the discrepancy principle proposed by Engl and Gfrerer in an alternate way. Received June 29, 1993 / Revised version received February 2, 1994     

A New Gradient Method for Ill-Posed Problems

In this paper, we present a new gradient method for linear and nonlinear ill-posed problems F(x) = y. Combined with the discrepancy principle as stopping rule it is a regularization method that yields convergence to an exact solution if the operator F satisfies a tangential cone condition. If the exact solution satisfies smoothness conditions, then even convergence rates can be proven. Numerical results show that the new method in most cases needs less iteration steps than Landweber iteration, the steepest descent or minimal error method.     

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.     

Dynamic programming and board games: A survey

In several of the earliest papers on dynamic programming (DP), reference was made to the possibility that the DP approach might be used to advise players on the optimal strategy for board games such as chess. Since these papers in the 1950s, there have been many attempts to develop such strategies, drawing on ideas from DP and other branches of mathematics. This paper presents a survey of those where a dynamic programming approach has been useful, or where such a formulation of the problem will allow further insight into the optimal mode of play.     

Existence of minimizers of the Mumford-Shah functional with singular operators and unbounded data

We consider the regularization of linear inverse problems by means of the minimization of a functional formed by a term of discrepancy to data and a Mumford-Shah functional term. The discrepancy term penalizes the L ² distance between a datum and a version of the unknown function which is filtered by means of a non-invertible linear operator. Depending on the type of the involved operator, the resulting variational problem has had several applications: image deblurring, or inverse source problems in the case of compact operators, and image inpainting in the case of suitable local operators, as well as the modeling of propagation of fracture. We present counterexamples showing that, despite this regularization, the problem is actually in general ill-posed. We provide, however, existence results of minimizers in a reasonable class of smooth functions out of piecewise Lipschitz discontinuity sets in two dimensions. The compactness arguments we developed to derive the existence results stem from geometrical and regularity properties of domains, interpolation inequalities, and classical compactness arguments in Sobolev spaces.     

Regularization for unconstrained vector optimization of convex functionals in Banach spaces

An operator regularization method is considered for ill-posed vector optimization of weakly lower semicontinuous essentially convex functionals on reflexive Banach spaces. The regularization parameter is chosen by a modified generalized discrepancy principle. A condition for the estimation of the convergence rate of regularized solutions is derived. This article was submitted by the author in English.