Preconditioning CGNE iteration for inverse problems

The conjugate gradient method applied to the normal equations (CGNE ) is known as efficient method for the solution of non‐symmetric linear equations. By stopping the iteration according to a discrepancy principle, CGNE can be turned into a regularization method, and thus can be applied to the solution of inverse, in particular, ill‐posed problems. We show that CGNE for inverse problems can be further accelerated by preconditioning in Hilbert scales, derive (optimal) convergence rates with respect to data noise, and give tight bounds on the iteration numbers. The theoretical results are illustrated by numerical tests. Copyright © 2007 John Wiley & Sons, Ltd.     

Optimization of the Relaxation Parameter for S.S.O.R. and A.D.I. Preconditioning

We present and compare several approaches for the optimization of the relaxation parameter both for A.D.I. and S.S.O.R. basic iteration and preconditioning conjugate gradient method. For each kind of preconditioning a detailed link between estimates of the spectral radius of the iteration matrix and of the condition number resulting from preconditioning is proposed. It allows to choose the best approach in order to obtain the optimal relaxation parameter and the corresponding optimal estimates either of the spectral radius of the iteration matrix and of the resulting condition mumber of the S.S.O.R. and A.D.I. preconditioning.     

An improved iteration regularization method and application to reconstruction of dynamic loads on a plate

We present an improved iteration regularization method for solving linear inverse problems. The algorithm considered here is detailedly given and proved that the computational costs for the proposed method are nearly the same as the Landweber iteration method, yet the number of iteration steps by the present method is even less. Meanwhile, we obtain the optimum asymptotic convergence order of the regularized solution by choosing a posterior regularization parameter based on Morozov’s discrepancy principle, and the present method is applied to the identification of the multi-source dynamic loads on a surface of the plate. Numerical simulations of two examples demonstrate the effectiveness and robustness of the present method.     

A GCV based Arnoldi-Tikhonov regularization method

For the solution of linear discrete ill-posed problems, in this paper we consider the Arnoldi-Tikhonov method coupled with the Generalized Cross Validation for the computation of the regularization parameter at each iteration. We study the convergence behavior of the Arnoldi method and its properties for the approximation of the (generalized) singular values, under the hypothesis that Picard condition is satisfied. Numerical experiments on classical test problems and on image restoration are presented.     

Strong convergence of new iterative projection methods with regularization for solving monotone variational inequalities in Hilbert spaces

In this paper, we introduce two new numerical methods for solving a variational inequality problem involving a monotone and Lipschitz continuous operator in a Hilbert space. We describe how to incorporate a regularization term depending on a parameter in the projection method and then establish the strong convergence of the resulting iterative regularization projection methods. Unlike known hybrid methods, the strong convergence of the new methods comes from the regularization technique. The first method is designed to work in the case where the Lipschitz constant of cost operator is known, whereas the second one is more easily implemented without this requirement. The reason is because the second method has used a simple computable stepsize rule. The variable stepsizes are generated by the second method at each iteration and based on the previous iterates. These stepsizes are found with only one cheap computation without line-search procedure. Several numerical experiments are implemented to show the computational effectiveness of the new methods over existing methods.     

应用正则化子建立求解不适定问题的正则化方法的探讨

根据紧算子的奇异系统理论,提出一种新的正则化子进而建立了一类新的求解不适定问题的正则化方法。分别通过正则参数的先验选取和后验确定方法,证明了正则解的收敛性并得到了其最优的渐近收敛阶;验证了应用Newton迭代法计算最佳参数的可行性。最后建立了当算子与右端均有扰动时相应的正则化求解策略。文中所述方法完善了一般优化正则化策略的构造理论。     

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     

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.     

On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, we present block SSOR and modified block SSOR iteration methods based on the special structures of the coefficient matrices. In each step of the block SSOR iteration, we employ the block LU factorization to solve the sub-systems of linear equations. We show that the block LU factorization is existent and stable when the coefficient matrices are block diagonally dominant of type-II by columns. Under suitable conditions, we establish convergence theorems for both block SSOR and modified block SSOR iteration methods. In addition, the block SSOR iteration and AF-ADI method are considered as preconditioners for the nonsymmetric systems of linear equations. Numerical experiments show that both block SSOR and modified block SSOR iterations are feasible iterative solvers and they are also effective for preconditioning Krylov subspace methods such as GMRES and BiCGSTAB when used to solve this class of systems of linear equations.     

Hybrid enriched bidiagonalization for discrete ill‐posed problems

The regularizing properties of the Golub–Kahan bidiagonalization algorithm are powerful when the associated Krylov subspace captures the dominating components of the solution. In some applications the regularized solution can be further improved by enrichment, that is, by augmenting the Krylov subspace with a low‐dimensional subspace that represents specific prior information. Inspired by earlier work on GMRES, we demonstrate how to carry these ideas over to the bidiagonalization algorithm, and we describe how to incorporate Tikhonov regularization. This leads to a hybrid iterative method where the choice of regularization parameter in each iteration also provides a stopping rule.     

