betaFeedback

WorksMathematics

A Batched Discrepancy Principle for Stochastic Landweber-Kaczmarz Iteration and its Application to EIT

Abstract

We consider an inverse problem given as ill-posed system of possibly nonlinear operator equations between Hilbert spaces. To solve the problem we use a stochastic mini-batch Landweber-Kaczmarz method, drawing uniformly a subset of equations in each step. As an a posteriori stopping rule, we introduce a batched version of the discrepancy principle, in which only the residual of the selected batches is monitored. Under the tangential cone condition, we establish the convergence of the iterates for exact data, the convergence of the regularized iterates for noisy data under an a priori choice of the stopping index, and the convergence of the method when it is terminated by the proposed batched discrepancy principle. Numerical experiments for the electrical impedance tomography problem illustrate the theoretical results and demonstrate the performance of the method for different batch sizes.

Introduction

Consider inverse problems in terms of a system of pp equations

Fi(x)=yi,i=1,…,p,(1)F_i(x)=y_i,\quad i=1,\ldots,p, \tag*{(1)}

where each Fi:D(Fi)⊂X→YiF_i:\mathcal{D}(F_i)\subset X\to Y_i is a possibly nonlinear operator between Hilbert spaces XX and YiY_i, each with inner products ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle and norms ∥⋅∥\|\cdot\|, respectively, and with domains D(Fi)\mathcal{D}(F_i). Such problems arise in many physical phenomena, such as in imaging, where the number of equations pp can be very large.

In practical applications, the exact data y:=(y1,…,yp)y := (y_1,\ldots,y_p) are not available. Instead we only have noisy data yδ:=(y1δ,…,ypδ)y^\delta:= (y_1^\delta,\ldots,y_p^\delta) satisfying

∥yiδ−yi∥≤δi,(2)\|y_i^\delta-y_i\|\le\delta_i, \tag*{(2)}

with noise levels δi>0\delta_i>0 for i=1,…,pi=1,\ldots,p. Since inverse problems are often ill-posed, small perturbations on the data may lead to large perturbations in the corresponding solution. Approximating the solution of (1) using noisy data yδy^\delta is done by regularization, an important area of research, see eq. the monographs [12, 35] and the references therein. The various regularization methods, which have been developed to solve single operator equations, can be applied to (1) by reformulating the problem as

F(x)=y,(3)F(x)=y, \tag*{(3)}

where F:=(F1,…,Fp):D(F)⊆X→YF := (F_1,\ldots,F_p) : \mathcal{D}(F) \subseteq X \to Y, Y=Y1×⋯×YpY = Y_1 \times\cdots\times Y_p and D(F)=⋂i=1pD(Fi)\mathcal{D}(F) = \bigcap_{i=1}^{p}\mathcal{D}(F_i). Assuming that FF has a continuous Fréchet derivative F′(⋅)F'(\cdot), one of the most notable iterative regularization methods is the Landweber iteration, with the form

xn+1δ=xnδ−F′(xnδ)∗(F(xnδ)−yδ),(4)x_{n+1}^{\delta}=x_n^{\delta}-F'(x_n^{\delta})^*(F(x_n^{\delta})-y^{\delta}), \tag*{(4)}

where F′(⋅)∗F'(\cdot)^* is the adjoint of the Fréchet derivative F′F' of FF. The convergence of iteration (4) was established in [18] when the stopping index nδn_\delta is chosen by the discrepancy principle

∥F(xnδδ)−yδ∥≤τδ<∥F(xnδ)−yδ∥,0≤n<nδ,(5)\left\|F(x_{n_\delta}^{\delta})-y^{\delta}\right\|\leq\tau\delta< \left\|F(x_n^{\delta})-y^{\delta}\right\|,\quad0\leq n<n_\delta, \tag*{(5)}

