Frozen Newton rates under differential range invariance

Assume the structural hypotheses of the frozen Newton one-step error lemma hold with fixed constants and notation. Let the initial pair be $({\widehat{r}}_0,x_0)\in \tilde{U}\times U$, where $x_0$ is the basepoint from the range-invariance factorization. At step $n\ge 1$, freeze the objective at the previous iterate $x_{n-1}$, use parameters ${\alpha }_n$ and ${\beta }_n=c_{\beta \alpha }{\alpha }_n$, and let $({\widehat{r}}_n,x_n)$ satisfy the resulting approximate-minimum inequality. Let $E_n$ and $S_n$ be the error and residual quantities from the one-step lemma for this step, with its input iterate relabeled $x_{n-1}$ and output iterate relabeled $x_n$. Define $E_0:=\frac{c_{\beta \alpha }}{C_{\psi }}(\lambda \mathrm{\parallel }{\widehat{r}}_0-r(x^{†}){\mathrm{\parallel }}_Z^p+t\mathrm{\parallel }r(x_0)-r(x^{†}){\mathrm{\parallel }}_Z^p)$. The parameter sequence $({\alpha }_n{)}_{n\ge 1}$ and the associated $h_n,{\rho }_n$ are fixed independently of $\delta$. Write

$H(q):={\sup }_{s\ge 0}(\psi (s)-qs),h_n:=H\text{\hspace{0.17em}⁣}\left(\frac{1}{2\bar{C}{\alpha }_n}\right),{\rho }_n:={\alpha }_n{h}_n,q:=\frac{v}{t},$

where $t,v,\bar{C}$ are as in that lemma. Let ${\alpha }_n>0$ decrease strictly to zero, suppose $h_n$ is finite and positive, ${\rho }_n$ decreases strictly to zero, and assume for some $C_H\ge 1$ that

$h_n\le C_H{h}_{n+1}(n\ge 1),q{C}_H<1.$

Assume each step through $N$ satisfies the one-step lemma, has tolerance ${\eta }_n\le C_{\eta }{\rho }_n$, and the initial error $E_0$ is finite. Assume also that for every sufficiently small $\delta >0$ there is an index $N=N(\delta )\ge 2$ such that

${\rho }_N\ge \tau {\delta }^p,{\rho }_N\le M\tau {\delta }^p,{\rho }_n\ge \tau {\delta }^p(1\le n\le N),$

for constants $\tau ,M>0$ independent of $\delta$. This bounded crossing condition is satisfied, for example, if $N$ is the last index with ${\rho }_N\ge \tau {\delta }^p$ and ${\rho }_n\mathrm{/}{\rho }_{n+1}\le M$ for all $n$.

Then the stopping iterate $({\widehat{r}}_N,x_N)$ satisfies

$E_N=O(h_N),S_N=O({\delta }^p),$

and therefore

$\mathrm{\parallel }{\widehat{r}}_N-r(x^{†}){\mathrm{\parallel }}_Z^p+\mathrm{\parallel }r(x_N)-r(x^{†}){\mathrm{\parallel }}_Z^p=O(h_N),$

$\mathrm{\parallel }K({\widehat{r}}_N-r(x^{†})){\mathrm{\parallel }}_Y=O(\delta ),\mathrm{\parallel }P{x}_N{\mathrm{\parallel }}_X=O(\delta ),\mathrm{\parallel }K{\widehat{r}}_N+F(x_0)-y^{\delta }{\mathrm{\parallel }}_Y=O(\delta )\mathrm{.}$

If $\mathrm{\Phi }(a):=aH(1\mathrm{/}(2\bar{C}a))$ has a strictly increasing inverse $\varphi$ on the relevant range, then

$h_N\le H\text{\hspace{0.17em}⁣}\left(\frac{1}{2\bar{C}\varphi (M\tau {\delta }^p)}\right),$

which gives the corresponding source-index rate for the range-variable and nonlinear-range errors.