A Dynamical Tikhonov Regularization for Solving Ill-posed Linear Algebraic Systems

The Tikhonov method is a famous technique for regularizing ill-posed linear problems, wherein a regularization parameter needs to be determined. This article, based on an invariant-manifold method, presents an adaptive Tikhonov method to solve ill-posed linear algebraic problems. The new method consists in building a numerical minimizing vector sequence that remains on an invariant manifold, and then the Tikhonov parameter can be optimally computed at each iteration by minimizing a proper merit function. In the optimal vector method (OVM) three concepts of optimal vector, slow manifold and Hopf bifurcation are introduced. Numerical illustrations on well known ill-posed linear problems point out the computational efficiency and accuracy of the present OVM as compared with classical ones.     

随机梯度下降法的收敛速度(英文)

本文研究了正则化格式下随机梯度下降法的收敛速度.利用线性迭代的方法,并通过参数选择,得到了随机梯度下降法的收敛速度.     

Nonmonotone equilibrium problems: coercivity conditions and weak regularization

We consider a general equilibrium problem in a finite-dimensional space setting and propose a new coercivity condition for existence of solutions. We also show that it enables us to create a broad family of regularization methods with preserving well-definiteness and convergence of the iteration sequence without additional monotonicity assumptions. Some examples of applications are also given.     

AIR Tools — A MATLAB package of algebraic iterative reconstruction methods

We present a MATLAB package with implementations of several algebraic iterative reconstruction methods for discretizations of inverse problems. These so-called row action methods rely on semi-convergence for achieving the necessary regularization of the problem. Two classes of methods are implemented: Algebraic Reconstruction Techniques (ART) and Simultaneous Iterative Reconstruction Techniques (SIRT). In addition we provide a few simplified test problems from medical and seismic tomography. For each iterative method, a number of strategies are available for choosing the relaxation parameter and the stopping rule. The relaxation parameter can be fixed, or chosen adaptively in each iteration; in the former case we provide a new “training” algorithm that finds the optimal parameter for a given test problem. The stopping rules provided are the discrepancy principle, the monotone error rule, and the NCP criterion; for the first two methods “training” can be used to find the optimal discrepancy parameter.     

On the order optimality of the regularization via inexact Newton iterations

Inexact Newton regularization methods have been proposed by Hanke and Rieder for solving nonlinear ill-posed inverse problems. Every such a method consists of two components: an outer Newton iteration and an inner scheme providing increments by regularizing local linearized equations. The method is terminated by a discrepancy principle. In this paper we consider the inexact Newton regularization methods with the inner scheme defined by Landweber iteration, the implicit iteration, the asymptotic regularization and Tikhonov regularization. Under certain conditions we obtain the order optimal convergence rate result which improves the suboptimal one of Rieder. We in fact obtain a more general order optimality result by considering these inexact Newton methods in Hilbert scales.     

SOLUTION OF BACKWARD HEAT PROBLEM BY MOROZOV DISCREPANCY PRINCIPLE AND CONDITIONAL STABILITY

Consider a 1-D backward heat conduction problem with Robin boundary condition. We recover u(x, 0) and u(x, t0) for to ∈(0, T) from the measured data u(x, T) respectively. The first problem is solved by the Morozov discrepancy principle for which a 3-order iteration procedure is applied to determine the regularizing parameter. For the second one, we combine the conditional stability with the Tikhonov regularization together to construct the regularizing solution for which the convergence rate is also established. Numerical results are given to show the validity of our inversion method     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

DYNAMICAL ADJUSTMENT OF THE PROX-PARAMETER IN BUNDLE METHODS

Abstract

Proximal bundle methods are well known for their efficiency in nondifferentiable optimization. Their interpretation as approximate proximal methods yields a certain reversal poor-man formula for the regularization parameter in the proximal term. A new updating rule for this prox-parameter is introduced, based on the same scheme but making use of all the information available at each iteration. Numerical results assessing the validity of the approach are reported.     

On nondecreasing sequences of regularization parameters for nonstationary iterated Tikhonov

Nonstationary iterated Tikhonov is an iterative regularization method that requires a strategy for defining the Tikhonov regularization parameter at each iteration and an early termination of the iterative process. A classical choice for the regularization parameters is a decreasing geometric sequence which leads to a linear convergence rate. The early iterations compute quickly a good approximation of the true solution, but the main drawback of this choice is a rapid growth of the error for later iterations. This implies that a stopping criteria, e.g. the discrepancy principle, could fail in computing a good approximation. In this paper we show by a filter factor analysis that a nondecreasing sequence of regularization parameters can provide a rapid and stable convergence. Hence, a reliable stopping criteria is no longer necessary. A geometric nondecreasing sequence of the Tikhonov regularization parameters into a fixed interval is proposed and numerically validated for deblurring problems.