On Steepest-Descent-Kaczmarz methods for regularizing systems of nonlinear ill-posed equations
Introduction
In this paper, we propose a new method for obtaining regularized approximations of systems of nonlinear ill-posed operator equations.
The inverse problem we are interested in consists of determining an unknown physical quantity from the set of data , where , are Hilbert spaces and . In practical situations, we do not know the data exactly. Instead, we have only approximate measured data satisfyingwith (noise level). We use the notation . The finite set of data above is obtained by indirect measurements of the parameter, and this process being described by the model,where , and are the corresponding domains of definition.
Standard methods for the solution of system (2) are based in the use of iterative-type regularization methods [1], [7], [13], [16], [19] or Tikhonov-type regularization methods [7], [23], [30], [32], [33] after rewriting (2) as a single equation , whereand . However, these methods become inefficient if is large or the evaluations of and are expensive. In such a situation, Kaczmarz-type methods [6], [15], [22], [26], which cyclically consider each equation in (2) separately, are much faster [24] and are often the method of choice in practice.
For recent analysis of Kaczmarz-type methods for systems of ill-posed equations, we refer the reader to [4], [10], [11], [17].
The starting point of our approach is the steepest-descent method [7], [29] for solving ill-posed problems. Motivated by the ideas in [10], [11], we propose in this article a loping Steepest-Descent-Kaczmarz method (l-SDK method) for the solution of (2). This iterative method is defined bywhereHere, , are appropriate chosen numbers (see (13), (14)), , and is an initial guess, possibly incorporating some a priori knowledge about the exact solution. The function defines a sequence of relaxation parameters and is assumed to be continuous, monotonically increasing, bounded by a constant , and to satisfy (see Fig. 1).
If is an upper bound for , then (cf. Lemma 3.2). Hence, the relaxation function needs only be defined on . In particular, if one chooses being constant on that interval, then and the l-SDK method reduces to the loping Landweber–Kaczmarz (l-LK) method considered in [10], [11]. The convergence analysis of the l-LK method requires , whereas the adaptive choice of the relaxation parameters in the present paper allows being much larger than .
The l-SDK method consists in incorporating the Kaczmarz strategy (with the loping parameters ) in the steepest-descent method. This strategy is analog to the one introduced in [11] regarding the Landweber–Kaczmarz iteration. As usual in Kaczmarz-type algorithms, a group of subsequent steps (starting at some multiple of ) shall be called a cycle. The iteration should be terminated when, for the first time, all are equal within a cycle. That is, we stop the iteration atNotice that is the smallest multiple of such thatIn the case of noise free data, in (1), we choose and the iteration (4), (5), (6), (7) reduces to the Steepest-Descent-Kaczmarz (SDK) method, which is closely related to the Landweber–Kaczmarz (LK) method considered in [17].
It is worth noticing that, for noisy data, the l-SDK method is fundamentally different from the SDK method: The bang-bang relaxation parameter effects that the iterates defined in (4) become stationary if all components of the residual vector fall below a pre-specified threshold. This characteristic renders (4), (5), (6), (7) a regularization method (see Section 3). Another consequence of using these relaxation parameters is the fact that, after a large number of iterations, will vanish for some within each iteration cycle. Therefore, the computational expensive evaluation of might be loped, making the l-SDK method in (4), (5), (6), (7) a fast alternative to the LK method in [17]. Since in praxis the steepest-descent method performs better than the Landweber method, the l-SDK is expected to be more efficient than the l-LK method [10], [11]. Our numerical experiments (mainly for the nonlinear problem considered in Section 5) corroborate this conjecture.
The article is outlined as follows. In Section 2, we formulate basic assumptions and derive some auxiliary estimates required for the analysis. In Section 3, we provide a convergence analysis for the l-SDK method. In Sections 4 Limited view problem in photoacoustic computed tomography, 5 An inverse doping problem we compare the numerical performance of the l-SDK method with other standard methods for inverse problems in photoacoustic tomography and in semiconductors, respectively.
Section snippets
Assumptions and basic results
We begin this section by introducing some assumptions, that are necessary for the convergence analysis presented in the following section. These assumptions derive from the classical assumptions used in the analysis of iterative regularization methods [7], [16], [29].
First, we assume that the operators are continuously Fréchet differentiable, and also assume that there exist , , and such thatNotice that is used as starting value of the l-SDK
Convergence analysis of the loping Steepest-Descent-Kaczmarz method
In this section, we provide a complete convergence analysis for the l-SDK iteration, showing that it is a convergent regularization method in the sense of [7] (see Theorem 3.3, Theorem 3.6 below). Throughout this section, we assume that (10), (11), (12), (13) hold, and that , , , and are defined by Eqs. (4), (5), (6), (7).
Our first goal is to prove convergence of the l-SDK iteration for . For exact data , the iterates in (4) are denoted by .
Limited view problem in photoacoustic computed tomography
In this section, we compare the numerical performance of loping Kaczmarz methods applied to a system of linear equations related to a limited view problem in photoacoustic computed tomography [8], [18], [28], [34].
Let denote the Hilbert space of all square integrable functions in the unit disc , and let denote the Hilbert space of all functions with . We consider the system,where ,correspond to a
An inverse doping problem
In this section we present another comparison of the numerical performance of the l-SDK, l-LK and LK methods. This time we consider an application related to inverse doping problems for semiconductors [2], [10], [20], [3]. For details on the mathematical modeling of this inverse problem we refer the reader to [10, Section 3].
In what follows, we describe the abstract formulation in Hilbert spaces of the problem (the so-called inverse doping problem in the linearized unipolar model for current
Conclusions
In this paper, we propose a new iterative method for inverse problems of the form (2), namely the l-SDK method. As a by-product we also formulated the SDK iteration, which is the steepest-descent counterpart of the LK method [17]. In the l-SDK iteration, we omit an update of the SDK iteration (within one cycle) if corresponding th residual is below some threshold. Consequently, the l-SDK method is not stopped until all residuals are below the specified threshold. We provided a complete
Acknowledgements
The work of M.H. and O.S. is supported by the FWF (Austrian Science Fund) Grants Y-123INF and P18172-N02. The work of A.L. and A.DC. are supported by the Brazilian National Research Council CNPq, Grants 306020/2006-8 and 474593/2007-0. The authors thank Andreas Rieder for stimulating discussion on iterative regularization methods.
References (35)
- et al.
Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
Linear Algebra and Applications
(1981) - et al.
Iterative methods for approximate solution of inverse problems
(2004) - et al.
On inverse problems for semiconductor equations
Milan Journal of Mathematics
(2004) - et al.
Identification of doping profiles in semiconductor devices
Inverse Problems
(2001) - et al.
Regularizing Newton–Kaczmarz methods for nonlinear ill-posed problems
SIAM Journal on Numerical Analysis
(2006) - et al.
Strong underrelaxation in Kaczmarz’s method for inconsistent systems
Numerische Mathematik
(1983) - et al.
Regularization of Inverse Problems
(1996) - et al.
The spherical mean value operator with centers on a sphere
Inverse Problems
(2007) - et al.
Thermoacoustic tomography with integrating area and line detectors
IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control
(2005) - et al.
Kaczmarz methods for regularizing nonlinear ill-posed equations. II. Applications
Inverse Problems and Imaging
(2007)