On Steepest-Descent-Kaczmarz methods for regularizing systems of nonlinear ill-posed equations

https://doi.org/10.1016/j.amc.2008.03.010Get rights and content

Abstract

We investigate modified steepest-descent methods coupled with a loping Kaczmarz strategy for obtaining stable solutions of nonlinear systems of ill-posed operator equations. We show that the proposed method is a convergent regularization method. Numerical tests are presented for a linear problem related to photoacoustic tomography and a nonlinear problem related to the testing of semiconductor devices.

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 xX from the set of data (y0,,yN-1)YN, where X, Y are Hilbert spaces and N1. In practical situations, we do not know the data exactly. Instead, we have only approximate measured data yiδY satisfyingyiδ-yiδi,i=0,,N-1with δi>0 (noise level). We use the notation δ(δ0,,δN-1). The finite set of data above is obtained by indirect measurements of the parameter, and this process being described by the model,Fi(x)=yi,i=0,,N-1,where Fi:DiXY, and Di 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 F(x)=y, whereF(F0,,FN-1):i=0N-1DiYNand y(y0,,yN-1). However, these methods become inefficient if N is large or the evaluations of Fi(x) and Fi(x) 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 byxk+1δ=xkδ-ωkαksk,whereskF[k](xkδ)(F[k](xkδ)-y[k]δ),ωk1,F[k](xkδ)-y[k]δτδ[k],0,otherwise,αkΦrel(sk2/F[k](xkδ)sk2),ωk=1,αmin,ωk=0.Here, αmin>0, τ[2,) are appropriate chosen numbers (see (13), (14)), [k](kmodN){0,,N-1}, and x0δ=x0X is an initial guess, possibly incorporating some a priori knowledge about the exact solution. The function Φrel:(0,)(0,) defines a sequence of relaxation parameters and is assumed to be continuous, monotonically increasing, bounded by a constant αmax, and to satisfy Φ(s)s (see Fig. 1).

If M is an upper bound for F[k](x), then sk2/F[k](xkδ)sk21/M2 (cf. Lemma 3.2). Hence, the relaxation function Φrel needs only be defined on [1/M2,). In particular, if one chooses Φrel(s)=αmin being constant on that interval, then αk=αmin 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 αmin1/M2, whereas the adaptive choice of the relaxation parameters in the present paper allows αk being much larger than 1/M2.

The l-SDK method consists in incorporating the Kaczmarz strategy (with the loping parameters ωk) 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 N subsequent steps (starting at some multiple k of N) shall be called a cycle. The iteration should be terminated when, for the first time, all xk are equal within a cycle. That is, we stop the iteration atkδargmin{lNN:xlNδ=xlN+1δ==xlN+N-1δ}.Notice that kδ is the smallest multiple of N such thatxkδ=xkδ+1==xkδ+N-1.In the case of noise free data, δi=0 in (1), we choose ωk1 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 ωk effects that the iterates defined in (4) become stationary if all components of the residual vector Fi(xkδ)-yiδ 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, ωk will vanish for some k within each iteration cycle. Therefore, the computational expensive evaluation of F[k](xk) 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 Fi are continuously Fréchet differentiable, and also assume that there exist x0X, M>0, and ρ>0 such thatFi(x)M,xBρ(x0)i=0N-1Di.Notice that x0δ=x0 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 xkδ, αk, ωk, and sk are defined by Eqs. (4), (5), (6), (7).

Our first goal is to prove convergence of the l-SDK iteration for δ=0. For exact data y=(y0,,yN-1), the iterates in (4) are denoted by xk.

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 XL2(D) denote the Hilbert space of all square integrable functions in the unit disc DR2, and let Y denote the Hilbert space of all functions y:[0,2]R with y202y(t)tdt<. We consider the system,Mix=yi,i=0,,N-1,where Mi:XY,(Mix)(t)1πS1x(ξi+tσ)dΩ(σ),t[0,2],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 ith 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)

  • P.P.B. Eggermont et al.

    Iterative algorithms for large partitioned linear systems, with applications to image reconstruction

    Linear Algebra and Applications

    (1981)
  • A.B. Bakushinsky et al.

    Iterative methods for approximate solution of inverse problems

    (2004)
  • M. Burger et al.

    On inverse problems for semiconductor equations

    Milan Journal of Mathematics

    (2004)
  • M. Burger et al.

    Identification of doping profiles in semiconductor devices

    Inverse Problems

    (2001)
  • M. Burger et al.

    Regularizing Newton–Kaczmarz methods for nonlinear ill-posed problems

    SIAM Journal on Numerical Analysis

    (2006)
  • Y. Censor et al.

    Strong underrelaxation in Kaczmarz’s method for inconsistent systems

    Numerische Mathematik

    (1983)
  • H.W. Engl et al.

    Regularization of Inverse Problems

    (1996)
  • D. Finch et al.

    The spherical mean value operator with centers on a sphere

    Inverse Problems

    (2007)
  • P. Burgholzer et al.

    Thermoacoustic tomography with integrating area and line detectors

    IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control

    (2005)
  • M. Haltmeier et al.

    Kaczmarz methods for regularizing nonlinear ill-posed equations. II. Applications

    Inverse Problems and Imaging

    (2007)
  • M. Haltmeier et al.

    Kaczmarz methods for regularizing nonlinear ill-posed equations. I. Convergence analysis

    Inverse Problems and Imaging

    (2007)
  • M. Hanke

    Conjugate Gradient Type Methods for Ill-posed Problems

    (1995)
  • M. Hanke et al.

    A convergence analysis of Landweber iteration for nonlinear ill-posed problems

    Numerische Mathematik

    (1995)
  • M.R. Hestenes et al.

    On the convergence of the conjugate gradient method for singular linear operator equations

    Journal of research of the National Bureau of Standards

    (1952)
  • S. Kaczmarz

    Approximate solution of systems of linear equations

    International Journal of Control

    (1993)
  • B. Kaltenbacher, A. Neubauer, O. Scherzer, Iterative regularization methods for nonlinear ill-posed problems, de...
  • R. Kowar et al.

    Convergence analysis of a Landweber–Kaczmarz method for solving nonlinear ill-posed problems

    Ill Posed and Inverse Problems (Book Series)

    (2002)
  • Cited by (0)

    View full text