For the following three-dimensional EIT specialization, assume the Axiom of Choice, Countable Choice and Dependent Choice. Let $\mathrm{\Omega }=B_1\subset {\mathbb{R}}^3$, let the known conductivity be $1$ outside $B_{\rho }⋐B_1$, impose fixed positive upper and lower conductivity bounds, use the exact intrinsic quadratic $H^{s_1}(\mathrm{\Omega })$ penalty with $s_1\in (5\mathrm{/}2,7\mathrm{/}2)$, and assume ${\sigma }^{†}\in B_{2,\mathrm{\infty }}^{s_2}(\mathrm{\Omega })$ for $s_2\in (s_1,2s_1-1)$. Use the centered mean-zero Neumann voltage map in $Y={\mathrm{\ell }}^2(L^2(S^2))$ and the explicit observation augmentation, admitted neighborhood $U$, penalty $R_P$, and linked-parameter constants in the EIT compatibility lemma. Choose the initial conductivity sufficiently close to the truth that its radius condition $LR<c_{\mathrm{t}\mathrm{c}\mathrm{r}}<1\mathrm{/}\sqrt{20}$ holds, and choose a fixed initial range variable in $r(U)$, independently of noise. Put

$\nu =\frac{(s_2-s_1)(2s_1-3)}{s_2-1},L_{\delta }=\log (1\mathrm{/}\delta )\mathrm{.}$

Take a fixed geometric parameter sequence, starting sufficiently far down its tail that the conjugate growth condition above holds, set ${\beta }_n=c_{\beta \alpha }{\alpha }_n$, and use admitted approximate steps with ${\eta }_n\le C_{\eta }{\rho }_n$. For a positive target $w_{\delta }$, stop at the last index $N$ with ${\rho }_N\ge \tau w_{\delta }$. If the actual squared data noise is $O(w_{\delta })$, then

$\mathrm{\parallel }{\sigma }_N-{\sigma }^{†}{\mathrm{\parallel }}_{H^{s_1}(\mathrm{\Omega })}=O(L_{\delta }^{-\nu \mathrm{/}2}),\mathrm{\parallel }{z}_N{\mathrm{\parallel }}_Y=O(\sqrt{w_{\delta }}),\mathrm{\parallel }K{\widehat{r}}_N+F(x_0)-y^{\delta }{\mathrm{\parallel }}_Y=O(\sqrt{w_{\delta }})$

in each of the following regimes: $w_{\delta }={\delta }^2$ for the balanced choice ${\alpha }_N\asymp {\delta }^2{L}_{\delta }^{\nu }$ and ordinary noise bounded by $\delta$; $w_{\delta }={\delta }^k{L}_{\delta }^{-\nu }$ for every $0<k<2$, giving ${\alpha }_N\asymp {\delta }^k$ under the same ordinary noise bound; and $w_{\delta }={\delta }^2{L}_{\delta }^{-\nu }$ for the nominal endpoint ${\alpha }_N\asymp {\delta }^2$, under the explicit stronger actual-noise condition $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_Y^2=O({\delta }^2{L}_{\delta }^{-\nu })$. All tolerances remain bounded by $C_{\eta }{\rho }_n$ through the stopping index. Thus the total conductivity and artificial-voltage norm error has logarithmic exponent $\nu \mathrm{/}2$ in every stated regime.

Frozen-step error and residual inequality

Barbara Kaltenbacher, Convergence rates under a range invariance condition with application to electrical impedance tomography, Theorem 7 and equations (2.31)–(2.41)

Frederic Weidling, Variational Source Conditions and Conditional Stability Estimates for Inverse Problems in PDEs, Theorem 2.20

Christian Clason, Regularization of Inverse Problems, Theorem 10.7

The Axiom of Choice

The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)

The axiom of dependent choice: a relation in which every element is related to something admits an $\mathbb{N}$-indexed chain

The full collared EIT class satisfies the centered range and source interfaces

Logarithmic source indices and their admissible parameter scales

Geometric parameters satisfy the logarithmic frozen stopping and growth conditions