Anchored IRGNM local source-condition convergence with ordinary discrepancy stopping

The hypotheses give $\theta <1$, $0\le b<q^{\beta }<1$, so all constants are finite and positive except possibly $b,d_0,\theta$. By [F3], $\mathrm{\parallel }{e}_0\mathrm{\parallel }\le W\mathrm{\parallel }A{\mathrm{\parallel }}^{2\nu }\le W{\alpha }_0^{\nu }<\rho$ and $v_0:=\mathrm{\parallel }A{e}_0\mathrm{\parallel }\le W{\alpha }_0^{\beta }$. If $X=\{0\}$, or $A=0$, the source condition gives $e_0=0$; more generally whenever $e_0=0$ the actual noisy algorithm stops at index zero since its residual is at most $\delta$. Its conclusion is exact. The extended recurrence is still treated by the estimates below, including in these cases, rather than assumed to stop.

Suppose a theoretical current iterate lies in $B$ and $v_k\le DW{\alpha }_k^{\beta }+E\delta$. The inverse [F4] defines its next exact step in $X$ before any next-domain assertion. The residual inequality [F2] yields $v_{k+1}\le aW{\alpha }_k^{\beta }+b{v}_k+c\delta \le (a+bD)W{\alpha }_k^{\beta }+(bE+c)\delta \le DW{\alpha }_{k+1}^{\beta }+E\delta$, since $D(q^{\beta }-b)\ge a$ and $E(1-b)=c$. Here $v_{k+1}=\mathrm{\parallel }A(x_{k+1}-x^{†})\mathrm{\parallel }$ is defined even before proving the next state lies in $B$.

Under step 1.2's conditions, substitute its bounds for $v_k,v_{k+1}$ into [F2]'s error inequality. As $\beta -1\mathrm{/}2=\nu$, this gives $\mathrm{\parallel }{e}_{k+1}\mathrm{\parallel }\le [1+D(d_0+\theta q^{\beta })\mathrm{/}2]W{\alpha }_k^{\nu }+[c_0+(d_0+\theta )E]\delta \mathrm{/}(2\sqrt{{\alpha }_k})=C_{e}W{\alpha }_k^{\nu }+N_e\delta \mathrm{/}\sqrt{{\alpha }_k}$. Thus the source term has its actual filtered power, not an inverse-shift estimate of the initial norm.

By [F6], $K_{\delta }$ exists and is positive. For every $j<K_{\delta }$, $\delta <W{\alpha }_j^{\beta }$, so step 2.1 gives $\mathrm{\parallel }{e}_{j+1}\mathrm{\parallel }\le (C_e+N_e)W{\alpha }_j^{\nu }\le (C_e+N_e)W{\alpha }_0^{\nu }<\rho$. Start at step 1.1 and induct: at stage $j$ the current state is already in $B$, so [F4] and step 1.2 define the next state and its residual bound, and the displayed estimate places it in $B$. This proves the extension, ball preservation and both stated estimates through $K_{\delta }$ without any future-ball assumption. For exact data the same induction runs for every $j$ with noise zero, and the error estimate with [F6] gives convergence of the exact extension to $x^{†}$.

The upper residual comparison in [F2] and step 3.1 give $\mathrm{\parallel }F(x_{K_{\delta }}^{\delta })-y_{\delta }\mathrm{\parallel }\le (1+\kappa )v_{K_{\delta }}+\delta \le [(1+\kappa )(D+E)+1]\delta <\tau \delta$. Thus the first crossing exists by $K_{\delta }$. Until its first crossing the actual finite algorithm uses exactly the extended recurrence, so with a sufficient cap and successful exact calls its return equals this crossing. No property of an arbitrary budget-final iterate follows.

For $1\le k_{\delta }\le K_{\delta }$, minimality of $K_{\delta }$ gives $W{\alpha }_{K_{\delta }-1}^{\beta }>\delta$ and hence $\delta \mathrm{/}\sqrt{{\alpha }_{k_{\delta }-1}}\le \delta \mathrm{/}\sqrt{{\alpha }_{K_{\delta }-1}}<W^{1\mathrm{/}(2\beta )}{\delta }^{1-1\mathrm{/}(2\beta )}\to 0$, since $\beta >1\mathrm{/}2$. Along any sequence with $k_{\delta }\to \mathrm{\infty }$, also ${\alpha }_{k_{\delta }-1}^{\nu }\to 0$ by [F6]. The error bound in step 3.1 therefore proves stopped convergence along such sequences.

For each fixed index $j$, the extended iterates depend continuously on the datum near $y$. Indeed, the exact states for data $y$ lie strictly inside $B$ by step 3.1. Inductively $F,F^{\mathrm{\prime }}$ and the adjoint/product laws [F5] are continuous there; for fixed positive ${\alpha }_j$, the inverse identity $B_1^{-1}-B_2^{-1}=B_1^{-1}(B_2-B_1)B_2^{-1}$ and [F4]'s $1\mathrm{/}{\alpha }_j$ bounds prove continuity of each normal inverse. Thus $x_j^{\delta }\to x_j^0$. If a stopping subsequence has fixed index $j$, its discrepancy bound implies $F(x_j^0)=y$. The lower residual comparison in [F2] then gives $A(x_j^0-x^{†})=0$.

By [F3], $e_0\perp \ker A$. Testing the anchored error equation $(A_k^{\ast }{A}_k+{\alpha }_{k}I)e_{k+1}={\alpha }_k{e}_0+A_k^{\ast }(y_{\delta }-y+t_k)$ against $h\in \ker A$ gives $⟨e_{k+1},h⟩=⟨e_0,h⟩=0$, because factorization gives $A_{k}h=0$. Hence every exact error lies in $(\ker A{)}^{\perp }$. The exact error in step 5.2 also lies in $\ker A$, so it is zero. This includes $j=0$ and proves convergence along every bounded-index stopping subsequence by taking a constant-index further subsequence.

If stopped convergence failed for some admissible noise sequence, take a sequence of errors bounded away from zero. Its stopping indices have either an unbounded subsequence, along which a further strictly increasing subsequence contradicts step 5.1, or a bounded subsequence, with a constant-index further subsequence contradicting step 6.1. Thus stopped convergence holds for every admissible noise family. This proof never assumes $k_{\delta }\to \mathrm{\infty }$ in all cases.