Introduction
Consider inverse problems in terms of a system of p p p equations
F i ( x ) = y i , i = 1 , … , p , (1) F_i(x)=y_i,\quad i=1,\ldots,p, \tag*{(1)} F i ( x ) = y i , i = 1 , … , p , (1)
where each F i : D ( F i ) ⊂ X → Y i F_i:\mathcal{D}(F_i)\subset X\to Y_i F i : D ( F i ) ⊂ X → Y i is a possibly nonlinear operator between Hilbert spaces X X X and Y i Y_i Y i , each with inner products ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and norms ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ , respectively, and with domains D ( F i ) \mathcal{D}(F_i) D ( F i ) . Such problems arise in many physical phenomena, such as in imaging, where the number of equations p p p can be very large.
In practical applications, the exact data y : = ( y 1 , … , y p ) y := (y_1,\ldots,y_p) y := ( y 1 , … , y p ) are not available. Instead we only have noisy data y δ : = ( y 1 δ , … , y p δ ) y^\delta:= (y_1^\delta,\ldots,y_p^\delta) y δ := ( y 1 δ , … , y p δ ) satisfying
∥ y i δ − y i ∥ ≤ δ i , (2) \|y_i^\delta-y_i\|\le\delta_i, \tag*{(2)} ∥ y i δ − y i ∥ ≤ δ i , (2)
with noise levels δ i > 0 \delta_i>0 δ i > 0 for i = 1 , … , p i=1,\ldots,p i = 1 , … , 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 y δ 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)} F ( x ) = y , (3)
where F : = ( F 1 , … , F p ) : D ( F ) ⊆ X → Y F := (F_1,\ldots,F_p) : \mathcal{D}(F) \subseteq X \to Y F := ( F 1 , … , F p ) : D ( F ) ⊆ X → Y , Y = Y 1 × ⋯ × Y p Y = Y_1 \times\cdots\times Y_p Y = Y 1 × ⋯ × Y p and D ( F ) = ⋂ i = 1 p D ( F i ) \mathcal{D}(F) = \bigcap_{i=1}^{p}\mathcal{D}(F_i) D ( F ) = ⋂ i = 1 p D ( F i ) . Assuming that F F F has a continuous Fréchet derivative F ′ ( ⋅ ) F'(\cdot) F ′ ( ⋅ ) , one of the most notable iterative regularization methods is the Landweber iteration, with the form
x n + 1 δ = x n δ − F ′ ( x n δ ) ∗ ( F ( x n δ ) − y δ ) , (4) x_{n+1}^{\delta}=x_n^{\delta}-F'(x_n^{\delta})^*(F(x_n^{\delta})-y^{\delta}), \tag*{(4)} x n + 1 δ = x n δ − F ′ ( x n δ ) ∗ ( F ( x n δ ) − y δ ) , (4)
where F ′ ( ⋅ ) ∗ F'(\cdot)^* F ′ ( ⋅ ) ∗ is the adjoint of the Fréchet derivative F ′ F' F ′ of F F F . The convergence of iteration (4) was established in [18 ] when the stopping index n δ n_\delta n δ is chosen by the discrepancy principle
∥ F ( x n δ δ ) − y δ ∥ ≤ τ δ < ∥ F ( x n δ ) − 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)} F ( x n δ δ ) − y δ ≤ τ δ < F ( x n δ ) − y δ , 0 ≤ n < n δ , (5)
with a constant τ > 1 \tau>1 τ > 1 and δ : = δ 1 2 + ⋯ + δ p 2 \delta:=\sqrt{\delta_1^2+\cdots+\delta_p^2} δ := δ 1 2 + ⋯ + δ 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 F i F_i F i and ( F i ′ ( x ) ) ∗ (F'_i(x))^* ( F i ′ ( x ) ) ∗ for all p p p 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 p p p equations in (1) per iteration. The classical Landweber-Kaczmarz iteration for solving (1) is given by
x n + 1 δ = x n δ − p F [ n ] ′ ( x n δ ) ∗ ( F [ n ] ( x n δ ) − 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)} x n + 1 δ = x n δ − p F [ n ] ′ ( x n δ ) ∗ ( F [ n ] ( x n δ ) − y [ n ] δ ) , (6)
where [ n ] : = n m o d p ∈ { 0 , 1 , … , p − 1 } [n]:=n \mathop{\rm mod} p\in\{0,1,\ldots,p-1\} [ n ] := n mod p ∈ { 0 , 1 , … , p − 1 } . Notice that each of the p p p 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 p p p in (6) is neglected, which corresponds to rescaling the operator F F F . However, here the factor p p p 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
x n + 1 δ = x n δ − p F i n ′ ( x n δ ) ∗ ( F i n ( x n δ ) − y i n δ ) , (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)} x n + 1 δ = x n δ − p F i n ′ ( x n δ ) ∗ ( F i n ( x n δ ) − y i n δ ) , (7)
where the index i n i_n i n is drawn uniformly from the set { 1 , … , p } \{1,\ldots,p\} { 1 , … , 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 η n instead of the factor p p p .
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 n n n , a subset I n = { i 1 , … , i b } ⊂ { 1 , … , p } I_n = \{i_1,\ldots,i_b\} \subset\{1,\ldots,p\} I n = { i 1 , … , i b } ⊂ { 1 , … , p } of fixed batch size b : = ∣ I n ∣ ∈ { 1 , … , p } b := |I_n| \in\{1,\ldots,p\} b := ∣ I n ∣ ∈ { 1 , … , p } , and updates the iterate via
x n + 1 δ : = x n δ − ω n p b ∑ i ∈ I n F i ′ ( x n δ ) ∗ ( F i ( x n δ ) − y i δ ) , (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)} x n + 1 δ := x n δ − ω n b p i ∈ I n ∑ F i ′ ( x n δ ) ∗ ( F i ( x n δ ) − y i δ ) , (8)
with an additional step control ω n \omega_n ω n , defined as
ω n = { 1 ∑ i ∈ I n ∥ F i ( x n δ ) − y i δ ∥ 2 ≥ τ 2 ∑ i ∈ I n δ i 2 , 0 else. (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)} ω n = { 1 0 ∑ i ∈ I n F i ( x n δ ) − y i δ 2 ≥ τ 2 ∑ i ∈ I n δ i 2 , else. (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.
If b = p b=p b = p the iteration (8) recovers the full Landweber iteration (4) until the classical discrepancy principle (5) holds and remains constant then. For b = 1 b=1 b = 1 the iteration reduces, if ω n = 1 \omega_n=1 ω n = 1 , to the single-equation SGD. The batch size b b b 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 δ ∈ N L_\delta\in\mathbb{N} L δ ∈ N iterations, and is defined as
n δ = arg min n ≥ L δ − 1 { ∑ j = 0 L δ − 1 ∑ i ∈ I n − j ∥ F i ( x n − j δ ) − y i δ ∥ 2 − τ 2 δ i 2 ≤ 0 } . (10) n_\delta= \arg\min_{n\ge L_\delta-1}\left\{\sum_{j=0}^{L_\delta-1}\sum_{i\in I_{n-j}}\left\|F_i(x_{n-j}^{\delta})-y_i^\delta\right\|^2-\tau^2\delta_i^2\le0\right\}. \tag*{(10)} n δ = arg n ≥ L δ − 1 min ⎩ ⎨ ⎧ j = 0 ∑ L δ − 1 i ∈ I n − j ∑ F i ( x n − j δ ) − y i δ 2 − τ 2 δ i 2 ≤ 0 ⎭ ⎬ ⎫ . (10)
The parameter L δ L_\delta L δ is chosen a priori and corresponds to the length of the aggregation. In this work we prove under the tangential cone condition that for properly chosen τ > 1 \tau>1 τ > 1 it holds n δ < ∞ n_\delta<\infty n δ < ∞ (Lemma 2.6 ) and the iterate x n δ δ x_{n_\delta}^{\delta} x n δ δ converges for any choice L δ → ∞ L_\delta\to\infty L δ → ∞ to a solution of problem (1) as δ → 0 \delta\to0 δ → 0 (Theorem 2.3).
The proposed stopping rule goes beyond the work in [32 , 21 ] , which analyze a mini-batch approach of the stochastic mirror descent algorithm. In [32 ] the method is applied on linear inverse problems and convergence is proven only for a priori stopping. Building on that, [21 ] considers the same iteration on nonlinear operators and proposes an a posteriori stopping rule involving, differently to our approach, the full residuum ∥ F ( x n δ ) − y δ ∥ \left\|F(x_n^\delta)-y^\delta\right\| F ( x n δ ) − y δ . Further works, that analyze approaches using the full residuum, are [23 , 15 ] for SGD and [28 , 31 ] for SVRG. Note that especially for a large number of equations p p p and small batch sizes b b b the batched version of the discrepancy principle significantly reduces the computational cost per iteration compared to techniques which consider all equations simultaneously.
The batched discrepancy principle can be seen as an instance of early stopping , a technique which received some attention in recent works on (statistical) inverse problems, see e.g. [3 , 4 , 22 ] . The rationale behind is that for iterative methods, the iteration number is on the one hand directly determining the computational cost (to be kept as small as possible), and on the other hand acts as a decreasing regularization parameter (to be chosen not too small). For methods such as truncated singular value decomposition or conjugate gradients, it has been shown in the above references, that early stopping reduces the computational effort while maintaining the optimality of the underlying method, both theoretically and numerically.
The remainder of this paper is organized as follows. In § 2 we first establish the general setting of the analysis. Then we proof the convergence of the mini-batch Landweber-Kaczmarz iteration (8) in three cases. First with noise-free data, continuing with noisy data, proving convergence under a priori stopping and then under the a posteriori stopping rule defined in equation (10) . Finally, in § 3 we illustrate the theoretical findings with numerical experiments for the electrical impedance tomography (EIT) problem, a nonlinear ill-posed system with a large number of measurement equations.
Convergence
In order to establish convergence of method (8), we first define the space on which the analysis will be carried out. We follow a similar approach as in [32 ] , but correct the definition of the sample space for the batch size b b b . Let
Λ b , p = { I ⊆ { 1 , … , p } : ∣ I ∣ = b } (11) \Lambda_{b,p} = \{I \subseteq\{1,\ldots,p\}: |I|=b\} \tag*{(11)} Λ b , p = { I ⊆ { 1 , … , p } : ∣ I ∣ = b } (11)
be the sample space and let S b , p \mathcal{S}_{b,p} S b , p denote the σ \sigma σ -algebra consisting of all subsets of Λ b , p \Lambda_{b,p} Λ b , p . At each iteration step, a random element of Λ b , p \Lambda_{b,p} Λ b , p is chosen based on the uniform distribution. This means P b , p ( I ) = 1 / ( p b ) \mathbb{P}_{b,p}(I)=1/\binom{p}{b} P b , p ( I ) = 1/ ( b p ) for all I ∈ Λ b , p I \in\Lambda_{b,p} I ∈ Λ b , p , since there are ( p b ) \binom{p}{b} ( b p ) different b b b -sized subsets of { 1 , … , p } \{1,\ldots,p\} { 1 , … , p } . Therefore, for each n ≥ 1 n \ge1 n ≥ 1 , we consider x n δ x_n^\delta x n δ on the sample space
Λ b , p n : = Λ b , p × ⋯ × Λ b , p ⏟ n copies . \Lambda_{b,p}^{n} := \underbrace{\Lambda_{b,p} \times\cdots\times\Lambda_{b,p}}_{n\ \text{copies}}. Λ b , p n := n copies Λ b , p × ⋯ × Λ b , p .
equipped with the σ \sigma σ -algebra S b , p n : = ⨂ k = 1 n S b , p \mathcal{S}_{b,p}^{n} := \bigotimes_{k=1}^{n}\mathcal{S}_{b,p} S b , p n := ⨂ k = 1 n S b , p and the product probability measure denoted by
P n ( ( I 0 , … , I n − 1 ) ) : = P b , p ( I 0 ) ⋯ P b , p ( I n − 1 ) for ( I 0 , … , I n − 1 ) ∈ Λ b , p n . \mathbb{P}_{n}((I_0,\ldots,I_{n-1})) := \mathbb{P}_{b,p}(I_0)\cdots\mathbb{P}_{b,p}(I_{n-1})\quad\text{for }(I_0,\ldots,I_{n-1})\in\Lambda_{b,p}^{n}. P n (( I 0 , … , I n − 1 )) := P b , p ( I 0 ) ⋯ P b , p ( I n − 1 ) for ( I 0 , … , I n − 1 ) ∈ Λ b , p n .
According to the Kolmogorov extension theorem [2 ] , there exists a unique probability P \mathbb{P} P defined on the measurable space ( Ω , F ) : = ( Λ b , p ∞ , S b , p ∞ ) (\Omega,\mathcal{F}) := (\Lambda_{b,p}^{\infty},\mathcal{S}_{b,p}^{\infty}) ( Ω , F ) := ( Λ b , p ∞ , S b , p ∞ ) , such that each P n \mathbb{P}_{n} P n is consistent with P \mathbb{P} P . Using this, the stochastic mini-batch Landweber-Kaczmarz iteration (8) corresponds to a random variable on the probability space
( Ω , F , P ) : = ( Λ b , p ∞ , S b , p ∞ , P ) . (12) (\Omega,\mathcal{F},\mathbb{P}) := (\Lambda_{b,p}^{\infty},\mathcal{S}_{b,p}^{\infty},\mathbb{P}). \tag*{(12)} ( Ω , F , P ) := ( Λ b , p ∞ , S b , p ∞ , P ) . (12)
Note that also the stopping index n δ n_\delta n δ of the batched discrepancy principle (10) is a random variable on ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) . We denote E \mathbb{E} E as expectation on ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) and define L 2 ( Ω , X ) L^2(\Omega,X) L 2 ( Ω , X ) as the space consisting of all random variables x x x with values in X X X such that E [ ∥ x ∥ 2 ] \mathbb{E}[\|x\|^2] E [ ∥ x ∥ 2 ] is finite; this is a Hilbert space under the norm
( E [ ∥ x ∥ 2 ] ) 1 / 2 . \left(\mathbb{E}[\|x\|^2]\right)^{1/2}. ( E [ ∥ x ∥ 2 ] ) 1/2 .
As a proof tool, we will use { F n } \{\mathcal{F}_n\} { F n } to denote the natural filtration, where F n = σ ( I 0 , … , I n − 1 ) \mathcal{F}_n=\sigma(I_0,\ldots,I_{n-1}) F n = σ ( I 0 , … , I n − 1 ) . The conditional expectation E [ ⋅ ∣ F n ] \mathbb{E}[\cdot\mid\mathcal{F}_n] E [ ⋅ ∣ F n ] averages over all future batch selections l ≥ n l\ge n l ≥ n and yields an F n \mathcal{F}_n F n -measurable function, meaning it only depends on the first n n n batches ( I 0 , … , I n − 1 ) (I_0,\ldots,I_{n-1}) ( I 0 , … , I n − 1 ) . The tower property of conditional expectation,
E [ ϕ ] = E [ E [ ϕ ∣ F n ] ] \mathbb{E}[\phi]=\mathbb{E}[\mathbb{E}[\phi\mid\mathcal{F}_n]] E [ ϕ ] = E [ E [ ϕ ∣ F n ]]
for any random variable ϕ \phi ϕ on ( Ω , F , P ) (\Omega,\mathcal{F},\mathbb{P}) ( Ω , F , P ) , will be frequently used. To simplify the notation, for each index set I = { i 1 , … , i b } ⊂ { 1 , … , p } I=\{i_1,\ldots,i_b\}\subset\{1,\ldots,p\} I = { i 1 , … , i b } ⊂ { 1 , … , p } of size b b b , we set
Y I : = Y i 1 × ⋯ × Y i b , y I δ : = ( y i 1 δ , … , y i b δ ) , δ I 2 = δ i 1 2 + ⋯ + δ i b 2 Y_I:=Y_{i_1}\times\cdots\times Y_{i_b},\qquad y_I^\delta:=\left(y_{i_1}^\delta,\ldots,y_{i_b}^\delta\right),\qquad\delta_I^2=\delta_{i_1}^2+\cdots+\delta_{i_b}^2 Y I := Y i 1 × ⋯ × Y i b , y I δ := ( y i 1 δ , … , y i b δ ) , δ I 2 = δ i 1 2 + ⋯ + δ i b 2
and define F I : X → Y I F_I:X\to Y_I F I : X → Y I by
F I ( x ) : = ( F i 1 ( x ) , … , F i b ( x ) ) , ∀ x ∈ X . F_I(x):=(F_{i_1}(x),\ldots,F_{i_b}(x)),\qquad\forall x\in X. F I ( x ) := ( F i 1 ( x ) , … , F i b ( x )) , ∀ x ∈ X .
Let F I ′ F_I' F I ′ denote the Fréchet derivative of F I F_I F I . Then the method (8) can be rewritten as
x n + 1 δ = x n δ − ω n p b F I n ′ ( x n δ ) ∗ ( F I n ( x n δ ) − y I n δ ) x_{n+1}^\delta=x_n^\delta-\omega_n\frac{p}{b}F_{I_n}'(x_n^\delta)^*\left(F_{I_n}(x_n^\delta)-y_{I_n}^\delta\right) x n + 1 δ = x n δ − ω n b p F I n ′ ( x n δ ) ∗ ( F I n ( x n δ ) − y I n δ )
with step control
ω n = { 1 ∥ F I n ( x n δ ) − y I n δ ∥ ≥ τ δ I n , 0 else , \omega_n=\begin{cases}1 & \left\|F_{I_n}(x_n^\delta)-y_{I_n}^\delta\right\|\ge\tau\delta_{I_n},\\0 & \text{else},\end{cases} ω n = { 1 0 F I n ( x n δ ) − y I n δ ≥ τ δ I n , else ,
and the batched discrepancy principle simplifies to
n δ = arg min n ≥ L δ − 1 { ∑ j = 0 L δ − 1 ∥ F I n − j ( x n − j δ ) − y I n − j δ ∥ 2 − τ 2 δ I n − j 2 ≤ 0 } . n_\delta=\arg\min_{n\ge L_\delta-1}\left\{\sum_{j=0}^{L_\delta-1}\left\|F_{I_{n-j}}(x_{n-j}^\delta)-y_{I_{n-j}}^\delta\right\|^2-\tau^2\delta_{I_{n-j}}^2\le0\right\}. n δ = arg n ≥ L δ − 1 min { j = 0 ∑ L δ − 1 F I n − j ( x n − j δ ) − y I n − j δ 2 − τ 2 δ I n − j 2 ≤ 0 } .
Note that x n δ x_n^\delta x n δ is F n \mathcal{F}_n F n measurable, but in general F I n F_{I_n} F I n and y I n y_{I_n} y I n are not, since the filtration F n \mathcal{F}_n F n excludes the ( n + 1 ) (n+1) ( n + 1 ) -th batch I n I_n I n . This fact is used to calculate the expected values of the batch residual and the batch noise, which will be heavily used later on.
Lemma 2.1. For an F n \mathcal{F}_n F n -measurable x ∈ X x\in X x ∈ X , we have
E [ ∥ y I n δ − F I n ( x ) ∥ 2 ] = b p E [ ∥ y δ − F ( x ) ∥ 2 ] . \mathbb{E}\left[\left\|y_{I_n}^\delta-F_{I_n}(x)\right\|^2\right]=\frac{b}{p}\mathbb{E}\left[\left\|y^\delta-F(x)\right\|^2\right]. E [ y I n δ − F I n ( x ) 2 ] = p b E [ y δ − F ( x ) 2 ] . In particular, it holds
E [ δ I n 2 ] = b p δ 2 . \mathbb{E}\left[\delta_{I_n}^2\right]=\frac{b}{p}\delta^2. E [ δ I n 2 ] = p b δ 2 . Proof. We follow the proof of [32 Lemma 3.1] . Due to the F n \mathcal{F}_n F n -measurability of x x x , the random variable ∥ y I n δ − F I n ( x ) ∥ 2 \left\|y_{I_n}^\delta-F_{I_n}(x)\right\|^2 y I n δ − F I n ( x ) 2 only depends on the batches I 0 , … , I n I_0,\ldots,I_n I 0 , … , I n . This implies that the conditional expectation E [ ⋅ ∣ F n ] \mathbb{E}[\cdot\mid\mathcal{F}_n] E [ ⋅ ∣ F n ] , which averages over all possible I l I_l I l with l ≥ n l\ge n l ≥ n , corresponds only to the sum over all possible selections of I n I_n I n . Since P ( I n ) = 1 / ( p b ) \mathbb{P}(I_n)=1/\binom{p}{b} P ( I n ) = 1/ ( b p ) , it follows
E [ ∥ y I n δ − F I n ( x ) ∥ 2 ∣ F n ] = 1 ( p b ) ∑ I : ∣ I ∣ = b ∥ y I δ − F I ( x ) ∥ 2 \mathbb{E}\left[\left\|y_{I_n}^\delta-F_{I_n}(x)\right\|^2\mid\mathcal{F}_n\right]
=\frac{1}{\binom{p}{b}}\sum_{I:|I|=b}\left\|y_I^\delta-F_I(x)\right\|^2 E [ y I n δ − F I n ( x ) 2 ∣ F n ] = ( b p ) 1 I : ∣ I ∣ = b ∑ y I δ − F I ( x ) 2 = 1 ( p b ) ∑ I : ∣ I ∣ = b ∑ i ∈ I ∥ y i δ − F i ( x ) ∥ 2 =\frac{1}{\binom{p}{b}}\sum_{I:|I|=b}\sum_{i\in I}\left\|y_i^\delta-F_i(x)\right\|^2 = ( b p ) 1 I : ∣ I ∣ = b ∑ i ∈ I ∑ y i δ − F i ( x ) 2 = 1 ( p b ) ∑ i = 1 p ∑ I : ∣ I ∣ = b , i ∈ I ∥ y i δ − F i ( x ) ∥ 2 =\frac{1}{\binom{p}{b}}\sum_{i=1}^{p}\sum_{I:|I|=b,\ i\in I}\left\|y_i^\delta-F_i(x)\right\|^2 = ( b p ) 1 i = 1 ∑ p I : ∣ I ∣ = b , i ∈ I ∑ y i δ − F i ( x ) 2 = ( p − 1 b − 1 ) ( p b ) ∑ i = 1 p ∥ y i δ − F i ( x ) ∥ 2 = b p ∥ y δ − F ( x ) ∥ 2 . =\frac{\binom{p-1}{b-1}}{\binom{p}{b}}\sum_{i=1}^{p}\left\|y_i^\delta-F_i(x)\right\|^2
=\frac{b}{p}\left\|y^\delta-F(x)\right\|^2. = ( b p ) ( b − 1 p − 1 ) i = 1 ∑ p y i δ − F i ( x ) 2 = p b y δ − F ( x ) 2 .
In the third equation we swap the addends and the fourth equation follows from a combinatorial argument: in creating a subset I I I containing a fixed i i i , there are ( p − 1 b − 1 ) \binom{p-1}{b-1} ( b − 1 p − 1 ) ways to picks the remaining b − 1 b-1 b − 1 entries from the remaining p − 1 p-1 p − 1 equations. Applying the expectation on both sides and using the tower property leads us to the first result. The second result follows analogously by replacing F I n ( x ) F_{I_n}(x) F I n ( x ) with y I n y_{I_n} y I n .
Remark 2.1. Applying Lemma 2.1 to single-valued batches I n I_n I n yields E [ δ I n 2 ] = 1 p δ 2 \mathbb{E}\left[\delta_{I_n}^2\right]=\frac{1}{p}\delta^2 E [ δ I n 2 ] = p 1 δ 2 and hence for b b b independent single-valued batches it holds E [ δ I n ( 1 ) 2 + … + δ I n ( b ) 2 ] = b p δ 2 \mathbb{E}\left[\delta_{I_n^{(1)}}^2+\ldots+\delta_{I_n^{(b)}}^2\right]=\frac{b}{p}\delta^2 E [ δ I n ( 1 ) 2 + … + δ I n ( b ) 2 ] = p b δ 2 . This argumentation implies that the result of Lemma 2.1 and therefore the rest of the paper can be generalized to the setting of choosing the batches with replacement.
To prove convergence we use the following standard Assumptions.
Assumption 2.1. Let the following conditions hold:
(i) There is a ρ > 0 \rho>0 ρ > 0 such that problem (1) has a solution in B ρ ( x 0 ) B_\rho(x_0) B ρ ( x 0 ) with B 2 ρ ( x 0 ) ⊆ D ( F ) B_{2\rho}(x_0)\subseteq D(F) B 2 ρ ( x 0 ) ⊆ D ( F ) .
(ii) Each operator F i : D ( F ) ⊂ X → Y i F_i:D(F)\subset X\to Y_i F i : D ( F ) ⊂ X → Y i has a continuous Fréchet derivative F i ′ F_i' F i ′ on B 2 ρ ( x 0 ) ⊆ X B_{2\rho}(x_0)\subseteq X B 2 ρ ( x 0 ) ⊆ X .
(iii) Each F i F_i F i is properly scaled, so that ∥ F i ′ ( x ) ∥ ≤ 1 / p \lVert F_i'(x)\rVert\leq1/\sqrt{p} ∥ F i ′ ( x )∥ ≤ 1/ p for all x ∈ B 2 ρ ( x 0 ) x\in B_{2\rho}(x_0) x ∈ B 2 ρ ( x 0 ) .
(iv) There exists an η ∈ [ 0 , 1 / 2 ) \eta\in[0,1/2) η ∈ [ 0 , 1/2 ) , such that the tangential cone condition
∥ F i ( x ) − F i ( x ˉ ) − F i ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ η ∥ F i ( x ) − F i ( x ˉ ) ∥ \lVert F_i(x)-F_i(\bar{x})-F_i'(\bar{x})(x-\bar{x})\rVert\leq\eta\lVert F_i(x)-F_i(\bar{x})\rVert ∥ F i ( x ) − F i ( x ˉ ) − F i ′ ( x ˉ ) ( x − x ˉ )∥ ≤ η ∥ F i ( x ) − F i ( x ˉ )∥ holds for all x , x ˉ ∈ B 2 ρ ( x 0 ) ⊆ D ( F ) x,\bar{x}\in B_{2\rho}(x_0)\subseteq D(F) x , x ˉ ∈ B 2 ρ ( x 0 ) ⊆ D ( F ) and for all i = 1 , … , p i=1,\ldots,p i = 1 , … , p .
Assumption 2.1(i) and (iv) guarantees the existence of the unique x 0 x_0 x 0 -minimum norm solution x † ∈ B ρ ( x 0 ) x^\dagger\in B_\rho(x_0) x † ∈ B ρ ( x 0 ) , which is characterized by x † − x 0 ∈ N ( F ′ ( x † ) ) ⊥ x^\dagger-x_0\in N(F'(x^\dagger))^\perp x † − x 0 ∈ N ( F ′ ( x † ) ) ⊥ [35 Proposition 2.1] . Here N N N denotes the null space of an operator. Moreover, Assumption 2.1(iv) is a rather strong condition since the nonlinearity condition is imposed to every function F i F_i F i instead to the entire system via F F F . Due to the definition of norms on product spaces, it implies that
∥ F I ( x ) − F I ( x ˉ ) − F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ η ∥ F I ( x ) − F I ( x ˉ ) ∥ (13) \lVert F_I(x)-F_I(\bar{x})-F_I'(\bar{x})(x-\bar{x})\rVert\leq\eta\lVert F_I(x)-F_I(\bar{x})\rVert \tag*{(13)} ∥ F I ( x ) − F I ( x ˉ ) − F I ′ ( x ˉ ) ( x − x ˉ )∥ ≤ η ∥ F I ( x ) − F I ( x ˉ )∥ (13)
for all x , x ˉ ∈ B 2 ρ ( x 0 ) ⊆ D ( F ) x,\bar{x}\in B_{2\rho}(x_0)\subseteq D(F) x , x ˉ ∈ B 2 ρ ( x 0 ) ⊆ D ( F ) and for every subset I ⊆ { 1 , … , p } I\subseteq\{1,\ldots,p\} I ⊆ { 1 , … , p } . Accordingly, with I = { 1 , … , p } I=\{1,\ldots,p\} I = { 1 , … , p } , the nonlinearity condition also holds for the overall operator F : X → Y F:X\to Y F : X → Y , i.e.
∥ F ( x ) − F ( x ˉ ) − F ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ η ∥ F ( x ) − F ( x ˉ ) ∥ . (14) \lVert F(x)-F(\bar{x})-F'(\bar{x})(x-\bar{x})\rVert\leq\eta\lVert F(x)-F(\bar{x})\rVert. \tag*{(14)} ∥ F ( x ) − F ( x ˉ ) − F ′ ( x ˉ ) ( x − x ˉ )∥ ≤ η ∥ F ( x ) − F ( x ˉ )∥ . (14)
Obviously, the reverse of the above implications is not true. The following bound will be useful.
Lemma 2.2. Let Assumption 2.1(iv) hold and I ⊆ { 1 , … , p } I\subseteq\{1,\ldots,p\} I ⊆ { 1 , … , p } . Then
1 1 + η ∥ F I ′ ( x ) ( x − x ˉ ) ∥ ≤ ∥ F I ( x ) − F I ( x ˉ ) ∥ ≤ 1 1 − η ∥ F I ′ ( x ) ( x − x ˉ ) ∥ (15) \frac{1}{1+\eta}\lVert F_I'(x)(x-\bar{x})\rVert\leq\lVert F_I(x)-F_I(\bar{x})\rVert\leq\frac{1}{1-\eta}\lVert F_I'(x)(x-\bar{x})\rVert \tag*{(15)} 1 + η 1 ∥ F I ′ ( x ) ( x − x ˉ )∥ ≤ ∥ F I ( x ) − F I ( x ˉ )∥ ≤ 1 − η 1 ∥ F I ′ ( x ) ( x − x ˉ )∥ (15) for all x , x ˉ ∈ B 2 ρ ( x 0 ) x,\bar{x}\in B_{2\rho}(x_0) x , x ˉ ∈ B 2 ρ ( x 0 ) .
Proof. Using equation (14) and the triangle inequality ∥ a ∥ − ∥ b ∥ ≤ ∥ a − b ∥ \lVert a\rVert-\lVert b\rVert\leq\lVert a-b\rVert ∥ a ∥ − ∥ b ∥ ≤ ∥ a − b ∥ for a , b ∈ Y a,b\in Y a , b ∈ Y , we get
η ∥ F I ( x ) − F I ( x ˉ ) ∥ ≥ ∥ F I ( x ) − F I ( x ˉ ) − F I ′ ( x ˉ ) ( x − x ˉ ) ∥ = ∥ F I ′ ( x ˉ ) ( x − x ˉ ) − ( F I ( x ) − F I ( x ˉ ) ) ∥ ≥ ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ − ∥ F I ( x ) − F I ( x ˉ ) ∥ , \eta\lVert F_I(x)-F_I(\bar{x})\rVert\geq\lVert F_I(x)-F_I(\bar{x})-F_I'(\bar{x})(x-\bar{x})\rVert
=\lVert F_I'(\bar{x})(x-\bar{x})-(F_I(x)-F_I(\bar{x}))\rVert
\geq\lVert F_I'(\bar{x})(x-\bar{x})\rVert-\lVert F_I(x)-F_I(\bar{x})\rVert, η ∥ F I ( x ) − F I ( x ˉ )∥ ≥ ∥ F I ( x ) − F I ( x ˉ ) − F I ′ ( x ˉ ) ( x − x ˉ )∥ = ∥ F I ′ ( x ˉ ) ( x − x ˉ ) − ( F I ( x ) − F I ( x ˉ ))∥ ≥ ∥ F I ′ ( x ˉ ) ( x − x ˉ )∥ − ∥ F I ( x ) − F I ( x ˉ )∥ ,
and hence,
∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ ( 1 + η ) ∥ F I ( x ) − F I ( x ˉ ) ∥ \left\|F'_I(\bar{x})(x-\bar{x})\right\| \le(1+\eta)\left\|F_I(x)-F_I(\bar{x})\right\| ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ ( 1 + η ) ∥ F I ( x ) − F I ( x ˉ ) ∥
1 1 + η ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ ∥ F I ( x ) − F I ( x ˉ ) ∥ . \frac{1}{1+\eta}\left\|F'_I(\bar{x})(x-\bar{x})\right\| \le\left\|F_I(x)-F_I(\bar{x})\right\|. 1 + η 1 ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ ∥ F I ( x ) − F I ( x ˉ ) ∥ .
which is the first inequality of (15) . Similarly it follows
∥ F I ( x ) − F I ( x ˉ ) ∥ − ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ η ∥ F I ( x ) − F I ( x ˉ ) ∥ \left\|F_I(x)-F_I(\bar{x})\right\|-\left\|F'_I(\bar{x})(x-\bar{x})\right\| \le\eta\left\|F_I(x)-F_I(\bar{x})\right\| ∥ F I ( x ) − F I ( x ˉ ) ∥ − ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ≤ η ∥ F I ( x ) − F I ( x ˉ ) ∥
( 1 − η ) ∥ F I ( x ) − F I ( x ˉ ) ∥ ≤ ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ (1-\eta)\left\|F_I(x)-F_I(\bar{x})\right\| \le\left\|F'_I(\bar{x})(x-\bar{x})\right\| ( 1 − η ) ∥ F I ( x ) − F I ( x ˉ ) ∥ ≤ ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥
∥ F I ( x ) − F I ( x ˉ ) ∥ ≤ 1 1 − η ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ , \left\|F_I(x)-F_I(\bar{x})\right\| \le\frac{1}{1-\eta}\left\|F'_I(\bar{x})(x-\bar{x})\right\|, ∥ F I ( x ) − F I ( x ˉ ) ∥ ≤ 1 − η 1 ∥ F I ′ ( x ˉ ) ( x − x ˉ ) ∥ ,
which leads to the second inequality of (15) .
The following result shows an error bound similar to that of Landweber iteration for nonlinear inverse problems derived in [18 Proposition 2.2] .
Lemma 2.3. Let Assumption 2.1 hold and x ∗ ∈ B 2 ρ ( x 0 ) x_*\in B_{2\rho}(x_0) x ∗ ∈ B 2 ρ ( x 0 ) be an arbitrary solution of equation (1) . Consider the iteration { x n δ } ⊆ X \{x_n^\delta\}\subseteq X { x n δ } ⊆ X generated by (8) with a fixed selection of batches ( I 0 , I 1 , … ) ∈ Ω (I_0,I_1,\ldots)\in\Omega ( I 0 , I 1 , … ) ∈ Ω . Then for all iterates that satisfy x n δ ∈ B 2 ρ ( x 0 ) x_n^\delta\in B_{2\rho}(x_0) x n δ ∈ B 2 ρ ( x 0 ) , it holds
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ ω n p b ∥ y I n δ − F I n ( x n δ ) ∥ ( ( 2 ( 1 + η ) δ I n − ( 1 − 2 η ) ∥ y I n δ − F I n ( x n δ ) ∥ ) ) . \left\|x_{n+1}^\delta-x_*\right\|^2-\left\|x_n^\delta-x_*\right\|^2
\le\omega_n\frac{p}{b}\left\|y_{I_n}^\delta-F_{I_n}(x_n^\delta)\right\|\left((2(1+\eta)\delta_{I_n}-(1-2\eta)\left\|y_{I_n}^\delta-F_{I_n}(x_n^\delta)\right\|)\right). x n + 1 δ − x ∗ 2 − x n δ − x ∗ 2 ≤ ω n b p y I n δ − F I n ( x n δ ) ( ( 2 ( 1 + η ) δ I n − ( 1 − 2 η ) y I n δ − F I n ( x n δ ) ) ) .
Proof. We follow the same computations for the nonlinear Landweber iteration found in the classical paper of [18 ] , which also can also be read in [35 ] . We start with computing
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 = ∥ x n + 1 δ ∥ 2 − ∥ x n δ ∥ 2 − 2 ⟨ x n + 1 δ , x ∗ ⟩ + 2 ⟨ x n δ , x ∗ ⟩ = ∥ x n + 1 δ − x n δ ∥ 2 + 2 ⟨ x n + 1 δ , x n δ ⟩ − 2 ∥ x n δ ∥ 2 − 2 ⟨ x n + 1 δ , x ∗ ⟩ + 2 ⟨ x n δ , x ∗ ⟩ = ∥ x n + 1 δ − x n δ ∥ 2 + 2 ⟨ x n + 1 δ − x n δ , x n δ − x ∗ ⟩ . \begin{aligned}
\left\|x_{n+1}^\delta-x_*\right\|^2-\left\|x_n^\delta-x_*\right\|^2
&=\left\|x_{n+1}^\delta\right\|^2-\left\|x_n^\delta\right\|^2-2\langle x_{n+1}^\delta,x_*\rangle+2\langle x_n^\delta,x_*\rangle\\
&=\left\|x_{n+1}^\delta-x_n^\delta\right\|^2+2\langle x_{n+1}^\delta,x_n^\delta\rangle-2\left\|x_n^\delta\right\|^2-2\langle x_{n+1}^\delta,x_*\rangle+2\langle x_n^\delta,x_*\rangle\\
&=\left\|x_{n+1}^\delta-x_n^\delta\right\|^2+2\langle x_{n+1}^\delta-x_n^\delta,x_n^\delta-x_*\rangle.
\end{aligned} x n + 1 δ − x ∗ 2 − x n δ − x ∗ 2 = x n + 1 δ 2 − x n δ 2 − 2 ⟨ x n + 1 δ , x ∗ ⟩ + 2 ⟨ x n δ , x ∗ ⟩ = x n + 1 δ − x n δ 2 + 2 ⟨ x n + 1 δ , x n δ ⟩ − 2 x n δ 2 − 2 ⟨ x n + 1 δ , x ∗ ⟩ + 2 ⟨ x n δ , x ∗ ⟩ = x n + 1 δ − x n δ 2 + 2 ⟨ x n + 1 δ − x n δ , x n δ − x ∗ ⟩ .
Inserting the definition of x n + 1 δ x_{n+1}^\delta x n + 1 δ and using ω n 2 = ω n \omega_n^2=\omega_n ω n 2 = ω n , we obtain
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 = ω n ( p b ) 2 ∥ F I n ′ ( x n δ ) ∗ ( y I n δ − F I n ( x n δ ) ) ∥ 2 + 2 ω n p b ⟨ y I n δ − F I n ( x n δ ) , F I n ′ ( x n δ ) ( x n δ − x ∗ ) ⟩ . \begin{aligned}
\left\|x_{n+1}^\delta-x_*\right\|^2-\left\|x_n^\delta-x_*\right\|^2
&=\omega_n\left(\frac{p}{b}\right)^2\left\|F'_{I_n}(x_n^\delta)^*(y_{I_n}^\delta-F_{I_n}(x_n^\delta))\right\|^2\\
&\quad+2\omega_n\frac{p}{b}\left\langle y_{I_n}^\delta-F_{I_n}(x_n^\delta),F'_{I_n}(x_n^\delta)(x_n^\delta-x_*)\right\rangle.
\end{aligned} x n + 1 δ − x ∗ 2 − x n δ − x ∗ 2 = ω n ( b p ) 2 F I n ′ ( x n δ ) ∗ ( y I n δ − F I n ( x n δ )) 2 + 2 ω n b p ⟨ y I n δ − F I n ( x n δ ) , F I n ′ ( x n δ ) ( x n δ − x ∗ ) ⟩ .
To simplify the last expression and obtain a more useful estimate, we use the decomposition
F I n ′ ( x n δ ) ( x n δ − x ∗ ) = ( y I n δ − y I n ) + ( F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ) − ( y I n δ − F I n ( x n δ ) ) . F'_{I_n}(x_n^\delta)(x_n^\delta-x_*)=(y_{I_n}^\delta-y_{I_n})+\left(F_{I_n}(x_*)-F_{I_n}(x_n^\delta)-F'_{I_n}(x_n^\delta)(x_*-x_n^\delta)\right)-(y_{I_n}^\delta-F_{I_n}(x_n^\delta)). F I n ′ ( x n δ ) ( x n δ − x ∗ ) = ( y I n δ − y I n ) + ( F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ) − ( y I n δ − F I n ( x n δ )) .
Furthermore, by Assumption 2.1(iii), it follows that
∥ F I n ′ ( x n δ ) ∗ ∥ 2 = ∥ F I n ′ ( x n δ ) ∥ 2 = ∑ i ∈ I n ∥ F i ′ ( x n δ ) ∥ 2 ≤ b p . \left\|F'_{I_n}(x_n^\delta)^*\right\|^2=\left\|F'_{I_n}(x_n^\delta)\right\|^2=\sum_{i\in I_n}\left\|F'_i(x_n^\delta)\right\|^2\le\frac{b}{p}. F I n ′ ( x n δ ) ∗ 2 = F I n ′ ( x n δ ) 2 = i ∈ I n ∑ F i ′ ( x n δ ) 2 ≤ p b .
Inserting this, we find
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ ω n ( p b ) ∥ y I n δ − F I n ( x n δ ) ∥ 2 + 2 ω n ( p b ) ⟨ y I n δ − F I n ( x n δ ) , y I n δ − y I n ⟩ + 2 ω n ( p b ) ⟨ y I n δ − F I n ( x n δ ) , F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ⟩ − 2 ω n ( p b ) ⟨ y I n δ − F I n ( x n δ ) , y I n δ − F I n ( x n δ ) ⟩ = ω n p b ( 2 ⟨ y I n δ − F I n ( x n δ ) , y I n δ − y I n ⟩ + 2 ⟨ y I n δ − F I n ( x n δ ) , F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ⟩ − ∥ y I n δ − F I n ( x n δ ) ∥ 2 ) . \begin{aligned}
\left\|x_{n+1}^{\delta}-x_*\right\|^2-\left\|x_n^{\delta}-x_*\right\|^2
&\leq\omega_n\left(\frac{p}{b}\right)\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|^2 \\
&\quad+2\omega_n\left(\frac{p}{b}\right)\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),y_{I_n}^{\delta}-y_{I_n}\right\rangle\\
&\quad+2\omega_n\left(\frac{p}{b}\right)\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),F_{I_n}(x_*)-F_{I_n}(x_n^{\delta})-F_{I_n}'(x_n^{\delta})(x_*-x_n^{\delta})\right\rangle\\
&\quad-2\omega_n\left(\frac{p}{b}\right)\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\rangle\\
&=\omega_n\frac{p}{b}\left(2\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),y_{I_n}^{\delta}-y_{I_n}\right\rangle\right.\\
&\qquad\left.+2\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),F_{I_n}(x_*)-F_{I_n}(x_n^{\delta})-F_{I_n}'(x_n^{\delta})(x_*-x_n^{\delta})\right\rangle\right.\\
&\qquad\left.-\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|^2\right).
\end{aligned} x n + 1 δ − x ∗ 2 − x n δ − x ∗ 2 ≤ ω n ( b p ) y I n δ − F I n ( x n δ ) 2 + 2 ω n ( b p ) ⟨ y I n δ − F I n ( x n δ ) , y I n δ − y I n ⟩ + 2 ω n ( b p ) ⟨ y I n δ − F I n ( x n δ ) , F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ⟩ − 2 ω n ( b p ) ⟨ y I n δ − F I n ( x n δ ) , y I n δ − F I n ( x n δ ) ⟩ = ω n b p ( 2 ⟨ y I n δ − F I n ( x n δ ) , y I n δ − y I n ⟩ + 2 ⟨ y I n δ − F I n ( x n δ ) , F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ⟩ − y I n δ − F I n ( x n δ ) 2 ) .
By the Cauchy-Schwarz inequality, we have
2 ⟨ y I n δ − F I n ( x n δ ) , y I n δ − y I n ⟩ ≤ 2 ∥ y I n δ − F I n ( x n δ ) ∥ ∥ y I n δ − y I n ∥ . 2\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),y_{I_n}^{\delta}-y_{I_n}\right\rangle
\leq2\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\left\|y_{I_n}^{\delta}-y_{I_n}\right\|. 2 ⟨ y I n δ − F I n ( x n δ ) , y I n δ − y I n ⟩ ≤ 2 y I n δ − F I n ( x n δ ) y I n δ − y I n .
Also, again by Cauchy-Schwarz, (13) due to x n δ ∈ B 2 ρ ( x 0 ) x_n^{\delta}\in B_{2\rho}(x_0) x n δ ∈ B 2 ρ ( x 0 ) and Assumption 2.1(iv), we find
2 ⟨ y I n δ − F I n ( x n δ ) , F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ⟩ ≤ 2 ∥ y I n δ − F I n ( x n δ ) ∥ ∥ F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ∥ ≤ 2 η ∥ y I n δ − F I n ( x n δ ) ∥ ∥ F I n ( x ∗ ) − F I n ( x n δ ) ∥ ≤ 2 η ∥ y I n δ − F I n ( x n δ ) ∥ ∥ y I n δ − y I n ∥ + 2 η ∥ y I n δ − F I n ( x n δ ) ∥ 2 . \begin{aligned}
&2\left\langle y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta}),F_{I_n}(x_*)-F_{I_n}(x_n^{\delta})-F_{I_n}'(x_n^{\delta})(x_*-x_n^{\delta})\right\rangle\\
&\leq2\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\left\|F_{I_n}(x_*)-F_{I_n}(x_n^{\delta})-F_{I_n}'(x_n^{\delta})(x_*-x_n^{\delta})\right\|\\
&\leq2\eta\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\left\|F_{I_n}(x_*)-F_{I_n}(x_n^{\delta})\right\|\\
&\leq2\eta\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\left\|y_{I_n}^{\delta}-y_{I_n}\right\|+2\eta\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|^2.
\end{aligned} 2 ⟨ y I n δ − F I n ( x n δ ) , F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ⟩ ≤ 2 y I n δ − F I n ( x n δ ) F I n ( x ∗ ) − F I n ( x n δ ) − F I n ′ ( x n δ ) ( x ∗ − x n δ ) ≤ 2 η y I n δ − F I n ( x n δ ) F I n ( x ∗ ) − F I n ( x n δ ) ≤ 2 η y I n δ − F I n ( x n δ ) y I n δ − y I n + 2 η y I n δ − F I n ( x n δ ) 2 .
This leads us to
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ ω n ( p b ) ( 2 ∥ y I n δ − F I n ( x n δ ) ∥ ∥ y I n δ − y I n ∥ + 2 η ∥ y I n δ − F I n ( x n δ ) ∥ ∥ y I n δ − y I n ∥ + 2 η ∥ y I n δ − F I n ( x n δ ) ∥ 2 − ∥ y I n δ − F I n ( x n δ ) ∥ 2 ) = ω n ( p b ) ( 2 ( 1 + η ) ∥ y I n δ − y I n ∥ ⏟ = δ I n ∥ y I n δ − F I n ( x n δ ) ∥ − ( 1 − 2 η ) ∥ y I n δ − F I n ( x n δ ) ∥ 2 ) , \begin{aligned}
\left\|x_{n+1}^{\delta}-x_*\right\|^2-\left\|x_n^{\delta}-x_*\right\|^2
&\leq\omega_n\left(\frac{p}{b}\right)\left(2\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\left\|y_{I_n}^{\delta}-y_{I_n}\right\|\right.\\
&\qquad+2\eta\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\left\|y_{I_n}^{\delta}-y_{I_n}\right\|\\
&\qquad\left.+2\eta\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|^2-\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|^2\right)\\
&=\omega_n\left(\frac{p}{b}\right)\left(2(1+\eta)\underbrace{\left\|y_{I_n}^{\delta}-y_{I_n}\right\|}_{=\delta_{I_n}}\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|\right.\\
&\qquad\left.-(1-2\eta)\left\|y_{I_n}^{\delta}-F_{I_n}(x_n^{\delta})\right\|^2\right),
\end{aligned} x n + 1 δ − x ∗ 2 − x n δ − x ∗ 2 ≤ ω n ( b p ) ( 2 y I n δ − F I n ( x n δ ) y I n δ − y I n + 2 η y I n δ − F I n ( x n δ ) y I n δ − y I n + 2 η y I n δ − F I n ( x n δ ) 2 − y I n δ − F I n ( x n δ ) 2 ) = ω n ( b p ) 2 ( 1 + η ) = δ I n y I n δ − y I n y I n δ − F I n ( x n δ ) − ( 1 − 2 η ) y I n δ − F I n ( x n δ ) 2 ) ,
which is the desired result.
Convergence for exact data
Next, we show the convergence of method (8) with exact data. In this instance, we remove the superscript δ \delta δ to denote exact data and iterates. Thus { x n } \{x_n\} { x n } denotes the corresponding iterative sequence. We show that { x n } \{x_n\} { x n } is a Cauchy sequence in L 2 ( Ω , X ) L^2(\Omega,X) L 2 ( Ω , X ) .
Theorem 2.1. Let Assumption 2.1 hold, y ∈ Y y\in Y y ∈ Y be the exact data and { x n } \{x_n\} { x n } the sequence of random variables on the probability space (12) generated by (8) with exact data y = y δ y=y^{\delta} y = y δ . Then there exists a random variable x ∗ ∈ L 2 ( Ω , X ) x^*\in L^2(\Omega,X) x ∗ ∈ L 2 ( Ω , X ) , such that x ∗ ∈ B 2 ρ ( x 0 ) x^*\in B_{2\rho}(x_0) x ∗ ∈ B 2 ρ ( x 0 ) solves problem (1) almost everywhere and { x n } \{x_n\} { x n } converges in expectation to x ∗ x^* x ∗ , i.e.
E [ ∥ x n − x ∗ ∥ ] ⟶ 0 as n ⟶ ∞ . \mathbb{E}\left[\left\|x_n-x^*\right\|\right]\longrightarrow0\qquad\text{as }n\longrightarrow\infty. E [ ∥ x n − x ∗ ∥ ] ⟶ 0 as n ⟶ ∞. If N ( F ′ ( x † ) ) ⊂ N ( F ′ ( x ) ) \mathcal{N}(F'(x^\dagger))\subset\mathcal{N}(F'(x)) N ( F ′ ( x † )) ⊂ N ( F ′ ( x )) for all x ∈ B ρ ( x † ) x\in B_\rho(x^\dagger) x ∈ B ρ ( x † ) , then the sequence { x n } \{x_n\} { x n } converges in expectation to the unique x 0 x_0 x 0 -minimum-norm solution x † x^\dagger x † of problem (1) :
E [ ∥ x n − x † ∥ ] ⟶ 0 as n ⟶ ∞ . \mathbb{E}\left[\left\|x_n-x^\dagger\right\|\right]\longrightarrow0\qquad\text{as }n\longrightarrow\infty. E [ x n − x † ] ⟶ 0 as n ⟶ ∞.
Remark 2.2. Note that problem (1) can have multiple solutions and the random variable x ∗ x^{*} x ∗ of Theorem 2.1 is generally not constant. I.e. for the same starting value x 0 x_{0} x 0 the method (8) can converge to different solutions depending on the chosen batches within the iteration. This phenomenon only appears in the non-linear case, since for a linear operator F F F it holds N ( F ′ ( x † ) ) = N ( F ′ ( x ) ) \mathcal{N}(F'(x^{\dagger}))=\mathcal{N}(F'(x)) N ( F ′ ( x † )) = N ( F ′ ( x )) for all x ∈ B ρ ( x † ) x \in\mathcal{B}_{\rho}(x^{\dagger}) x ∈ B ρ ( x † ) and hence the method converges to the unique x 0 x_{0} x 0 -minimum-norm solution.
Proof of Theorem 2.1. Let x ∗ ∈ B ρ ( x 0 ) x_{*} \in\mathcal{B}_{\rho}(x_{0}) x ∗ ∈ B ρ ( x 0 ) be an arbitrary solution of problem (1) according to Assumption 2.1 (i). First we prove point-wise monotonicity of { ∥ x n − x ∗ ∥ } \{\lVert x_{n}-x_{*}\rVert\} {∥ x n − x ∗ ∥} . For that, we fix an infinite selection of batches Λ = ( I 0 , I 1 , … ) ∈ Ω \Lambda=(I_{0},I_{1},\ldots)\in\Omega Λ = ( I 0 , I 1 , … ) ∈ Ω and denote the corresponding iterates as x ^ n : = x n ( Λ ) ∈ X \hat{x}_{n}:=x_{n}(\Lambda)\in X x ^ n := x n ( Λ ) ∈ X . Consequently, Lemma 2.3 implies for all x ^ n ∈ B 2 ρ ( x 0 ) \hat{x}_{n}\in\mathcal{B}_{2\rho}(x_{0}) x ^ n ∈ B 2 ρ ( x 0 ) that
∥ x ^ n + 1 − x ∗ ∥ 2 − ∥ x ^ n − x ∗ ∥ 2 ≤ − ( 1 − 2 η ) p b ∥ y I n − F I n ( x ^ n ) ∥ 2 ≤ 0. (16) \lVert\hat{x}_{n+1}-x_{*}\rVert^{2}-\lVert\hat{x}_{n}-x_{*}\rVert^{2}\leq-(1-2\eta)\frac{p}{b}\lVert y_{I_{n}}-F_{I_{n}}(\hat{x}_{n})\rVert^{2}\leq0. \tag*{(16)} ∥ x ^ n + 1 − x ∗ ∥ 2 − ∥ x ^ n − x ∗ ∥ 2 ≤ − ( 1 − 2 η ) b p ∥ y I n − F I n ( x ^ n ) ∥ 2 ≤ 0. (16)
Here we used that δ I n = 0 \delta_{I_{n}}=0 δ I n = 0 and ω n = 1 \omega_{n}=1 ω n = 1 in the exact data case. Inductively, we get ∥ x ^ n − x ∗ ∥ 2 ≤ ∥ x 0 − x ∗ ∥ 2 < ρ 2 \lVert\hat{x}_{n}-x_{*}\rVert^{2}\leq\lVert x_{0}-x_{*}\rVert^{2}<\rho^{2} ∥ x ^ n − x ∗ ∥ 2 ≤ ∥ x 0 − x ∗ ∥ 2 < ρ 2 and therefore x ^ n ∈ B ρ ( x ∗ ) ⊆ B 2 ρ ( x 0 ) \hat{x}_{n}\in\mathcal{B}_{\rho}(x_{*})\subseteq\mathcal{B}_{2\rho}(x_{0}) x ^ n ∈ B ρ ( x ∗ ) ⊆ B 2 ρ ( x 0 ) for all n ∈ N n\in\mathbb{N} n ∈ N . Hence the inequality (16) holds for all n ∈ N 0 n\in\mathbb{N}_{0} n ∈ N 0 . And since Λ ∈ Ω \Lambda\in\Omega Λ ∈ Ω was chosen arbitrarily the inequality (16) holds point-wise for x n x_{n} x n and by taking expectations, we obtain
E [ ∥ x n + 1 − x ∗ ∥ 2 ] − E [ ∥ x n − x ∗ ∥ 2 ] ≤ − ( 1 − 2 η ) p b E [ ∥ y I n − F I n ( x n ) ∥ 2 ] = − c E [ ∥ y − F ( x n ) ∥ 2 ] , (17) \begin{aligned}
\mathbb{E}\left[\lVert x_{n+1}-x_{*}\rVert^{2}\right]-\mathbb{E}\left[\lVert x_{n}-x_{*}\rVert^{2}\right]\leq-(1-2\eta)\frac{p}{b}\mathbb{E}\left[\lVert y_{I_{n}}-F_{I_{n}}(x_{n})\rVert^{2}\right] \\
&=-c\mathbb{E}\left[\lVert y-F(x_{n})\rVert^{2}\right], \tag*{(17)}
\end{aligned} E [ ∥ x n + 1 − x ∗ ∥ 2 ] − E [ ∥ x n − x ∗ ∥ 2 ] ≤ − ( 1 − 2 η ) b p E [ ∥ y I n − F I n ( x n ) ∥ 2 ] = − c E [ ∥ y − F ( x n ) ∥ 2 ] , (17)
where we used the F n \mathcal{F}_{n} F n -measurability of x n x_{n} x n and Lemma 2.1, setting c : = ( 1 − 2 η ) > 0 c:=(1-2\eta)>0 c := ( 1 − 2 η ) > 0 . Thus, the sequence { E [ ∥ x n − x ∗ ∥ 2 ] } \{\mathbb{E}[\lVert x_{n}-x_{*}\rVert^{2}]\} { E [∥ x n − x ∗ ∥ 2 ]} is monotonically decreasing and hence converges to some number α ≥ 0 \alpha\geq0 α ≥ 0 . Consequently, it also follows from (17) that
lim n → ∞ E [ ∥ y − F ( x n ) ∥ 2 ] = 0. (18) \lim_{n\to\infty}\mathbb{E}\left[\lVert y-F(x_{n})\rVert^{2}\right]=0. \tag*{(18)} n → ∞ lim E [ ∥ y − F ( x n ) ∥ 2 ] = 0. (18)
In the following part we use the same method done in [18 ] . At this point, we need to show that the sequence { x n } \{x_{n}\} { x n } is a Cauchy sequence in L 2 ( Ω , X ) L^{2}(\Omega,X) L 2 ( Ω , X ) . First note that x n ∈ L 2 ( Ω , X ) x_{n}\in L^{2}(\Omega,X) x n ∈ L 2 ( Ω , X ) due to the above calculations. Now for every j ≥ n j\geq n j ≥ n , we choose l ∈ N l\in\mathbb{N} l ∈ N with j ≥ l ≥ n j\geq l\geq n j ≥ l ≥ n such that
E [ ∥ y − F ( x l ) ∥ 2 ] ≤ E [ ∥ y − F ( x i ) ∥ 2 ] for all n ≤ i ≤ j . (19) \mathbb{E}\left[\lVert y-F(x_{l})\rVert^{2}\right]\leq\mathbb{E}\left[\lVert y-F(x_{i})\rVert^{2}\right]\qquad\text{for all }n\leq i\leq j. \tag*{(19)} E [ ∥ y − F ( x l ) ∥ 2 ] ≤ E [ ∥ y − F ( x i ) ∥ 2 ] for all n ≤ i ≤ j . (19)
Let e n : = x n − x ∗ e_{n}:=x_{n}-x_{*} e n := x n − x ∗ . Using the fact that E [ ∥ ⋅ ∥ 2 ] 1 / 2 \mathbb{E}[\lVert\cdot\rVert^{2}]^{1/2} E [∥ ⋅ ∥ 2 ] 1/2 is a norm [29 ] , we get
E [ ∥ e j − e n ∥ 2 ] 1 / 2 ≤ E [ ∥ e j − e l ∥ 2 ] 1 / 2 + E [ ∥ e l − e n ∥ 2 ] 1 / 2 . (20) \mathbb{E}\left[\lVert e_{j}-e_{n}\rVert^{2}\right]^{1/2}\leq\mathbb{E}\left[\lVert e_{j}-e_{l}\rVert^{2}\right]^{1/2}+\mathbb{E}\left[\lVert e_{l}-e_{n}\rVert^{2}\right]^{1/2}. \tag*{(20)} E [ ∥ e j − e n ∥ 2 ] 1/2 ≤ E [ ∥ e j − e l ∥ 2 ] 1/2 + E [ ∥ e l − e n ∥ 2 ] 1/2 . (20)
Also in terms of expectation, based on the polarization identity, we have the identities
E [ ∥ e j − e l ∥ 2 ] = 2 E [ ⟨ e l − e j , e l ⟩ ] + E [ ∥ e j ∥ 2 ] − E [ ∥ e l ∥ 2 ] , \mathbb{E}\left[\lVert e_{j}-e_{l}\rVert^{2}\right]=2\mathbb{E}[\langle e_{l}-e_{j},e_{l}\rangle]+\mathbb{E}\left[\lVert e_{j}\rVert^{2}\right]-\mathbb{E}\left[\lVert e_{l}\rVert^{2}\right], E [ ∥ e j − e l ∥ 2 ] = 2 E [⟨ e l − e j , e l ⟩] + E [ ∥ e j ∥ 2 ] − E [ ∥ e l ∥ 2 ] ,
E [ ∥ e l − e n ∥ 2 ] = 2 E [ ⟨ e l − e n , e l ⟩ ] + E [ ∥ e n ∥ 2 ] − E [ ∥ e l ∥ 2 ] . (21) \mathbb{E}\left[\lVert e_{l}-e_{n}\rVert^{2}\right]=2\mathbb{E}[\langle e_{l}-e_{n},e_{l}\rangle]+\mathbb{E}\left[\lVert e_{n}\rVert^{2}\right]-\mathbb{E}\left[\lVert e_{l}\rVert^{2}\right]. \tag*{(21)} E [ ∥ e l − e n ∥ 2 ] = 2 E [⟨ e l − e n , e l ⟩] + E [ ∥ e n ∥ 2 ] − E [ ∥ e l ∥ 2 ] . (21)
The last two terms in the right of both equations in (21) both tend to α − α = 0 \alpha-\alpha=0 α − α = 0 . We hence need to show that
E [ ⟨ e l − e n , e l ⟩ ] → 0 as n → ∞ . (22) \mathbb{E}[\langle e_{l}-e_{n},e_{l}\rangle]\to0\quad\text{as }n\to\infty. \tag*{(22)} E [⟨ e l − e n , e l ⟩] → 0 as n → ∞. (22)
Now, by (8) ,
⟨ e l − e n , e l ⟩ = ∑ k = n l − 1 ⟨ e k + 1 − e k , e l ⟩ = − ∑ k = n l − 1 ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x l − x ∗ ) ⟩ . \langle e_{l}-e_{n},e_{l}\rangle=\sum_{k=n}^{l-1}\langle e_{k+1}-e_{k},e_{l}\rangle=-\sum_{k=n}^{l-1}\langle F_{I_{k}}(x_{k})-y_{I_{k}},F'_{I_{k}}(x_{k})(x_{l}-x_{*})\rangle. ⟨ e l − e n , e l ⟩ = k = n ∑ l − 1 ⟨ e k + 1 − e k , e l ⟩ = − k = n ∑ l − 1 ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x l − x ∗ )⟩ .
By applying the triangle inequality and Cauchy-Schwarz inequality, we further get
∣ E [ ⟨ e l − e n , e l ⟩ ] ∣ ≤ ∑ k = n l − 1 ∣ E [ ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x l − x k + x k − x ∗ ) ⟩ ] ∣ = ∑ k = n l − 1 ∣ E [ ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x l − x k ) ⟩ ] ∣ + ∑ k = n l − 1 ∣ E [ ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x k − x ∗ ) ⟩ ] ∣ ≤ ∑ k = n l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1 / 2 E [ ∥ F I k ′ ( x k ) ( x l − x k ) ∥ 2 ] 1 / 2 + ∑ k = n l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1 / 2 E [ ∥ F I k ′ ( x k ) ( x k − x ∗ ) ∥ 2 ] 1 / 2 = : E 1 + E 2 . \begin{aligned}
\left|\mathbb{E}\left[\langle e_l-e_n,e_l\rangle\right]\right|
&\le\sum_{k=n}^{l-1}\left|\mathbb{E}\left[\left\langle F_{I_k}(x_k)-y_{I_k},F'_{I_k}(x_k)(x_l-x_k+x_k-x_\ast)\right\rangle\right]\right|\\
&=\sum_{k=n}^{l-1}\left|\mathbb{E}\left[\left\langle F_{I_k}(x_k)-y_{I_k},F'_{I_k}(x_k)(x_l-x_k)\right\rangle\right]\right|\\
&\quad+\sum_{k=n}^{l-1}\left|\mathbb{E}\left[\left\langle F_{I_k}(x_k)-y_{I_k},F'_{I_k}(x_k)(x_k-x_\ast)\right\rangle\right]\right|\\
&\le\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]^{1/2}\mathbb{E}\left[\left\|F'_{I_k}(x_k)(x_l-x_k)\right\|^2\right]^{1/2}\\
&\quad+\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]^{1/2}\mathbb{E}\left[\left\|F'_{I_k}(x_k)(x_k-x_\ast)\right\|^2\right]^{1/2}\\
&=:E_1+E_2.
\end{aligned} ∣ E [ ⟨ e l − e n , e l ⟩ ] ∣ ≤ k = n ∑ l − 1 E [ ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x l − x k + x k − x ∗ ) ⟩ ] = k = n ∑ l − 1 E [ ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x l − x k ) ⟩ ] + k = n ∑ l − 1 E [ ⟨ F I k ( x k ) − y I k , F I k ′ ( x k ) ( x k − x ∗ ) ⟩ ] ≤ k = n ∑ l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1/2 E [ F I k ′ ( x k ) ( x l − x k ) 2 ] 1/2 + k = n ∑ l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1/2 E [ F I k ′ ( x k ) ( x k − x ∗ ) 2 ] 1/2 =: E 1 + E 2 .
Applying Lemma 2.2 and the triangle inequality, we obtain
E 1 ≤ ( 1 + η ) ∑ k = n l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1 / 2 E [ ∥ F I k ( x l ) − F I k ( x k ) ∥ 2 ] 1 / 2 ≤ ( 1 + η ) ∑ k = n l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1 / 2 ( E [ ∥ F I k ( x l ) − F I k ( x ∗ ) ∥ 2 ] 1 / 2 + E [ ∥ F I k ( x ∗ ) − F I k ( x k ) ∥ 2 ] 1 / 2 ) . \begin{aligned}
E_1
&\le(1+\eta)\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]^{1/2}\mathbb{E}\left[\left\|F_{I_k}(x_l)-F_{I_k}(x_k)\right\|^2\right]^{1/2}\\
&\le(1+\eta)\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]^{1/2}\left(\mathbb{E}\left[\left\|F_{I_k}(x_l)-F_{I_k}(x_\ast)\right\|^2\right]^{1/2}\right.\\
&\qquad\left.+\mathbb{E}\left[\left\|F_{I_k}(x_\ast)-F_{I_k}(x_k)\right\|^2\right]^{1/2}\right).
\end{aligned} E 1 ≤ ( 1 + η ) k = n ∑ l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1/2 E [ ∥ F I k ( x l ) − F I k ( x k ) ∥ 2 ] 1/2 ≤ ( 1 + η ) k = n ∑ l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1/2 ( E [ ∥ F I k ( x l ) − F I k ( x ∗ ) ∥ 2 ] 1/2 + E [ ∥ F I k ( x ∗ ) − F I k ( x k ) ∥ 2 ] 1/2 ) .
Since x k x_k x k is F k \mathcal{F}_k F k -measurable, Lemma 2.1 implies
E [ ∥ F I k ( x k ) − y I k ∥ 2 ] = b p E [ ∥ F ( x k ) − y ∥ 2 ] . \mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]=\frac{b}{p}\mathbb{E}\left[\left\|F(x_k)-y\right\|^2\right]. E [ ∥ F I k ( x k ) − y I k ∥ 2 ] = p b E [ ∥ F ( x k ) − y ∥ 2 ] .
Note that x l x_l x l is not F k \mathcal{F}_k F k -measurable, since k < l k<l k < l . But observe that ∥ F I k ( x l ) − F I k ( x ∗ ) ∥ ≤ ∥ F ( x l ) − F ( x ∗ ) ∥ \left\|F_{I_k}(x_l)-F_{I_k}(x_\ast)\right\|\le\left\|F(x_l)-F(x_\ast)\right\| ∥ F I k ( x l ) − F I k ( x ∗ ) ∥ ≤ ∥ F ( x l ) − F ( x ∗ ) ∥ . By the choice of l l l in (19) , it holds that
E [ ∥ F I k ( x l ) − F I k ( x ∗ ) ∥ 2 ] 1 / 2 ≤ E [ ∥ F ( x l ) − F ( x ∗ ) ∥ 2 ] 1 / 2 ≤ E [ ∥ F ( x k ) − F ( x ∗ ) ∥ 2 ] 1 / 2 \mathbb{E}\left[\left\|F_{I_k}(x_l)-F_{I_k}(x_\ast)\right\|^2\right]^{1/2}
\le\mathbb{E}\left[\left\|F(x_l)-F(x_\ast)\right\|^2\right]^{1/2}
\le\mathbb{E}\left[\left\|F(x_k)-F(x_\ast)\right\|^2\right]^{1/2} E [ ∥ F I k ( x l ) − F I k ( x ∗ ) ∥ 2 ] 1/2 ≤ E [ ∥ F ( x l ) − F ( x ∗ ) ∥ 2 ] 1/2 ≤ E [ ∥ F ( x k ) − F ( x ∗ ) ∥ 2 ] 1/2
for n ≤ k < l n\le k<l n ≤ k < l , noting that y = F ( x ∗ ) y=F(x_\ast) y = F ( x ∗ ) . This brings us to
E 1 ≤ c 1 ∑ k = n l − 1 E [ ∥ F ( x k ) − F ( x ∗ ) ∥ 2 ] , E_1\le c_1\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F(x_k)-F(x_\ast)\right\|^2\right], E 1 ≤ c 1 k = n ∑ l − 1 E [ ∥ F ( x k ) − F ( x ∗ ) ∥ 2 ] ,
where c 1 : = ( 1 + η ) b / p ( 1 + b / p ) c_1:=(1+\eta)\sqrt{b/p}(1+\sqrt{b/p}) c 1 := ( 1 + η ) b / p ( 1 + b / p ) . Similarly,
E 2 ≤ ( 1 + η ) ∑ k = n l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1 / 2 E [ ∥ F I k ( x k ) − F I k ( x ∗ ) ∥ 2 ] 1 / 2 = ( 1 + η ) ∑ k = n l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] = c 2 ∑ k = n l − 1 E [ ∥ F ( x k ) − y ∥ 2 ] , \begin{aligned}
E_2\le(1+\eta)\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]^{1/2}\mathbb{E}\left[\left\|F_{I_k}(x_k)-F_{I_k}(x_\ast)\right\|^2\right]^{1/2} \\
&=(1+\eta)\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F_{I_k}(x_k)-y_{I_k}\right\|^2\right]
=c_2\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F(x_k)-y\right\|^2\right],
\end{aligned} E 2 ≤ ( 1 + η ) k = n ∑ l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] 1/2 E [ ∥ F I k ( x k ) − F I k ( x ∗ ) ∥ 2 ] 1/2 = ( 1 + η ) k = n ∑ l − 1 E [ ∥ F I k ( x k ) − y I k ∥ 2 ] = c 2 k = n ∑ l − 1 E [ ∥ F ( x k ) − y ∥ 2 ] ,
where c 2 : = ( 1 + η ) b / p c_2:=(1+\eta)b/p c 2 := ( 1 + η ) b / p . Let c 3 : = c 1 + c 2 c_3:=c_1+c_2 c 3 := c 1 + c 2 . Combining the estimates for E 1 E_1 E 1 and E 2 E_2 E 2 , and using (17) , we get
∣ E [ ⟨ e l − e n , e l ⟩ ] ∣ ≤ c 3 ∑ k = n l − 1 E [ ∥ F ( x k ) − y ∥ 2 ] ≤ c 4 ∑ k = n l − 1 ( E [ ∥ e k ∥ 2 ] − E [ ∥ e k + 1 ∥ 2 ] ) = c 4 ( E [ ∥ e n ∥ 2 ] − E [ ∥ e l ∥ 2 ] ) , \begin{aligned}
\left|\mathbb{E}\left[\langle e_l-e_n,e_l\rangle\right]\right|
\le c_3\sum_{k=n}^{l-1}\mathbb{E}\left[\left\|F(x_k)-y\right\|^2\right]
\le c_4\sum_{k=n}^{l-1}\left(\mathbb{E}\left[\left\|e_k\right\|^2\right]-\mathbb{E}\left[\left\|e_{k+1}\right\|^2\right]\right) \\
&=c_4\left(\mathbb{E}\left[\left\|e_n\right\|^2\right]-\mathbb{E}\left[\left\|e_l\right\|^2\right]\right),
\end{aligned} ∣ E [ ⟨ e l − e n , e l ⟩ ] ∣ ≤ c 3 k = n ∑ l − 1 E [ ∥ F ( x k ) − y ∥ 2 ] ≤ c 4 k = n ∑ l − 1 ( E [ ∥ e k ∥ 2 ] − E [ ∥ e k + 1 ∥ 2 ] ) = c 4 ( E [ ∥ e n ∥ 2 ] − E [ ∥ e l ∥ 2 ] ) ,
where c 4 : = c 3 c c_4 := \frac{c_3}{c} c 4 := c c 3 . By a similar process, we can also deduce that
∣ E [ ⟨ e l − e j , e l ⟩ ] ∣ ≤ c 4 ( E [ ∥ e l ∥ 2 ] − E [ ∥ e j ∥ 2 ] ) . \left|\mathbb{E}\left[\langle e_l-e_j,e_l\rangle\right]\right| \leq c_4\left(\mathbb{E}\left[\lVert e_l\rVert^2\right]-\mathbb{E}\left[\lVert e_j\rVert^2\right]\right). ∣ E [ ⟨ e l − e j , e l ⟩ ] ∣ ≤ c 4 ( E [ ∥ e l ∥ 2 ] − E [ ∥ e j ∥ 2 ] ) .
Using the convergence of { E [ ∥ e n ∥ 2 ] } \{\mathbb{E}\left[\lVert e_n\rVert^2\right]\} { E [ ∥ e n ∥ 2 ] } , it follows that the right hand sides of (21) converges to zero as n → ∞ n\to\infty n → ∞ . By (20) , it also follows that { e n } \{e_n\} { e n } and, in turn, { x n } \{x_n\} { x n } are Cauchy sequences in L 2 ( Ω , X ) L^2(\Omega,X) L 2 ( Ω , X ) . Thus { x n } \{x_n\} { x n } has a limit denoted by x ∗ ∈ L 2 ( Ω , X ) x^*\in L^2(\Omega,X) x ∗ ∈ L 2 ( Ω , X ) . Using (18) , we get E [ ∥ y − F ( x ∗ ) ∥ 2 ] = 0 \mathbb{E}[\lVert y-F(x^*)\rVert^2]=0 E [∥ y − F ( x ∗ ) ∥ 2 ] = 0 and, in turn, x ∗ x^* x ∗ is a solution of problem (1) almost everywhere. The point-wise monotonicity of { ∥ x n − x ∗ ∥ } \{\lVert x_n-x^*\rVert\} {∥ x n − x ∗ ∥} and the convergence in expectation additionally imply ∥ x n − x ∗ ∥ → 0 \lVert x_n-x^*\rVert\to0 ∥ x n − x ∗ ∥ → 0 almost everywhere as n → ∞ n\to\infty n → ∞ . Using this, we conclude from x n ∈ B ρ ( x ∗ ) x_n\in B_\rho(x^*) x n ∈ B ρ ( x ∗ ) , that x ∗ ∈ B ρ ( x ∗ ) ⊆ B 2 ρ ( x 0 ) x^*\in B_\rho(x^*)\subseteq B_{2\rho}(x_0) x ∗ ∈ B ρ ( x ∗ ) ⊆ B 2 ρ ( x 0 ) almost everywhere.
If, in addition, N ( F ′ ( x † ) ) ⊂ N ( F ′ ( x ) ) \mathcal{N}(F'(x^\dagger))\subset\mathcal{N}(F'(x)) N ( F ′ ( x † )) ⊂ N ( F ′ ( x )) for all x ∈ B ρ ( x † ) x\in B_\rho(x^\dagger) x ∈ B ρ ( x † ) , then one can simply apply the same argument as in [18 ] : Problem (1) has a unique solution x † x^\dagger x † of minimal distance from initial guess x 0 x_0 x 0 which satisfies x † − x 0 ∈ N ( F ′ ( x † ) ) ⊥ x^\dagger-x_0\in\mathcal{N}(F'(x^\dagger))^\perp x † − x 0 ∈ N ( F ′ ( x † ) ) ⊥ . We now again fix an infinite selection of batches Λ = ( I 0 , I 1 , … ) ∈ Ω \Lambda=(I_0,I_1,\ldots)\in\Omega Λ = ( I 0 , I 1 , … ) ∈ Ω and denote the corresponding iterates as x ^ n : = x n ( Λ ) ∈ X \hat{x}_n:=x_n(\Lambda)\in X x ^ n := x n ( Λ ) ∈ X . By definition of the iteration (8) , it holds
x ^ n + 1 − x ^ n ∈ R ( F I n ′ ( x ^ n ) ∗ ) ⊂ R ( F ′ ( x ^ n ) ∗ ) ⊂ N ( F ′ ( x ^ n ) ) ⊥ ⊂ N ( F ′ ( x † ) ) ⊥ \hat{x}_{n+1}-\hat{x}_n\in R(F'_{I_n}(\hat{x}_n)^*)\subset R(F'(\hat{x}_n)^*)\subset\mathcal{N}(F'(\hat{x}_n))^\perp\subset\mathcal{N}(F'(x^\dagger))^\perp x ^ n + 1 − x ^ n ∈ R ( F I n ′ ( x ^ n ) ∗ ) ⊂ R ( F ′ ( x ^ n ) ∗ ) ⊂ N ( F ′ ( x ^ n ) ) ⊥ ⊂ N ( F ′ ( x † ) ) ⊥
for all n ∈ N 0 n\in\mathbb{N}_0 n ∈ N 0 . Then it follows that x ^ n − x 0 = ( x ^ n − x ^ n − 1 ) + ⋯ + ( x ^ 1 − x 0 ) ∈ N ( F ′ ( x † ) ) ⊥ \hat{x}_n-x_0=(\hat{x}_n-\hat{x}_{n-1})+\cdots+(\hat{x}_1-x_0)\in\mathcal{N}(F'(x^\dagger))^\perp x ^ n − x 0 = ( x ^ n − x ^ n − 1 ) + ⋯ + ( x ^ 1 − x 0 ) ∈ N ( F ′ ( x † ) ) ⊥ for n = 0 , 1 , … n=0,1,\ldots n = 0 , 1 , … . Since Λ ∈ Ω \Lambda\in\Omega Λ ∈ Ω and n ∈ N n\in\mathbb{N} n ∈ N was arbitrary, this extends to the point-wise limit of x n x_n x n , i.e. x ∗ − x 0 ∈ N ( F ′ ( x † ) ) ⊥ x^*-x_0\in\mathcal{N}(F'(x^\dagger))^\perp x ∗ − x 0 ∈ N ( F ′ ( x † ) ) ⊥ almost everywhere, and therefore we get x ∗ = x † x^*=x^\dagger x ∗ = x † .
Convergence for noisy data
Lemma 2.4. Let Assumption 2.1 hold and x ∗ ∈ B 2 ρ ( x 0 ) x_*\in B_{2\rho}(x_0) x ∗ ∈ B 2 ρ ( x 0 ) be any solution to problem (1) . Consider the iteration { x n δ } ⊆ X \{x_n^\delta\}\subseteq X { x n δ } ⊆ X generated by (8) with a fixed selection of batches ( I 0 , I 1 , … ) ∈ Ω (I_0,I_1,\ldots)\in\Omega ( I 0 , I 1 , … ) ∈ Ω and
τ > 2 ( 1 + η ) 1 − 2 η . (23) \tau>\frac{2(1+\eta)}{1-2\eta}. \tag*{(23)} τ > 1 − 2 η 2 ( 1 + η ) . (23) Then x n δ ∈ B 2 ρ ( x 0 ) x_n^\delta\in B_{2\rho}(x_0) x n δ ∈ B 2 ρ ( x 0 ) for all n ∈ N 0 n\in\mathbb{N}_0 n ∈ N 0 and we get
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ − ω n c ∥ y I n δ − F I n ( x n δ ) ∥ 2 , (24) \lVert x_{n+1}^\delta-x_*\rVert^2-\lVert x_n^\delta-x_*\rVert^2\leq-\omega_n c\lVert y_{I_n}^\delta-F_{I_n}(x_n^\delta)\rVert^2, \tag*{(24)} ∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ − ω n c ∥ y I n δ − F I n ( x n δ ) ∥ 2 , (24) with a constant c > 0 c>0 c > 0 . In particular, the sequence { ∥ x n δ − x ∗ ∥ } \{\lVert x_n^\delta-x_*\rVert\} {∥ x n δ − x ∗ ∥} is monotonically decreasing.
Proof. We follow the argumentation of [35 ] [Proposition 2.2]. Let us denote the constant c 1 ∈ R c_1\in\mathbb{R} c 1 ∈ R as c 1 : = ( 1 − 2 η ) − 2 ( 1 + η ) τ − 1 c_1:=(1-2\eta)-2(1+\eta)\tau^{-1} c 1 := ( 1 − 2 η ) − 2 ( 1 + η ) τ − 1 . Note that c 1 > 0 c_1>0 c 1 > 0 by (23) . Suppose x n δ ∈ B 2 ρ ( x 0 ) x_n^\delta\in B_{2\rho}(x_0) x n δ ∈ B 2 ρ ( x 0 ) for a fixed n ∈ N 0 n\in\mathbb{N}_0 n ∈ N 0 . Then Lemma 2.3 implies
∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ ω n p b ∥ y I n δ − F I n ( x n δ ) ∥ × ( ( 1 + η ) δ I n − ( 1 − 2 η ) ∥ y I n δ − F I n ( x n δ ) ∥ ) ≤ − c 1 ω n p b ∥ y I n δ − F I n ( x n δ ) ∥ 2 . (25) \begin{aligned}
\lVert x_{n+1}^\delta-x_*\rVert^2-\lVert x_n^\delta-x_*\rVert^2
&\leq\omega_n\frac{p}{b}\lVert y_{I_n}^\delta-F_{I_n}(x_n^\delta)\rVert\\
&\quad{}\times\left((1+\eta)\delta_{I_n}-(1-2\eta)\lVert y_{I_n}^\delta-F_{I_n}(x_n^\delta)\rVert\right)\\
&\leq-c_1\omega_n\frac{p}{b}\lVert y_{I_n}^\delta-F_{I_n}(x_n^\delta)\rVert^2. \tag*{(25)}
\end{aligned} ∥ x n + 1 δ − x ∗ ∥ 2 − ∥ x n δ − x ∗ ∥ 2 ≤ ω n b p ∥ y I n δ − F I n ( x n δ )∥ × ( ( 1 + η ) δ I n − ( 1 − 2 η ) ∥ y I n δ − F I n ( x n δ )∥ ) ≤ − c 1 ω n b p ∥ y I n δ − F I n ( x n δ ) ∥ 2 . (25)
The last inequality follows directly by the definition of ω n \omega_n ω n : If ω n = 0 \omega_n=0 ω n = 0 both sides vanish and if ω n = 1 \omega_n=1 ω n = 1 it holds δ I n ≤ τ − 1 ∥ y I n δ − F I n ( x n δ ) ∥ \delta_{I_n}\leq\tau^{-1}\lVert y_{I_n}^\delta-F_{I_n}(x_n^\delta)\rVert δ I n ≤ τ − 1 ∥ y I n δ − F I n ( x n δ )∥ .
In particular, for any solution x ∗ ∈ B ρ ( x 0 ) x_*\in B_\rho(x_0) x ∗ ∈ B ρ ( x 0 ) according to Assumption 2.1(i), it follows inductively x n δ ∈ B ρ ( x ∗ ) ⊆ B 2 ρ ( x 0 ) x_n^\delta\in B_\rho(x_*)\subseteq B_{2\rho}(x_0) x n δ ∈ B ρ ( x ∗ ) ⊆ B 2 ρ ( x 0 ) for all n ∈ N 0 n\in\mathbb{N}_0 n ∈ N 0 , since x n − 1 δ ∈ B ρ ( x ∗ ) x_{n-1}^\delta\in B_\rho(x_*) x n − 1 δ ∈ B ρ ( x ∗ ) implies x n δ ∈ B ρ ( x ∗ ) x_n^\delta\in B_\rho(x_*) x n δ ∈ B ρ ( x ∗ ) by
∥ x n δ − x ∗ ∥ ≤ ∥ x n − 1 δ − x ∗ ∥ < ρ . \lVert x_n^\delta-x_*\rVert\leq\lVert x_{n-1}^\delta-x_*\rVert<\rho. ∥ x n δ − x ∗ ∥ ≤ ∥ x n − 1 δ − x ∗ ∥ < ρ .
Hence inequality (25) holds for all iterates with c = c 1 p / b c=c_1p/b c = c 1 p / b .
In particular, the above Lemma implies that x n δ ∈ L 2 ( Ω , X ) x_n^\delta\in L^2(\Omega, X) x n δ ∈ L 2 ( Ω , X ) for the random variable x n δ x_n^\delta x n δ generated by (8) with τ \tau τ as in (23) . In the next Lemma, we analyze the relationship between the noisy and the noise-free iteration.
Lemma 2.5. Let Assumption 2.1 hold and N ∈ N 0 N \in\mathbb{N}_0 N ∈ N 0 be fixed. Consider the iteration { x n δ } ⊆ X \{x_n^\delta\} \subseteq X { x n δ } ⊆ X defined by (8) with an arbitrary selection of batches ( I 0 , I 1 , … ) ∈ Ω (I_0,I_1,\ldots) \in\Omega ( I 0 , I 1 , … ) ∈ Ω . Then it holds
∥ x N δ − x N ∥ → 0 as δ → 0. \left\|x_N^\delta-x_N\right\| \to0 \text{ as } \delta\to0. x N δ − x N → 0 as δ → 0. In particular, for the sequence of random variables { x n δ } ⊆ L 2 ( Ω , X ) \{x_n^\delta\} \subseteq L^2(\Omega,X) { x n δ } ⊆ L 2 ( Ω , X ) , it holds
E [ ∥ x N δ − x N ∥ ] → 0 as δ → 0. \mathbb{E}\left[\left\|x_N^\delta-x_N\right\|\right] \to0 \text{ as } \delta\to0. E [ x N δ − x N ] → 0 as δ → 0.
Proof. The proof follows the argumentation of [32 ] , Lemma 3.3. First note that the convergence of x N δ x_N^\delta x N δ for a fixed selection of batches implies the convergence in expectation, since there are only finitely many sample paths for fixed N ≥ 0 N \geq0 N ≥ 0 .
We prove by mathematical induction over N N N . For N = 0 N=0 N = 0 the result is trivial. Assume the result holds for x N δ x_N^\delta x N δ with a fixed N ∈ N N \in\mathbb{N} N ∈ N , we need to prove it holds for x N + 1 δ x_{N+1}^\delta x N + 1 δ . Now, by (8) , and using ω N = 1 \omega_N=1 ω N = 1 in the exact data case, it holds
x N + 1 δ − x N + 1 = ( x N δ − x N ) − ω N p b F I N ′ ( x N δ ) ∗ ( F I N ( x N δ ) − y I N δ ) + p b F I N ′ ( x N δ ) ∗ ( F I N ( x N ) − y I N ) − p b F I N ′ ( x N δ ) ∗ ( F I N ( x N ) − y I N ) + p b F I N ′ ( x N ) ∗ ( F I N ( x N ) − y I N ) = ( x N δ − x N ) − p b ( F I N ′ ( x N δ ) ∗ − F I N ′ ( x N ) ∗ ) ( F I N ( x N ) − y I N ) + p b F I N ′ ( x N δ ) ∗ ( ω N ( F I N ( x N δ ) − y I N δ ) − ( F I N ( x N ) − y I N ) ) . \begin{aligned}
x_{N+1}^\delta-x_{N+1}
={}&(x_N^\delta-x_N)-\omega_N\frac{p}{b}F_{I_N}'(x_N^\delta)^*(F_{I_N}(x_N^\delta)-y_{I_N}^\delta)\\
&+\frac{p}{b}F_{I_N}'(x_N^\delta)^*(F_{I_N}(x_N)-y_{I_N})-\frac{p}{b}F_{I_N}'(x_N^\delta)^*(F_{I_N}(x_N)-y_{I_N})\\
&+\frac{p}{b}F_{I_N}'(x_N)^*(F_{I_N}(x_N)-y_{I_N})\\
={}&(x_N^\delta-x_N)-\frac{p}{b}\left(F_{I_N}'(x_N^\delta)^*-F_{I_N}'(x_N)^*\right)(F_{I_N}(x_N)-y_{I_N})\\
&+\frac{p}{b}F_{I_N}'(x_N^\delta)^*\left(\omega_N(F_{I_N}(x_N^\delta)-y_{I_N}^\delta)-(F_{I_N}(x_N)-y_{I_N})\right).
\end{aligned} x N + 1 δ − x N + 1 = = ( x N δ − x N ) − ω N b p F I N ′ ( x N δ ) ∗ ( F I N ( x N δ ) − y I N δ ) + b p F I N ′ ( x N δ ) ∗ ( F I N ( x N ) − y I N ) − b p F I N ′ ( x N δ ) ∗ ( F I N ( x N ) − y I N ) + b p F I N ′ ( x N ) ∗ ( F I N ( x N ) − y I N ) ( x N δ − x N ) − b p ( F I N ′ ( x N δ ) ∗ − F I N ′ ( x N ) ∗ ) ( F I N ( x N ) − y I N ) + b p F I N ′ ( x N δ ) ∗ ( ω N ( F I N ( x N δ ) − y I N δ ) − ( F I N ( x N ) − y I N ) ) .
Then by triangle and Cauchy-Schwarz inequality,
∥ x N + 1 δ − x N + 1 ∥ ≤ ∥ x N δ − x N ∥ + p b ∥ F I N ′ ( x N δ ) ∗ − F I N ′ ( x N ) ∗ ∥ ∥ F I N ( x N ) − y I N ∥ + p b ∥ F I N ′ ( x N δ ) ∗ ∥ ∥ ω N ( F I N ( x N δ ) − y I N δ ) − ( F I N ( x N ) − y I N ) ∥ . \begin{aligned}
\left\|x_{N+1}^\delta-x_{N+1}\right\|
\leq{}&\left\|x_N^\delta-x_N\right\|+\frac{p}{b}\left\|F_{I_N}'(x_N^\delta)^*-F_{I_N}'(x_N)^*\right\|\left\|F_{I_N}(x_N)-y_{I_N}\right\|\\
&+\frac{p}{b}\left\|F_{I_N}'(x_N^\delta)^*\right\|\left\|\omega_N(F_{I_N}(x_N^\delta)-y_{I_N}^\delta)-(F_{I_N}(x_N)-y_{I_N})\right\|.
\end{aligned} x N + 1 δ − x N + 1 ≤ x N δ − x N + b p F I N ′ ( x N δ ) ∗ − F I N ′ ( x N ) ∗ ∥ F I N ( x N ) − y I N ∥ + b p F I N ′ ( x N δ ) ∗ ω N ( F I N ( x N δ ) − y I N δ ) − ( F I N ( x N ) − y I N ) .
By induction hypothesis the first term converges to zero for δ → 0 \delta\to0 δ → 0 . Using the continuity of the operator F I ′ F_I' F I ′ the same holds for the second term. For the third term first note that with the same argumentation it follows lim sup δ → 0 ∥ F I N ′ ( x N δ ) ∗ ∥ < ∞ \limsup_{\delta\to0}\left\|F_{I_N}'(x_N^\delta)^*\right\|<\infty lim sup δ → 0 F I N ′ ( x N δ ) ∗ < ∞ . We now want to show that
∥ ω N ( F I N ( x N δ ) − y I N δ ) − ( F I N ( x N ) − y I N ) ∥ → 0 as δ → 0. (26) \left\|\omega_N(F_{I_N}(x_N^\delta)-y_{I_N}^\delta)-(F_{I_N}(x_N)-y_{I_N})\right\|\to0 \text{ as } \delta\to0. \tag*{(26)} ω N ( F I N ( x N δ ) − y I N δ ) − ( F I N ( x N ) − y I N ) → 0 as δ → 0. (26)
For this, let R ( δ ) : = F I N ( x N δ ) − y I N δ R(\delta):=F_{I_N}(x_N^\delta)-y_{I_N}^\delta R ( δ ) := F I N ( x N δ ) − y I N δ and R ( 0 ) : = F I N ( x N ) − y I N R(0):=F_{I_N}(x_N)-y_{I_N} R ( 0 ) := F I N ( x N ) − y I N its exact data variant. This reduces (26) to lim δ → 0 ∥ ω N R ( δ ) − R ( 0 ) ∥ = 0 \lim_{\delta\to0}\|\omega_N R(\delta)-R(0)\|=0 lim δ → 0 ∥ ω N R ( δ ) − R ( 0 ) ∥ = 0 with ω N = 1 \omega_N=1 ω N = 1 if ∥ R ( δ ) ∥ ≥ τ δ \|R(\delta)\|\geq\tau\delta ∥ R ( δ ) ∥ ≥ τ δ and ω N = 0 \omega_N=0 ω N = 0 else. Since lim δ → 0 y I N δ = y I N \lim_{\delta\to0}y_{I_N}^\delta=y_{I_N} lim δ → 0 y I N δ = y I N , we get with the induction hypothesis and continuity of F I N F_{I_N} F I N that lim δ → 0 R ( δ ) = R ( 0 ) \lim_{\delta\to0}R(\delta)=R(0) lim δ → 0 R ( δ ) = R ( 0 ) . For R ( 0 ) = 0 R(0)=0 R ( 0 ) = 0 this implies (26) . If ∥ R ( 0 ) ∥ > 0 \|R(0)\|>0 ∥ R ( 0 ) ∥ > 0 then ∥ R ( δ ) ∥ ≥ τ δ \|R(\delta)\|\geq\tau\delta ∥ R ( δ ) ∥ ≥ τ δ and hence ω N = 1 \omega_N=1 ω N = 1 for sufficiently small δ \delta δ . Therefore (26) and the statement follows. □
In the following Theorem we prove a general result, which includes the convergence for both the a priori and a posteriori stopping.
Theorem 2.2. Let Assumption 2.1 hold and choose τ \tau τ according to (23) . Consider the batched Landweber-Kaczmarz iteration { x n δ } ⊆ L 2 ( Ω , X ) \{x_n^\delta\}\subseteq L^2(\Omega,X) { x n δ } ⊆ L 2 ( Ω , X ) defined by (8) and let x ∗ ∈ L 2 ( Ω , X ) x^*\in L^2(\Omega,X) x ∗ ∈ L 2 ( Ω , X ) be the random variable from Theorem 2.1, which solves problem (1) almost everywhere. Then for all random variables n δ ∈ N n_\delta\in\mathbb{N} n δ ∈ N on the probability space (12) , with n δ → ∞ n_\delta\to\infty n δ → ∞ as δ → 0 \delta\to0 δ → 0 , it holds
E [ ∥ x n δ δ − x ∗ ∥ ] → 0 as δ → 0 , \mathbb{E}\left[\left\|x_{n_\delta}^\delta-x^*\right\|\right]\to0 \text{ as } \delta\to0, E [ x n δ δ − x ∗ ] → 0 as δ → 0 , where E \mathbb{E} E denotes the joint expectation.
Proof. First, note that the monotonicity of the error { ∥ x n − x ∗ ∥ } \{\lVert x_n-x^*\rVert\} {∥ x n − x ∗ ∥} (Lemma 2.4 ) and its convergence in L 2 ( Ω , X ) L^2(\Omega,X) L 2 ( Ω , X ) (Theorem 2.1) imply the point-wise convergence ∥ x n − x ∗ ∥ → 0 \lVert x_n-x^*\rVert\to0 ∥ x n − x ∗ ∥ → 0 almost everywhere as n → ∞ n\to\infty n → ∞ . Let now { y δ k } ⊆ Y \{y^{\delta_k}\}\subseteq Y { y δ k } ⊆ Y be a sequence of noisy data with lim k → ∞ δ k = 0 \lim_{k\to\infty}\delta_k=0 lim k → ∞ δ k = 0 . We now prove point-wise convergence of the noisy iterates, i.e. ∥ x n δ k δ k − x ∗ ∥ → 0 \lVert x_{n_{\delta_k}}^{\delta_k}-x^*\rVert\to0 ∥ x n δ k δ k − x ∗ ∥ → 0 almost everywhere as k → ∞ k\to\infty k → ∞ . For this, we fix an infinite selection of batches Λ : = ( I 0 , I 1 , … ) ∈ Ω \Lambda:= (I_0,I_1,\ldots)\in\Omega Λ := ( I 0 , I 1 , … ) ∈ Ω , such that x ^ ∗ : = x ∗ ( Λ ) \hat{x}^*:=x^*(\Lambda) x ^ ∗ := x ∗ ( Λ ) is a solution of (1) and for the iteration x ^ n : = x n ( Λ ) \hat{x}_n:=x_n(\Lambda) x ^ n := x n ( Λ ) it holds lim n → ∞ ∥ x ^ n − x ^ ∗ ∥ = 0 \lim_{n\to\infty}\lVert\hat{x}_n-\hat{x}^*\rVert=0 lim n → ∞ ∥ x ^ n − x ^ ∗ ∥ = 0 . Setting n k : = n δ k ( Λ ) > m n_k:=n_{\delta_k}(\Lambda)>m n k := n δ k ( Λ ) > m , Lemma 2.4 implies that
∥ x ^ n k δ k − x ^ ∗ ∥ ≤ ∥ x ^ m δ k − x ^ ∗ ∥ ≤ ∥ x ^ m δ k − x ^ m ∥ + ∥ x ^ m − x ^ ∗ ∥ . (27) \lVert\hat{x}_{n_k}^{\delta_k}-\hat{x}^*\rVert\le\lVert\hat{x}_m^{\delta_k}-\hat{x}^*\rVert\le\lVert\hat{x}_m^{\delta_k}-\hat{x}_m\rVert+\lVert\hat{x}_m-\hat{x}^*\rVert. \tag*{(27)} ∥ x ^ n k δ k − x ^ ∗ ∥ ≤ ∥ x ^ m δ k − x ^ ∗ ∥ ≤ ∥ x ^ m δ k − x ^ m ∥ + ∥ x ^ m − x ^ ∗ ∥ . (27)
Let ε > 0 \varepsilon>0 ε > 0 . Since the second summand in (27) vanishes for large m m m , we can fix some m = m ( ε ) m=m(\varepsilon) m = m ( ε ) so that the term is less than ε / 2 \varepsilon/2 ε /2 . Also, by Lemma 2.5 , there is k 0 = k ( ε , m ) k_0=k(\varepsilon,m) k 0 = k ( ε , m ) such that the first term in the right hand side of (27) is less than ε / 2 \varepsilon/2 ε /2 for k ≥ k 0 k\ge k_0 k ≥ k 0 . And due to n k → ∞ n_k\to\infty n k → ∞ there is a k 1 ( m ) k_1(m) k 1 ( m ) , such that n k > m n_k>m n k > m for all k ≥ k 1 k\ge k_1 k ≥ k 1 . Consequently for all k ≥ max { k 0 , k 1 } k\ge\max\{k_0,k_1\} k ≥ max { k 0 , k 1 } we get ∥ x ^ n k δ k − x ^ ∗ ∥ ≤ ε \lVert\hat{x}_{n_k}^{\delta_k}-\hat{x}^*\rVert\le\varepsilon ∥ x ^ n k δ k − x ^ ∗ ∥ ≤ ε and hence lim k → ∞ ∥ x ^ n k δ k − x ^ ∗ ∥ = 0 \lim_{k\to\infty}\lVert\hat{x}_{n_k}^{\delta_k}-\hat{x}^*\rVert=0 lim k → ∞ ∥ x ^ n k δ k − x ^ ∗ ∥ = 0 .
Since the selection of the batches Λ \Lambda Λ was arbitrary up to a null set, this implies the convergence in expectation using dominated convergence with majorant ∥ x 0 − x ∗ ∥ \lVert x_0-x^*\rVert ∥ x 0 − x ∗ ∥ , since
∥ x n δ δ − x ∗ ∥ ≤ ∥ x 0 δ − x ∗ ∥ = ∥ x 0 − x ∗ ∥ < ∞ . \lVert x_{n_\delta}^{\delta}-x^*\rVert\le\lVert x_0^\delta-x^*\rVert=\lVert x_0-x^*\rVert<\infty. ∥ x n δ δ − x ∗ ∥ ≤ ∥ x 0 δ − x ∗ ∥ = ∥ x 0 − x ∗ ∥ < ∞.
Corollary 2.1 (A priori convergence). Let the assumptions of Theorem 2.2 hold. Then for all n δ ∈ N n_\delta\in\mathbb{N} n δ ∈ N with n δ → ∞ n_\delta\to\infty n δ → ∞ as δ → 0 \delta\to0 δ → 0 , it holds
E [ ∥ x n δ δ − x ∗ ∥ ] → 0 as δ → 0. \mathbb{E}\left[\lVert x_{n_\delta}^{\delta}-x^*\rVert\right]\to0\text{ as }\delta\to0. E [ ∥ x n δ δ − x ∗ ∥ ] → 0 as δ → 0.
Remark 2.3. Note that in Theorem 2.2 and Corollary 2.1 no growth condition on n δ n_\delta n δ is needed. This is a result of the step size ω n \omega_n ω n in (9) . Unlike the typical semiconvergent behaviour of the classical Landweber iteration, iteration (8) yields unconditional monotonicity of ∥ x n n − x ∗ ∥ \lVert x_n^n-x^*\rVert ∥ x n n − x ∗ ∥ . Instead of deteriorating the approximation for large n n n the iteration remains constant. However, a larger stopping index n δ n_\delta n δ corresponds to a larger computational effort. Hence even though the size of n δ n_\delta n δ has theoretically no impact, early stopping is still computationally desirable.
Batched Discrepancy Principle
Let us now analyze the batched discrepancy principle (10) . The main goal of the proposed criterion is to approximate the classical discrepancy principle with a computationally cheaper rule. For this one observes that
∥ F I n ( x n δ ) − y I n δ ∥ 2 − τ 2 δ I n 2 \lVert F_{I_n}(x_n^\delta)-y_{I_n}^\delta\rVert^2-\tau^2\delta_{I_n}^2 ∥ F I n ( x n δ ) − y I n δ ∥ 2 − τ 2 δ I n 2
is an unbiased estimator of
b p ( ∥ F ( x n δ ) − y δ ∥ 2 − τ 2 δ 2 ) \frac{b}{p}\left(\lVert F(x_n^\delta)-y^\delta\rVert^2-\tau^2\delta^2\right) p b ( ∥ F ( x n δ ) − y δ ∥ 2 − τ 2 δ 2 )
by Lemma 2.1. We improve this estimate by aggregation and approximate
b p ( ∥ F ( x n δ ) − y δ ∥ 2 − τ 2 δ 2 ) ≈ 1 L δ ∑ j = 0 L δ − 1 ( ∥ F I n − j ( x n − j δ ) − y I n − j δ ∥ 2 − τ 2 δ I n − j 2 ) , \frac{b}{p}\left(\lVert F(x_n^\delta)-y^\delta\rVert^2-\tau^2\delta^2\right)\approx\frac{1}{L_\delta}\sum_{j=0}^{L_\delta-1}\left(\lVert F_{I_{n-j}}(x_{n-j}^\delta)-y_{I_{n-j}}^\delta\rVert^2-\tau^2\delta_{I_{n-j}}^2\right), p b ( ∥ F ( x n δ ) − y δ ∥ 2 − τ 2 δ 2 ) ≈ L δ 1 j = 0 ∑ L δ − 1 ( ∥ F I n − j ( x n − j δ ) − y I n − j δ ∥ 2 − τ 2 δ I n − j 2 ) ,
where the aggregation length L δ ∈ N L_\delta\in\mathbb{N} L δ ∈ N is fixed a priori. Here we ignore the errors due to evaluation at different iterates, since we expect them to be similar for L δ L_\delta L δ not too large. However, for smaller L δ L_\delta L δ less equations are monitored and the probability of overlooking equations in an iteration increases, i.e. it is more likely that i ∉ ⋃ j = 0 L δ − 1 I n − j i\notin\bigcup_{j=0}^{L_\delta-1}I_{n-j} i ∈ / ⋃ j = 0 L δ − 1 I n − j for an equation i ∈ { 1 , … , p } i\in\{1,\ldots,p\} i ∈ { 1 , … , p } . This might result in too early stopping, leading to poor reconstructions and no convergence in expectation. Overall, the intuition suggests that the best results can be obtained for a sufficiently large but not too large aggregation length L δ L_\delta L δ . We will see later that the parameter L δ L_\delta L δ does indeed have a significant impact on the quality of the reconstructions. Before proving convergence, the next Lemma shows that the proposed rule is well-defined, i.e. the iteration stops.
Lemma 2.6. Let Assumption 2.1 hold, assume δ i > 0 \delta_i > 0 δ i > 0 for all i ∈ { 1 , … , p } i \in\{1,\ldots,p\} i ∈ { 1 , … , p } , L δ ∈ N L_\delta\in\mathbb{N} L δ ∈ N and choose τ > 1 \tau> 1 τ > 1 according to (23) . Then iteration { x n δ } ⊆ X \{x_n^\delta\} \subseteq X { x n δ } ⊆ X generated by (8) with an arbitrary selection of batches ( I 0 , I 1 , … ) ∈ Ω (I_0,I_1,\ldots) \in\Omega ( I 0 , I 1 , … ) ∈ Ω terminates under the batched discrepancy principle (10) in a finite number of iterations, i.e. n δ < ∞ n_\delta< \infty n δ < ∞ .
Proof. Let x ∗ ∈ B ρ ( x 0 ) x_\ast\in B_{\rho}(x_0) x ∗ ∈ B ρ ( x 0 ) be a solution of problem (1) according to Assumption 2.1 (i). With c > 0 c > 0 c > 0 from Lemma 2.4 , it follows for all M ∈ N M \in\mathbb{N} M ∈ N that
c ∑ n = 0 M ω n ∥ y I n δ − F I n ( x n δ ) ∥ 2 ≤ ∑ n = 0 M ∥ x n δ − x ∗ ∥ 2 − ∥ x n + 1 δ − x ∗ ∥ 2 ≤ ∥ x 0 δ − x ∗ ∥ 2 − ∥ x M + 1 δ − x ∗ ∥ 2 ≤ ∥ x 0 − x ∗ ∥ 2 < ∞ . c \sum_{n=0}^{M} \omega_n \left\|y_{I_n}^{\delta} - F_{I_n}(x_n^\delta)\right\|^2 \le\sum_{n=0}^{M} \left\|x_n^\delta- x_\ast\right\|^2 - \left\|x_{n+1}^\delta- x_\ast\right\|^2
\le\left\|x_0^\delta- x_\ast\right\|^2 - \left\|x_{M+1}^\delta- x_\ast\right\|^2
\le\left\|x_0-x_\ast\right\|^2 < \infty. c n = 0 ∑ M ω n y I n δ − F I n ( x n δ ) 2 ≤ n = 0 ∑ M x n δ − x ∗ 2 − x n + 1 δ − x ∗ 2 ≤ x 0 δ − x ∗ 2 − x M + 1 δ − x ∗ 2 ≤ ∥ x 0 − x ∗ ∥ 2 < ∞.
In particular for M → ∞ M \to\infty M → ∞ this implies
ω n ∥ y I n δ − F I n ( x n δ ) ∥ 2 → 0 as n → ∞ . \omega_n \left\|y_{I_n}^{\delta} - F_{I_n}(x_n^\delta)\right\|^2 \to0 \text{ as } n \to\infty. ω n y I n δ − F I n ( x n δ ) 2 → 0 as n → ∞.
Since δ i > 0 \delta_i > 0 δ i > 0 for all i ∈ { 1 , … , p } i \in\{1,\ldots,p\} i ∈ { 1 , … , p } , there exists an N ∈ N N \in\mathbb{N} N ∈ N such that
ω n ∥ y I n δ − F I n ( x n δ ) ∥ 2 ≤ min i ∈ { 1 , … , p } τ 2 δ i 2 ≤ τ 2 δ I n 2 for all n > N . \omega_n \left\|y_{I_n}^{\delta} - F_{I_n}(x_n^\delta)\right\|^2 \le\min_{i\in\{1,\ldots,p\}} \tau^2\delta_i^2 \le\tau^2\delta_{I_n}^2 \quad\text{for all } n > N. ω n y I n δ − F I n ( x n δ ) 2 ≤ i ∈ { 1 , … , p } min τ 2 δ i 2 ≤ τ 2 δ I n 2 for all n > N .
By multiplying both sides with ω n \omega_n ω n and adding up L δ L_\delta L δ consecutive iterates, it follows
∑ l = 0 L δ − 1 ω n − l ∥ F I n − l ( x n − l δ ) − y I n − l δ ∥ 2 ≤ ∑ l = 0 L δ − 1 ω n − l τ 2 δ I n − l 2 for all n > N − L δ − 1. \sum_{l=0}^{L_\delta-1} \omega_{n-l}\left\|F_{I_{n-l}}(x_{n-l}^\delta)-y_{I_{n-l}}^\delta\right\|^2 \le\sum_{l=0}^{L_\delta-1}\omega_{n-l}\tau^2\delta_{I_{n-l}}^2 \quad\text{for all } n > N-L_\delta-1. l = 0 ∑ L δ − 1 ω n − l F I n − l ( x n − l δ ) − y I n − l δ 2 ≤ l = 0 ∑ L δ − 1 ω n − l τ 2 δ I n − l 2 for all n > N − L δ − 1.
Note that ω n − l 2 = ω n − l \omega_{n-l}^2=\omega_{n-l} ω n − l 2 = ω n − l , since it only takes values 0 and 1. Additionally we get
∥ F I n − l ( x n − l δ ) − y I n − l δ ∥ 2 − τ 2 δ I n − l 2 ≤ ω n ( ∥ F I n − l ( x n − l δ ) − y I n − l δ ∥ 2 − τ 2 δ I n − l 2 ) \left\|F_{I_{n-l}}(x_{n-l}^\delta)-y_{I_{n-l}}^\delta\right\|^2-\tau^2\delta_{I_{n-l}}^2 \le\omega_n\left(\left\|F_{I_{n-l}}(x_{n-l}^\delta)-y_{I_{n-l}}^\delta\right\|^2-\tau^2\delta_{I_{n-l}}^2\right) F I n − l ( x n − l δ ) − y I n − l δ 2 − τ 2 δ I n − l 2 ≤ ω n ( F I n − l ( x n − l δ ) − y I n − l δ 2 − τ 2 δ I n − l 2 )
for all n ≥ l n \ge l n ≥ l , because per definition ω n − l = 0 \omega_{n-l}=0 ω n − l = 0 iff the right hand side is negative and ω n − l = 1 \omega_{n-l}=1 ω n − l = 1 else. Together this results in
∑ l = 0 L δ − 1 ( ∥ F I n − l ( x n − l δ ) − y I n − l δ ∥ 2 − τ 2 δ I n − l 2 ) ≤ ∑ l = 0 L δ − 1 ω n ( ∥ F I n − l ( x n − l δ ) − y I n − l δ ∥ 2 − τ 2 δ I n − l 2 ) ≤ 0 \sum_{l=0}^{L_\delta-1}\left(\left\|F_{I_{n-l}}(x_{n-l}^\delta)-y_{I_{n-l}}^\delta\right\|^2-\tau^2\delta_{I_{n-l}}^2\right)
\le\sum_{l=0}^{L_\delta-1}\omega_n\left(\left\|F_{I_{n-l}}(x_{n-l}^\delta)-y_{I_{n-l}}^\delta\right\|^2-\tau^2\delta_{I_{n-l}}^2\right)\le0 l = 0 ∑ L δ − 1 ( F I n − l ( x n − l δ ) − y I n − l δ 2 − τ 2 δ I n − l 2 ) ≤ l = 0 ∑ L δ − 1 ω n ( F I n − l ( x n − l δ ) − y I n − l δ 2 − τ 2 δ I n − l 2 ) ≤ 0
for all n > N + L δ − 1 n>N+L_\delta-1 n > N + L δ − 1 . Hence n δ ≤ N + L δ < ∞ n_\delta\le N+L_\delta<\infty n δ ≤ N + L δ < ∞ which proves the statement.
Theorem 2.3 (A posteriori convergence). Let the assumptions of Theorem 2.2 hold and consider L δ ∈ N L_\delta\in\mathbb{N} L δ ∈ N , such that L δ → ∞ L_\delta\to\infty L δ → ∞ as δ ↘ 0 \delta\searrow0 δ ↘ 0 . Then for n δ ∈ N n_\delta\in\mathbb{N} n δ ∈ N chosen according to (10) , it holds
E [ ∥ x n δ δ − x ∗ ∥ 2 ] → 0 as δ ↘ 0. \mathbb{E}\left[\left\|x_{n_\delta}^\delta-x_\ast\right\|^2\right]\to0\text{ as }\delta\searrow0. E [ x n δ δ − x ∗ 2 ] → 0 as δ ↘ 0.
Proof. This is a direct consequence of Theorem 2.2 , since ∞ > n δ ≥ L δ → ∞ \infty>n_\delta\ge L_\delta\to\infty ∞ > n δ ≥ L δ → ∞ as δ ↘ 0 \delta\searrow0 δ ↘ 0 .
The condition L δ → ∞ L_\delta\to\infty L δ → ∞ is necessary to ensure that the probability of overlooking equations vanishes. As in the previous results, there is no growth condition needed on L δ L_\delta L δ due to the step control ω n \omega_n ω n in the definition of the method (8). However, in the next section will see, that it is well advised to control the parameter L δ L_\delta L δ .
Numerical illustration
In this section, the batched Kaczmarz-Landweber method is tested on a simulation of the electrical impedance tomography problem (EIT-problem). EIT is a type of medical imaging to determine the electrical conductivity inside a domain by boundary measurements of currents and voltages. The formulation in this paper is based on [5 ] . Consider the conductivity equation
− ∇ ⋅ ( σ ∇ u ) = 0. -\nabla\cdot(\sigma\nabla u) = 0. − ∇ ⋅ ( σ ∇ u ) = 0.
In the physical context, σ \sigma σ denotes the conductivity and u u u the voltage on a domain U ⊆ R d U \subseteq\mathbb{R}^{d} U ⊆ R d . The theoretical EIT-problem, also known as Calderón problem, is the parameter identification of the conductivity σ \sigma σ from the Neumann-to-Dirichlet map (N2D-map).
The N2D-map Λ σ ( g ) \Lambda_{\sigma}(g) Λ σ ( g ) is defined as boundary evaluation of the solution of the conductivity equation with Neumann boundary value g g g . I.e. Λ σ ( g ) : = u σ , g ∣ ∂ U \Lambda_{\sigma}(g) := u_{\sigma,g}|_{\partial U} Λ σ ( g ) := u σ , g ∣ ∂ U where u σ , g u_{\sigma,g} u σ , g is the unique solution of
{ − ∇ ⋅ ( σ ∇ u ) = 0 in U σ ∂ u ∂ n = g on ∂ U . (28) \begin{cases}
-\nabla\cdot(\sigma\nabla u) = 0 & \text{in } U \\
\sigma\frac{\partial u}{\partial n} = g & \text{on } \partial U. \tag*{(28)}
\end{cases} { − ∇ ⋅ ( σ ∇ u ) = 0 σ ∂ n ∂ u = g in U on ∂ U . (28)
Hence the forward operator of the EIT-problem F F F maps the conductivity σ \sigma σ to the N2D-map F : σ → Λ σ F : \sigma\to\Lambda_{\sigma} F : σ → Λ σ .
While the just defined forward operator corresponds to the problem with all Neumann input functions, a single measurement is given by F f ( σ ) : = F ( σ ) f F_f(\sigma) := F(\sigma)f F f ( σ ) := F ( σ ) f for Neumann input data f f f . For multiple Neumann input data f 1 , … , f p f_1,\ldots,f_p f 1 , … , f p the inverse problem corresponds to the prior introduced setting
F f i ( σ ) = y i i = 1 , … , p , F_{f_i}(\sigma) = y_i \quad i = 1,\ldots,p, F f i ( σ ) = y i i = 1 , … , p ,
with noisy data y i δ y_i^\delta y i δ satisfying
∥ y i δ − y i ∥ ≤ δ i . \left\|y_i^\delta-y_i\right\| \leq\delta_i. y i δ − y i ≤ δ i .
To formally define the operator we introduce the spaces with vanishing boundary integral H ⋄ 1 ( U ) \mathbf{H}^{1}_{\diamond}(U) H ⋄ 1 ( U ) and L ⋄ 2 ( ∂ U ) \mathbf{L}^{2}_{\diamond}(\partial U) L ⋄ 2 ( ∂ U ) . Using this spaces, the weak formulation of (28) is given by
∫ U σ ∇ u ∇ v d x = ∫ ∂ U g Tr v d S ∀ v ∈ H ⋄ 1 ( U ) , (29) \int_U \sigma\nabla u \nabla v \, \mathrm{d}x = \int_{\partial U} g \operatorname{Tr}v \, \mathrm{d}S \quad\forall v \in\mathbf{H}^{1}_{\diamond}(U), \tag*{(29)} ∫ U σ ∇ u ∇ v d x = ∫ ∂ U g Tr v d S ∀ v ∈ H ⋄ 1 ( U ) , (29)
where Tr : H 1 ( U ) → L 2 ( ∂ U ) \operatorname{Tr} : \mathbf{H}^{1}(U) \to\mathbf{L}^{2}(\partial U) Tr : H 1 ( U ) → L 2 ( ∂ U ) denotes the trace operator. We define the corresponding differential operator L σ : H ⋄ 1 ( U ) → H ⋄ − 1 ( U ) L_{\sigma} : \mathbf{H}^{1}_{\diamond}(U) \to\mathbf{H}^{-1}_{\diamond}(U) L σ : H ⋄ 1 ( U ) → H ⋄ − 1 ( U ) as L σ ( u ) = ∫ U σ ∇ u ∇ ⋅ d x L_{\sigma}(u) = \int_U \sigma\nabla u \nabla\cdot\, \mathrm{d}x L σ ( u ) = ∫ U σ ∇ u ∇ ⋅ d x . If σ ∈ D U \sigma\in\mathcal{D}_U σ ∈ D U , with
D U : = { σ ∈ L ∞ ( U ) : ess inf σ > 0 } . \mathcal{D}_U := \{\sigma\in\mathbf{L}^{\infty}(U) : \operatorname{ess\,inf} \sigma> 0\}. D U := { σ ∈ L ∞ ( U ) : ess inf σ > 0 } .
it can be shown, analogously to the Dirichlet setting in [13 Section 6.2.1] , by using the Lax-Milgram theorem and the Poincaré inequality, that L σ L_{\sigma} L σ is boundedly invertible. Using the dual map of the trace operator Tr ′ : L 2 ( ∂ U ) → H ⋄ − 1 ( U ) \operatorname{Tr}' : \mathbf{L}^{2}(\partial U) \to\mathbf{H}^{-1}_{\diamond}(U) Tr ′ : L 2 ( ∂ U ) → H ⋄ − 1 ( U ) the weak conductivity equation with Neumann boundary values (29) reduces to L σ u = Tr ′ g L_{\sigma}u = \operatorname{Tr}'g L σ u = Tr ′ g and hence has the unique solution u σ , g = L σ − 1 Tr ′ g u_{\sigma,g} = L_{\sigma}^{-1}\operatorname{Tr}'g u σ , g = L σ − 1 Tr ′ g for σ ∈ D U \sigma\in\mathcal{D}_U σ ∈ D U .
Therefore, the forward operator of the EIT-problem is formally defined as
F : D U ⊆ L ∞ ( U ) → L ( L ⋄ 2 ( ∂ U ) , L ⋄ 2 ( ∂ U ) ) with F ( σ ) = Tr L σ − 1 Tr ′ . F : \mathcal{D}_U \subseteq\mathbf{L}^{\infty}(U) \to\mathcal{L}(\mathbf{L}^{2}_{\diamond}(\partial U),\mathbf{L}^{2}_{\diamond}(\partial U)) \quad\text{with} \quad F(\sigma) = \operatorname{Tr}L_{\sigma}^{-1}\operatorname{Tr}'. F : D U ⊆ L ∞ ( U ) → L ( L ⋄ 2 ( ∂ U ) , L ⋄ 2 ( ∂ U )) with F ( σ ) = Tr L σ − 1 Tr ′ .
Using basic calculus we can show that the operator is Fréchet-differentiable with respect to the L ∞ \mathbf{L}^{\infty} L ∞ -norm and the derivative is given by
F ′ ( σ ) h = − Tr L σ − 1 L h L σ − 1 Tr ′ . F'(\sigma)h = -\operatorname{Tr}L_{\sigma}^{-1}L_hL_{\sigma}^{-1}\operatorname{Tr}'. F ′ ( σ ) h = − Tr L σ − 1 L h L σ − 1 Tr ′ .
However, the considered batched Landweber-Kaczmarz method requires the operator to be defined on a Hilbert space and the Fréchet-derivative does not extend to L 2 \mathbf{L}^{2} L 2 . Therefore we will work with Sobolev spaces H s ( U ) \mathbf{H}^{s}(\mathrm{U}) H s ( U ) based on the Fourier transform with s > 0 s > 0 s > 0 . This spaces are Hilbert spaces and continuously embed into L ∞ ( U ) L^{\infty}(\mathrm{U}) L ∞ ( U ) for s > d / 2 s > d/2 s > d /2 where d d d is the dimension of the underlying domain U \mathrm{U} U , see e.g. [1 Theorem 1.66] . Let now s > d / 2 s > d/2 s > d /2 , then the restricted operator F ∣ H s ( U ) F|_{\mathbf{H}^{s}(\mathrm{U})} F ∣ H s ( U ) is Fréchet-differentiable with respect to H s \mathbf{H}^{s} H s . Analogously the restricted forward operator with fixed Neumann data F f : D U ∩ H s ( U ) ⊆ H s ( U ) → L ⋄ 2 ( ∂ U ) F_f \colon\mathcal{D}_{\mathrm{U}} \cap\mathbf{H}^{s}(\mathrm{U}) \subseteq\mathbf{H}^{s}(\mathrm{U}) \to L^{2}_{\diamond}(\partial\mathrm{U}) F f : D U ∩ H s ( U ) ⊆ H s ( U ) → L ⋄ 2 ( ∂ U ) , defined as F f ( σ ) h = F ( σ ) f F_f(\sigma)h = F(\sigma)f F f ( σ ) h = F ( σ ) f , is Fréchet-differentiable with derivative
F f ′ ( σ ) h = − Tr L σ − 1 L h L σ − 1 Tr ′ f . (30) F'_f(\sigma)h = -\operatorname{Tr}L_{\sigma}^{-1}L_hL_{\sigma}^{-1}\operatorname{Tr}'f. \tag*{(30)} F f ′ ( σ ) h = − Tr L σ − 1 L h L σ − 1 Tr ′ f . (30)
The derivative can be interpreted as boundary evaluation F f ′ ( σ ) h = Tr u ~ F'_f(\sigma)h = \operatorname{Tr}\tilde{u} F f ′ ( σ ) h = Tr u ~ of the unique solution u ~ ∈ H ⋄ 1 ( U ) \tilde{u} \in\mathbf{H}^{1}_{\diamond}(\mathrm{U}) u ~ ∈ H ⋄ 1 ( U ) of the boundary value problem
{ − ∇ ⋅ ( σ ∇ u ~ ) = ∇ ⋅ ( h ∇ u σ , f ) in U , σ ∂ u ~ ∂ n = − h ∂ u σ , f ∂ n on ∂ U . \begin{cases}
-\nabla\cdot(\sigma\nabla\tilde{u}) = \nabla\cdot(h\nabla u_{\sigma,f}) & \text{in } \mathrm{U},\\
\sigma\dfrac{\partial\tilde{u}}{\partial n} = -h\dfrac{\partial u_{\sigma,f}}{\partial n} & \text{on } \partial\mathrm{U}.
\end{cases} ⎩ ⎨ ⎧ − ∇ ⋅ ( σ ∇ u ~ ) = ∇ ⋅ ( h ∇ u σ , f ) σ ∂ n ∂ u ~ = − h ∂ n ∂ u σ , f in U , on ∂ U .
Here again u σ , f = L σ − 1 Tr ′ f ∈ H ⋄ 1 ( U ) u_{\sigma,f} = L_{\sigma}^{-1}\operatorname{Tr}'f \in\mathbf{H}^{1}_{\diamond}(\mathrm{U}) u σ , f = L σ − 1 Tr ′ f ∈ H ⋄ 1 ( U ) is the solution to the conductivity equation (29) with boundary value f f f .
Since the derivative F f ′ F'_f F f ′ is continuous, the operator F f F_f F f fulfills Assumption 2.1 (ii). The boundedness of the Fréchet-derivative (Assumption 2.1 (iii)) is ensured by scaling the operator F f F_f F f properly. This means applying the method on adjusted data y ^ δ : = ( ρ 1 y f 1 δ , … , ρ p y f p δ ) \hat{y}^{\delta} := (\rho_1y^{\delta}_{f_1}, \ldots, \rho_py^{\delta}_{f_p}) y ^ δ := ( ρ 1 y f 1 δ , … , ρ p y f p δ ) , using the scaled operator F ^ : = ( ρ 1 F f 1 , … , ρ p F f p ) \hat{F} := (\rho_1F_{f_1}, \ldots, \rho_pF_{f_p}) F ^ := ( ρ 1 F f 1 , … , ρ p F f p ) with
ρ i = 1 p ⋅ 1 max { c F , sup σ ∈ D U s ∥ F f i ′ [ σ ] ∥ L ( H s ( U ) , L ⋄ 2 ( ∂ U ) ) } (31) \rho_i = \frac{1}{\sqrt{p}} \cdot\frac{1}{\max\left\{c_F,\sup_{\sigma\in\mathcal{D}_{\mathrm{U}}^{s}}\left\|F'_{f_i}[\sigma]\right\|_{\mathcal{L}(\mathbf{H}^{s}(\mathrm{U}),L^{2}_{\diamond}(\partial\mathrm{U}))}\right\}} \tag*{(31)} ρ i = p 1 ⋅ max { c F , sup σ ∈ D U s F f i ′ [ σ ] L ( H s ( U ) , L ⋄ 2 ( ∂ U )) } 1 (31)
where c F > 0 c_F > 0 c F > 0 is a positive constant. For the noise level δ ^ = ( δ ^ 1 , … , δ ^ p ) \hat{\delta} = (\hat{\delta}_1,\ldots,\hat{\delta}_p) δ ^ = ( δ ^ 1 , … , δ ^ p ) , this implies
∥ y ^ i − y ^ i δ ∥ ≤ ρ i δ i = : δ ^ i , i = 1 , … , p . \left\|\hat{y}_i-\hat{y}^{\delta}_i\right\| \leq\rho_i\delta_i =: \hat{\delta}_i,\qquad i=1,\ldots,p. y ^ i − y ^ i δ ≤ ρ i δ i =: δ ^ i , i = 1 , … , p .
The validity of Assumption 2.1 (iv), the tangential cone condition for EIT, is an open problem and only known in special cases (see [36 ] for a discussion).
To implement the Landweber-Kaczmarz iteration we use a discretization of the continuous Landweber step, i.e. evaluate the operator
σ n δ → σ n δ − ω n p b ∑ i ∈ I n F ^ f i ′ ( σ n δ ) ∗ ( F ^ f i ( σ n δ ) − y ^ i δ ) . \sigma_n^\delta\to\sigma_n^\delta-\omega_n\frac{p}{b}\sum_{i\in I_n}\hat{F}'_{f_i}(\sigma_n^\delta)^*(\hat{F}_{f_i}(\sigma_n^\delta)-\hat{y}^{\delta}_i). σ n δ → σ n δ − ω n b p i ∈ I n ∑ F ^ f i ′ ( σ n δ ) ∗ ( F ^ f i ( σ n δ ) − y ^ i δ ) .
For this we calculate the adjoint F f ′ ( σ ) ∗ F'_f(\sigma)^* F f ′ ( σ ) ∗ as
F f ′ ( σ ) ∗ g = − I H s ( U ) − 1 ( ⟨ ∇ u σ , f ∇ u σ , g , ⋅ ⟩ L 2 ( U ) ) . F'_f(\sigma)^*g=-\mathcal{I}_{\mathbf{H}^{s}(\mathrm{U})}^{-1}\left(\left\langle\nabla u_{\sigma,f}\nabla u_{\sigma,g},\cdot\right\rangle_{L^2(\mathrm{U})}\right). F f ′ ( σ ) ∗ g = − I H s ( U ) − 1 ( ⟨ ∇ u σ , f ∇ u σ , g , ⋅ ⟩ L 2 ( U ) ) .
Here again u σ , h = L σ − 1 Tr ′ h u_{\sigma,h}=L_{\sigma}^{-1}\operatorname{Tr}'h u σ , h = L σ − 1 Tr ′ h is the solution of the conductivity equation with Neumann boundary value h ∈ L ⋄ 2 ( ∂ U ) h\in L^2_{\diamond}(\partial\mathrm{U}) h ∈ L ⋄ 2 ( ∂ U ) (cf. (29) ) and I H s ( U ) : H s ( U ) → H s ( U ) ∗ \mathcal{I}_{\mathbf{H}^{s}(\mathrm{U})}\colon\mathbf{H}^{s}(\mathrm{U})\to\mathbf{H}^{s}(\mathrm{U})^* I H s ( U ) : H s ( U ) → H s ( U ) ∗ denotes the Riesz-operator of H s ( U ) \mathbf{H}^{s}(\mathrm{U}) H s ( U ) . The implementation uses the finite element method with p1-triangles to solve the boundary value problem and the discrete Fourier transform to approximate the Riesz-operator of H s ( U ) \mathbf{H}^{s}(\mathrm{U}) H s ( U ) . Note that the discretization of the continuous adjoint F f ′ ( σ ) ∗ F'_f(\sigma)^* F f ′ ( σ ) ∗ is just an approximation of the actual discrete adjoint.
We compare the batched discrepancy principle, introduced in this paper, with the classical discrepancy principle (5) . To simplify the notation of both termination criteria we define the discrepancy ratios as
R n b , L : = ∑ j = 0 L − 1 ∥ F ^ I n − j ( σ n − j δ ) − y ^ I n − j δ ∥ 2 ∑ j = 0 L − 1 δ ^ I n − j 2 and R n f u l l : = ∥ F ^ ( σ n δ ) − y ^ δ ∥ 2 δ ^ 2 . R_{n}^{b,L}:=\frac{\sum_{j=0}^{L-1}\left\|\hat{F}_{I_{n-j}}(\sigma_{n-j}^{\delta})-\hat{y}^{\delta}_{I_{n-j}}\right\|^{2}}{\sum_{j=0}^{L-1}\hat{\delta}_{I_{n-j}}^{2}}
\qquad\text{and}\qquad
R_{n}^{\mathrm{full}}:=\frac{\left\|\hat{F}(\sigma_{n}^{\delta})-\hat{y}^{\delta}\right\|^{2}}{\hat{\delta}^{2}}. R n b , L := ∑ j = 0 L − 1 δ ^ I n − j 2 ∑ j = 0 L − 1 F ^ I n − j ( σ n − j δ ) − y ^ I n − j δ 2 and R n full := δ ^ 2 F ^ ( σ n δ ) − y ^ δ 2 .
Using this notation, the iteration terminates at the first n ∈ N n \in\mathbb{N} n ∈ N with R n < τ 2 R_n < \tau^2 R n < τ 2 where R n ∈ { R n b , L , R n f u l l } R_n \in\{R_n^{b,L}, R_n^{\mathrm{full}}\} R n ∈ { R n b , L , R n full } . The final method is given in Algorithm 1. Note that the scaling factor ρ i \rho_i ρ i of equation (31) is simplified by using the operator norm of the current term F f i ′ ( σ n δ ) F_{f_i}'(\sigma_n^\delta) F f i ′ ( σ n δ ) instead of the supremum over all feasible conductivities.
Algorithm 1 Landweber-Kaczmarz algorithm for EIT
Choose a domain discretization (mesh and grid).
Select boundary functions f = ( f 1 , … , f p ) \mathbf{f}=(f_1,\ldots,f_p) f = ( f 1 , … , f p ) and pick an initial guess σ 0 ∈ D U \sigma_0 \in\mathcal{D}_U σ 0 ∈ D U .
Choose τ > 1 \tau>1 τ > 1 and c F > 0 c_F>0 c F > 0 appropriately.
Select the discrepancy type R n ∈ { R n b , L , R n f u l l } R_n \in\{R_n^{b,L}, R_n^{\mathrm{full}}\} R n ∈ { R n b , L , R n full } , batch size b ≤ p b \le p b ≤ p and aggregation length L L L .
for n = 0 , 1 , … n=0,1,\ldots n = 0 , 1 , … do
Randomly select batch I n = { i 1 , … , i b } ⊆ { 1 , … , p } I_n=\{i_1,\ldots,i_b\}\subseteq\{1,\ldots,p\} I n = { i 1 , … , i b } ⊆ { 1 , … , p } with ∣ I n ∣ = b \lvert I_n\rvert=b ∣ I n ∣ = b via uniform distribution.
ρ i , n ← \rho_{i,n}\leftarrow ρ i , n ← Approximation of max { c F , ∥ F f i ′ ( σ n δ ) ∥ L ( H s ( U ) , L ⋄ 2 ( ∂ U ) ) } − 1 \max\{c_F,\lVert F_{f_i}'(\sigma_n^\delta)\rVert_{\mathcal{L}(H^s(U),L_\diamond^2(\partial U))}\}^{-1} max { c F , ∥ F f i ′ ( σ n δ ) ∥ L ( H s ( U ) , L ⋄ 2 ( ∂ U )) } − 1 using the power method
if R n < τ 2 R_n<\tau^2 R n < τ 2 then
Terminate iteration. ▷ Take σ n δ \sigma_n^\delta σ n δ as approximate solution.
end if
σ n + 1 δ ← σ n δ − 1 b ∑ i ∈ I n ρ i , n 2 F f i ′ ( σ n δ ) ∗ ( F f i ( σ n ) − y i δ ) \sigma_{n+1}^\delta\leftarrow\sigma_n^\delta-\frac{1}{b}\sum_{i\in I_n}\rho_{i,n}^2F_{f_i}'(\sigma_n^\delta)^*\left(F_{f_i}(\sigma_n)-y_i^\delta\right) σ n + 1 δ ← σ n δ − b 1 ∑ i ∈ I n ρ i , n 2 F f i ′ ( σ n δ ) ∗ ( F f i ( σ n ) − y i δ )
end for
Simulation details
We consider a two-dimensional test function defined as
σ ˉ ( x , y ) = 1.605 − 0.05 sin ( 2 x ) − 0.25 sin ( 2 y ) − 0.25 sin ( 1.81 x + 0.85 y ) + 0.08 sin ( 4 x ) − 0.025 sin ( 4 y ) − 0.15 sin ( 3.24 x + 2.35 y ) \bar{\sigma}(x,y)=1.605-0.05\sin(2x)-0.25\sin(2y)-0.25\sin(1.81x+0.85y)
+0.08\sin(4x)-0.025\sin(4y)-0.15\sin(3.24x+2.35y) σ ˉ ( x , y ) = 1.605 − 0.05 sin ( 2 x ) − 0.25 sin ( 2 y ) − 0.25 sin ( 1.81 x + 0.85 y ) + 0.08 sin ( 4 x ) − 0.025 sin ( 4 y ) − 0.15 sin ( 3.24 x + 2.35 y )
on the domain U = { ( x , y ) : x 2 + y 2 ≤ 4 } U=\{(x,y):x^2+y^2\le4\} U = {( x , y ) : x 2 + y 2 ≤ 4 } (see the left panel of Figure 1 ). The function is smooth and hence σ ˉ ∈ H s ( U ) \bar{\sigma}\in H^s(U) σ ˉ ∈ H s ( U ) for s > 1 s>1 s > 1 . In the experiments we will work with s : = 1.01 s:=1.01 s := 1.01 . The domain
Figure 1. Example setting: exact conductivity σ ˉ \bar{\sigma} σ ˉ (left) and selected Neumann input functions f i f_i f i with the corresponding boundary data y i y_i y i (right). Shown are 6 of the p = 182 p=182 p = 182 input/output pairs.
is discretized by an equidistant grid with 64 × 64 64\times64 64 × 64 grid points and the finite element method is based on a triangular mesh with 792 degree of freedom. The mesh implies a grid on the boundary with 184 grid points. Hence as Neumann input functions we select N = 182 N=182 N = 182 basis functions of L ⋄ 2 ( ∂ U ) L^2_{\diamond}(\partial U) L ⋄ 2 ( ∂ U ) , i.e.
B ∂ U N : = { b ∈ L ⋄ 2 ( ∂ U ) : b ( t ) = sin ( n t ) or b ( t ) = cos ( n t ) with n = 1 , … , ⌊ N / 2 ⌋ } \mathcal{B}_{\partial U}^{N}:=\left\{b\in L^2_{\diamond}(\partial U):b(t)=\sin(nt)\text{ or }b(t)=\cos(nt)\text{ with }n=1,\ldots,\left\lfloor N/2\right\rfloor\right\} B ∂ U N := { b ∈ L ⋄ 2 ( ∂ U ) : b ( t ) = sin ( n t ) or b ( t ) = cos ( n t ) with n = 1 , … , ⌊ N /2 ⌋ }
where t : ∂ U → [ 0 , 2 π ) t:\partial U\to[0,2\pi) t : ∂ U → [ 0 , 2 π ) corresponds to a uniform parametrization of the boundary (see the right panel of Figure 1 ).
The experiments are applied on simulated data. First the discretized forward operator is evaluated for the exact conductivity and then a Gaussian noise is added to the data. In the simulation, the model error is neglected by using the same discretization for both simulation and iteration. This allows the use of high-frequency basis functions, in which the model error dominates.
To test the Landweber-Kaczmarz method, we start with the constant function σ 0 ≡ 1 \sigma_0\equiv1 σ 0 ≡ 1 , get an iteration σ n δ \sigma_n^\delta σ n δ and terminate either if the full or batched discrepancy principle holds for the parameter τ = 1.05 \tau=1.05 τ = 1.05 . Since all other parameters are fixed, the iteration σ n δ \sigma_n^\delta σ n δ depends only on the batch size b b b . However, due to the randomness in the selection of the batch, the same parameter choice will not produce the same results. Hence, the experiments are carried out multiple times. Note that due to the Gaussian noise, here with a noise level of 5%, the data also has a random component. This randomness is not addressed in the experiments; instead the same data is used for each run.
Results
In Figure 2 the total results are plotted and Figure 3 shows selected reconstructions.
Figure 2. Relative L 2 L^2 L 2 -error of the final iterates versus the number of PDE-solves for the classical and the batched discrepancy principle with different batch sizes and aggregation lengths L L L .
Figure 3. Reconstruction of the classical Landweber method and selected reconstructions of the batched Landweber-Kaczmarz method with b ∈ { 1 , 20 } b \in\{1,20\} b ∈ { 1 , 20 } and L ∈ { 1 , 200 } L \in\{1,200\} L ∈ { 1 , 200 } . Below each reconstruction the relative L 2 L^2 L 2 -error and the computation time are given.
The computation speed is measured by the number of PDE-solves. For p p p number of functions and batch size b b b the number of PDE-solves per iteration is given by
n P D E = { 2 b if the batched discrepancy is used b + p if the classical discrepancy is used. n_{\mathrm{PDE}}=\begin{cases}
2b & \text{if the batched discrepancy is used}\\
b+p & \text{if the classical discrepancy is used.}
\end{cases} n PDE = { 2 b b + p if the batched discrepancy is used if the classical discrepancy is used.
Note, that the largest part of the computational effort of Algorithm 1 lies in solving the PDEs. Figure 2 shows that the quality and computational effort of the reconstructions using the batched discrepancy principle depend significantly on the parameters L L L and b b b . For a larger batch size b b b , the variance decreases, but at the same time more PDE-solves are required. For a larger aggregation length L L L the iteration terminates later and hence yields better results. An exception are the light blue points with n P D E ≈ 10 5 n_{\mathrm{PDE}} \approx10^5 n PDE ≈ 1 0 5 and relative error ≈ 0.08 \approx0.08 ≈ 0.08 . Here one observes that in some runs the stopping criterion fails, terminating only when leaving the range of definition δ n σ ∉ D U \delta_n^\sigma\notin D_U δ n σ ∈ / D U . This is a purely numerical issue; in total the results show: For a proper choice of parameters L L L and b b b the batched discrepancy principle yields equally good approximations as the classical discrepancy principle at significantly lower computation cost. In our problem the best choice is batch size b = 1 b=1 b = 1 and aggregation length L ≈ 150 L \approx150 L ≈ 150 .
The same effects can be observed in Figure 3 showing the selected reconstructions compared with the classical Landweber method. To explain the reason behind the influence of the parameters
on the results we plotted the batched and classical discrepancy ratio over the iteration index n n n for b ∈ { 1 , 20 } b \in\{1,20\} b ∈ { 1 , 20 } and L ∈ { 1 , 200 } L \in\{1,200\} L ∈ { 1 , 200 } (Figure 4 ). Here we observe, that for batch size b = 20 b=20 b = 20 the ratio is less scattered than for batch size b = 1 b=1 b = 1 . In the plots with L = 1 L=1 L = 1 , one can also see that, as explained in § 2.2.1 , the batched discrepancy for L = 1 L=1 L = 1 is an unbiased estimator of the classical discrepancy. However, in this case the batched ratio has a large variance, hence the approximation of the classical ratio is unstable and the stopping too early. The problem is solved choosing larger values of L L L , which gives a reduced variance, but an additional error occurs due to the consideration of previous iterates. The plots of L = 200 L=200 L = 200 show, that the additional error is limited to the first iterates. For later iterates the batched ratio yields a good approximation of the classical ratio and therefore similar stopping at lower computational cost.
Figure 4. Batched and classical discrepancy ratio R n b , L R_n^{b,L} R n b , L , R n f u l l R_n^{\mathrm{full}} R n full over the iteration index n n n for b ∈ { 1 , 20 } b \in\{1,20\} b ∈ { 1 , 20 } and L ∈ { 1 , 200 } L \in\{1,200\} L ∈ { 1 , 200 } . The vertical lines mark the stopping indices of the batched and the classical discrepancy principle.
Concluding Remarks
In this work, we analyzed a stochastic mini-batch Landweber-Kaczmarz method with a new a posteriori stopping: the batched discrepancy principle. Under the tangential cone condition we proved the regularization properties for a priori stopping and the introduced batched discrepancy principle. Numerical experiments for the electrical impedance tomography problem show that: For a proper choice of the aggregation parameter L L L and the batch size b b b , the batched discrepancy principle yields equally good approximations as the classical discrepancy principle at significantly lower computational cost. Building on our work, there are some questions that might be considered for future research:
Can the method be generalized to a Banach space setup, i.e. the parameter space X X X and/or data spaces Y i Y_i Y i are Banach spaces? This will cover inverse problems with nonsmooth solutions.
What convergence rates can be proven?
How does the method extend to accelerations, like for example the Nesterov acceleration?
Acknowledgment
Rommel R. Real is supported by Centre International de Mathématiques Pures et Appliquées (CIMPA) and the Abdus Salam International Centre for Theoretical Physics (ICTP) through the CIMPA-ICTP Research in Pairs fellowship programme.
Disclaimer
During the writing of this paper, artificial intelligence was used for graphic design and proofreading parts of the manuscript. We carefully checked all AI suggested content and take full responsibility for all mathematical content, software, numerical results, interpretations and conclusions.