with a constant τ>1\tau>1 and δ:=δ12+⋯+δp2\delta:=\sqrt{\delta_1^2+\cdots+\delta_p^2}. Due to its simple implementation and relatively small complexity per iteration compared to variational methods (such as Tikhonov regularization), Landweber iteration has received prominent attention in the inverse problem community, with generalizations to non-smooth operators [9] and semi-iterative accelerations [17]. For convergence and regularization properties of the iteration we refer to the monographs [12, 35]. However, a single step in (4) requires evaluating the operators FiF_i and (Fi′(x))∗(F'_i(x))^* for all pp equations simultaneously, which can make the Landweber iteration inefficient in applications with a large number of equations. A way to overcome this disadvantage is to apply Kaczmarz-type methods, which require evaluating only one of the pp equations in (1) per iteration. The classical Landweber-Kaczmarz iteration for solving (1) is given by

xn+1δ=xnδ−pF[n]′(xnδ)∗(F[n](xnδ)−y[n]δ),(6)x_{n+1}^{\delta}=x_n^{\delta}-pF'_{[n]}(x_n^{\delta})^*(F_{[n]}(x_n^{\delta})-y_{[n]}^{\delta}), \tag*{(6)}

where [n]:=nmodp∈{0,1,…,p−1}[n]:=n \mathop{\rm mod} p\in\{0,1,\ldots,p-1\}. Notice that each of the pp equations in (1) is chosen cyclically per iteration in (6). The regularizing properties of this method have been studied in [37, 16]. In the related literature, the factor pp in (6) is neglected, which corresponds to rescaling the operator FF. However, here the factor pp is considered for consistency with the rest of the work. Generalizations of the method like the Steepest-Descent-Kaczmarz method [10] also include changing step sizes. Other variants of the method are the projective Landweber-Kaczmarz method [38], the averaged Kaczmarz method [39], or a Kaczmarz method with convex penalty functional [33]. However, we point out that the efficiency of the method (6) depends on how the equations in (1) are ordered [19]. To address this issue, the randomized Kaczmarz method, introduced by Strohmer and Vershynin [45] for consistent linear systems, chooses the equations in (6) randomly instead of cyclically. Closely related is the stochastic gradient descent (SGD) method, which can be seen as generalization of the randomized Kaczmarz method [40] and is for our problem defined as

xn+1δ=xnδ−pFin′(xnδ)∗(Fin(xnδ)−yinδ),(7)x_{n+1}^{\delta}=x_n^{\delta}-pF'_{i_n}(x_n^{\delta})^*(F_{i_n}(x_n^{\delta})-y_{i_n}^{\delta}), \tag*{(7)}

where the index ini_n is drawn uniformly from the set {1,…,p}\{1,\ldots,p\}. SGD was pioneered by Robbins and Monro in statistical inference [42]. Recent studies exhibit the attractiveness of SGD in large-scale problems that require efficient and practical methods, such as machine learning [6, 7], and also inspired subsequent work such as [14, 20] and the references therein. The authors in [8] used SGD in optical tomography, exhibiting promising numerical results, while the paper [24] studies SGD in inverse lithography technology. Meanwhile, for inverse problems of the form (1), recent and generalized convergence analysis of (7) under noisy data with an a priori stopping rule can be read in [27] for the linear and in [29] for the nonlinear case. The generalization to Banach spaces is analyzed in [25, 26]. Different generalizations include stochastic mirror descent [32, 21] and SGD with convex penalty [15]. Note that in the SGD literature the iteration is commonly defined with a possibly changing step size ηn\eta_n instead of the factor pp.

However, while SGD substantially lowers the computational burden per iteration compared with the full Landweber iteration, relying on a single equation per step can lead to high variance in the update direction and consequently to oscillatory, slowly converging behavior. For large-scale optimization problems various variance reduction methods have been proposed to accelerate the stochastic gradient method, inspired by machine learning problems, e.g. the stochastic variance reduced gradient (SVRG) [34], the stochastic dual coordinate ascent (SDCA) [44], the stochastic averaged gradient (SAG) [43], the SAGA algorithm [11], the stochastic recursive gradient algorithm (SARAH) [41], the epoch mixed gradient descent (EMGD) [46] and the stochastic primal-dual coordinate method (SPDC) [47]. In particular, for linear inverse problems the SVRG was analyzed in [30, 28, 31]. However their approaches involve one full Landweber step similar to (4), as well as storing past gradients, and mixing them with full gradients. Here we consider a mini-batch Kaczmarz approach. This natural compromise between the full Landweber iteration (4) and the single-equation SGD scheme selects randomly, at every iteration nn, a subset In={i1,…,ib}⊂{1,…,p}I_n = \{i_1,\ldots,i_b\} \subset\{1,\ldots,p\} of fixed batch size b:=∣In∣∈{1,…,p}b := |I_n| \in\{1,\ldots,p\}, and updates the iterate via

xn+1δ:=xnδ−ωnpb∑i∈InFi′(xnδ)∗(Fi(xnδ)−yiδ),(8)x_{n+1}^{\delta} := x_n^{\delta} - \omega_n \frac{p}{b} \sum_{i\in I_n} F_i'(x_n^{\delta})^* \left(F_i(x_n^{\delta}) - y_i^{\delta}\right), \tag*{(8)}

with an additional step control ωn\omega_n, defined as

ωn={1∑i∈In∥Fi(xnδ)−yiδ∥2≥τ2∑i∈Inδi2,0else.(9)\omega_n = \begin{cases} 1 & \sum_{i\in I_n}\left\|F_i(x_n^{\delta})-y_i^{\delta}\right\|^2 \ge\tau^2\sum_{i\in I_n}\delta_i^2,\\ 0 & \text{else.} \end{cases} \tag*{(9)}

The step control monitors the residual of the selected equations and decides, based on the discrepancy principle, whether or not the proposed step is taken.

Remark 1.1. To reduce superfluous repetitions in the calculation of the residuum, additional numerical adjustments can be added. If ωn=0\omega_n = 0 then the elements of InI_n could be excluded in the selection of the next batch In+1⊂{1,…,p}∖InI_{n+1} \subset\{1,\ldots,p\}\setminus I_n. Going on with ωn+1=0\omega_{n+1}=0 then In+2⊂{1,…,p}∖(In∪In+1)I_{n+2} \subset\{1,\ldots,p\}\setminus(I_n\cup I_{n+1}) and so on. When ωn+i=1\omega_{n+i}=1 one starts again with all indices. And when {1,…,p}∖(In∪…∪In+i)=∅\{1,\ldots,p\}\setminus(I_n\cup\ldots\cup I_{n+i})=\varnothing, the classical discrepancy principle (5) is fulfilled and the algorithm stops. This corresponds to a stochastic version of the termination criterion introduced in [16] for the deterministic Kaczmarz method.

If b=pb=p the iteration (8) recovers the full Landweber iteration (4) until the classical discrepancy principle (5) holds and remains constant then. For b=1b=1 the iteration reduces, if ωn=1\omega_n=1, to the single-equation SGD. The batch size bb interpolates between these two extremes, trading per-iteration cost against variance of the update.

For this mini-batch iteration (8) we prove convergence in expectation for noise-free data and the corresponding regularization property for a priori stopping. This extends the analysis of [32] to nonlinear operators. Additionally we propose and analyze a novel a posteriori stopping rule: The batched discrepancy principle monitors the batched residual of the last Lδ∈NL_\delta\in\mathbb{N} iterations, and is defined as

References

  1. [1]H. Bahouri, J.-Y. Chemin, and R. Danchin. Fourier analysis and nonlinear partial differential equations, volume 343 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Heidelberg, 2011.DOI
  2. [2]R. Bhattacharya and E. C. Waymire. A basic course in probability theory. Universitext. Springer, Cham, second edition, 2016.
  3. [3]G. Blanchard, M. Hoffmann, and M. Reiß. Early stopping for statistical inverse problems via truncated SVD estimation. Electron. J. Stat., 12(2):3204–3231, 2018.arxiv.org/abs/1710.07278
  4. [4]G. Blanchard, M. Hoffmann, and M. Reiß. Optimal adaptation for early stopping in statistical inverse problems. SIAM/ASA J. Uncertain. Quantif., 6(3):1043–1075, 2018.arxiv.org/abs/1606.07702
  5. [5]L. Borcea. Electrical impedance tomography. Inverse Problems, 18(6):R99–R136, 2002.
  6. [6]L. Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT’2010, pages 177–186. Physica-Verlag/Springer, Heidelberg, 2010.
  7. [7]L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Rev., 60(2):223–311, 2018.arxiv.org/abs/1606.04838
  8. [8]K. Chen, Q. Li, and J.-G. Liu. Online learning in optical tomography: a stochastic approach. Inverse Problems, 34(7):075010, 2018.DOI
  9. [9]C. Clason and V. H. Nhu. Bouligand-Landweber iteration for a non-smooth ill-posed problem. Numer. Math., 142(4):789–832, 2019.DOI
  10. [10]A. De Cezaro, M. Haltmeier, A. Leitão, and O. Scherzer. On steepest-descent-Kaczmarz methods for regularizing systems of nonlinear ill-posed equations. Appl. Math. Comput., 202(2):596–607, 2008.arxiv.org/abs/0801.3088
  11. [11]A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  12. [12]H. W. Engl, M. Hanke, and A. Neubauer. Regularization of inverse problems, volume 375 of Mathematics and its Applications. Kluwer Academic Publishers Group, Dordrecht, 1996.
  13. [13]L. C. Evans. Partial differential equations, volume 19 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, second edition, 2010.
  14. [14]I. Gitman, H. Lang, P. Zhang, and L. Xiao. Understanding the role of momentum in stochastic gradient methods. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.arxiv.org/abs/1910.13962
  15. [15]R. Gu, Z. Fu, B. Han, and H. Fu. Stochastic gradient descent method with convex penalty for ill-posed problems in Banach spaces. Inverse Problems, 41(5):055003, 2025.arxiv.org/abs/2409.04973
  16. [16]M. Haltmeier, A. Leitão, and O. Scherzer. Kaczmarz methods for regularizing nonlinear ill-posed equations. I. Convergence analysis. Inverse Probl. Imaging, 1(2):289–298, 2007.DOI
  17. [17]M. Hanke. Accelerated Landweber iterations for the solution of ill-posed equations. Numer. Math., 60(3):341–373, 1991.DOI
  18. [18]M. Hanke, A. Neubauer, and O. Scherzer. A convergence analysis of the Landweber iteration for nonlinear ill-posed problems. Numer. Math., 72(1):21–37, 1995.DOI
  19. [19]G. T. Herman and L. B. Meyer. Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Med. Imaging, 12(3):600–609, 1993.pubmed.ncbi.nlm.nih.gov/18218454
  20. [20]J. Hertrich and G. Steidl. Inertial stochastic PALM and applications in machine learning. Sampl. Theory Signal Process. Data Anal., 20(1):4, 2022.DOI
  21. [21]J. Huang, Q. Jin, X. Lu, and L. Zhang. On early stopping of stochastic mirror descent method for ill-posed inverse problems. Numer. Math., 157(2):539–571, 2025.DOI
  22. [22]L. Hucker and M. Reiß. Early stopping for conjugate gradients in statistical inverse problems. Numer. Math., 157(5):1739–1791, 2025.
  23. [23]T. Jahn and B. Jin. On the discrepancy principle for stochastic gradient descent. Inverse Problems, 36(9):095009, 2020.arxiv.org/abs/2004.14625
  24. [24]N. Jia and E. Y. Lam. Machine learning for inverse lithography: using stochastic gradient descent for robust photomask synthesis. J. Opt., 12(4):045601, 2010.DOI
  25. [25]B. Jin and Ž. Kereta. On the convergence of stochastic gradient descent for linear inverse problems in Banach spaces. SIAM J. Imaging Sci., 16(2):671–705, 2023.arxiv.org/abs/2302.05197
  26. [26]B. Jin, Ž. Kereta, and Y. Xia. Stochastic gradient descent for nonlinear inverse problems in Banach spaces. SIAM J. Imaging Sci., 19(2):1244–1271, 2026.
  27. [27]B. Jin and X. Lu. On the regularizing property of stochastic gradient descent. Inverse Problems, 35(1):015004, 2019.
  28. [28]B. Jin and Z. Zhou. On the convergence of stochastic variance reduced gradient for linear inverse problems. Inverse Problems, 42(4):045006, 2026.arxiv.org/abs/2510.14759
  29. [29]B. Jin, Z. Zhou, and J. Zou. On the convergence of stochastic gradient descent for nonlinear ill-posed problems. SIAM J. Optim., 30(2):1421–1450, 2020.arxiv.org/abs/1907.03132
  30. [30]B. Jin, Z. Zhou, and J. Zou. An analysis of stochastic variance reduced gradient for linear inverse problems. Inverse Problems, 38(2):025009, 2022.DOI
  31. [31]Q. Jin and L. Chen. Stochastic variance reduced gradient method for linear ill-posed inverse problems. Inverse Problems, 41(5):055014, 2025.arxiv.org/abs/2403.12460
  32. [32]Q. Jin, X. Lu, and L. Zhang. Stochastic mirror descent method for linear ill-posed problems in Banach spaces. Inverse Problems, 39(6):065010, 2023.DOI
  33. [33]Q. Jin and W. Wang. Landweber iteration of Kaczmarz type with general non-smooth convex penalty functionals. Inverse Problems, 29(8):085011, 2013.arxiv.org/abs/1307.4311
  34. [34]R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, pages 315–323. Curran Associates, Inc., 2013.
  35. [35]B. Kaltenbacher, A. Neubauer, and O. Scherzer. Iterative regularization methods for nonlinear ill-posed problems, volume 6 of Radon Series on Computational and Applied Mathematics. Walter de Gruyter, Berlin, 2008.
  36. [36]S. Kindermann. On the tangential cone condition for electrical impedance tomography. Electron. Trans. Numer. Anal., 57:17–34, 2022.arxiv.org/abs/2105.02635
  37. [37]R. Kowar and O. Scherzer. Convergence analysis of a Landweber-Kaczmarz method for solving nonlinear ill-posed problems. In V. G. Romanov, S. I. Kabanikhin, Y. E. Anikonov, and A. L. Bukhgeim, editors, Ill-posed and inverse problems, pages 253–270. VSP, Zeist, 2002.DOI
  38. [38]A. Leitão and B. F. Svaiter. On projective Landweber-Kaczmarz methods for solving systems of nonlinear ill-posed equations. Inverse Problems, 32(2):025004, 2016.DOI
  39. [39]H. Li and M. Haltmeier. The averaged Kaczmarz iteration for solving inverse problems. SIAM J. Imaging Sci., 11(1):618–642, 2018.DOI
  40. [40]D. Needell, N. Srebro, and R. Ward. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program., 155(1–2):549–573, 2016.arxiv.org/abs/1310.5715
  41. [41]L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proc. Mach. Learn. Res., pages 2613–2621. PMLR, 2017.arxiv.org/abs/1703.00102
  42. [42]H. Robbins and S. Monro. A stochastic approximation method. Ann. Math. Statistics, 22:400–407, 1951.
  43. [43]M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math. Program., 162(1–2):83–112, 2017.arxiv.org/abs/1309.2388
  44. [44]S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. J. Mach. Learn. Res., 14:567–599, 2013.DOI
  45. [45]T. Strohmer and R. Vershynin. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl., 15(2):262–278, 2009.arxiv.org/abs/math/0702226
  46. [46]L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access of full gradients. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
  47. [47]Y. Zhang and L. Xiao. Stochastic primal-dual coordinate method for regularized empirical risk minimization. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proc. Mach. Learn. Res., pages 353–361. PMLR, 2015.arxiv.org/abs/1409.3257

Paper details

vlnc:W_6y64ev6a
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents