Data, operator, discretization, and solve errors

Let $X,Y$ be real or complex Hilbert spaces over the same scalar field, let $A:X\to Y$ be a compact linear forward map (the closure of $A(B)$ is compact in $Y$ for every bounded set $B\subseteq X$), and let $A_h:X\to Y$ be a bounded linear discretized map with finite-dimensional range. For a datum $b\in Y$, let $\lambda >0$ be the coefficient of $\mathrm{\parallel }x{\mathrm{\parallel }}_X^2$ in the Tikhonov objective $\mathrm{\parallel }Ax-b{\mathrm{\parallel }}_Y^2+\lambda \mathrm{\parallel }x{\mathrm{\parallel }}_X^2$. Supply adjoints $A^{\ast }:Y\to X$ and $A_h^{\ast }:Y\to X$ satisfying $⟨Ax,y{⟩}_Y=⟨x,A^{\ast }y{⟩}_X$ and $⟨A_{h}x,y{⟩}_Y=⟨x,A_h^{\ast }y{⟩}_X$, where the inner products are linear in their first arguments. Assume the shifted normal operators $A^{\ast }A+\lambda I_X$ and $A_h^{\ast }{A}_h+\lambda I_X$ are bijective, and define $R_{\lambda }=(A^{\ast }A+\lambda I_X{)}^{-1}{A}^{\ast },R_{\lambda ,h}=(A_h^{\ast }{A}_h+\lambda I_X{)}^{-1}{A}_h^{\ast }\mathrm{.}$

For a truth $x^{†}\in X$, data perturbation $e\in Y$, and $\delta \ge 0$ with $\mathrm{\parallel }e\mathrm{\parallel }\le \delta$, put $y=A{x}^{†},y_{\delta }=y+e,y_{h,\delta }=A_h{x}^{†}+e,d_h=(A-A_h)x^{†}=y_{\delta }-y_{h,\delta }\mathrm{.}$ For any returned output ${\tilde{x}}_h\in X$, define its exact discrete normal-equation residual by $r_{h,h}=(A_h^{\ast }{A}_h+\lambda I_X){\tilde{x}}_h-A_h^{\ast }{y}_{h,\delta }\mathrm{.}$ The five-channel error budget is the ordered tuple $(b_{\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}},b_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}},b_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}},b_{\mathrm{p}\mathrm{r}\mathrm{e}},b_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}})$, where $\begin{array}{rl}{\displaystyle b_{\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}}}& {\displaystyle =x^{†}-R_{\lambda }y,b_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}=R_{\lambda }y-R_{\lambda }{y}_{\delta },}\\ {\displaystyle b_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}}}& {\displaystyle =(R_{\lambda }-R_{\lambda ,h})y_{h,\delta },b_{\mathrm{p}\mathrm{r}\mathrm{e}}=R_{\lambda }{d}_h,}\\ {\displaystyle b_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}}}& {\displaystyle =R_{\lambda ,h}{y}_{h,\delta }-{\tilde{x}}_h\mathrm{.}}\end{array}$ The five entries are, in order, the truth-bias, data-perturbation, regularized-operator, pre-inversion, and algebraic-solve error vectors. The scalar total budget is the sum of the five channel norms. The raw pre-inversion forward residual is $d_h$; its reconstruction contribution is $b_{\mathrm{p}\mathrm{r}\mathrm{e}}$. The operator channel measures the difference between the regularized exact and discretized operators. The solve channel measures the returned output's difference from the exact discrete Tikhonov output. The definition supplies no rate or arithmetic residual certificate.

Compact Hilbert-space inverse model

Clason, Regularization of Inverse Problems, Chapter 8

Hansen, Introduction to Inverse Problems, Chapter 5

Van Leeuwen and Brune, 10 Lectures on Inverse Problems and Imaging, Chapter 3

Assume Countable Choice, meaning every sequence of nonempty sets has a choice function. Let $X,Y$ be real or complex Hilbert spaces over the same scalar field, let $A:X\to Y$ be compact and linear (the closure of $A(B)$ is compact in $Y$ for every bounded set $B\subseteq X$), and let $A_h:X\to Y$ be bounded and linear with finite-dimensional range. Let $A^{\ast }:Y\to X$ and $A_h^{\ast }:Y\to X$ be their Hilbert adjoints, characterized by $⟨Ax,z{⟩}_Y=⟨x,A^{\ast }z{⟩}_X$ and $⟨A_{h}x,z{⟩}_Y=⟨x,A_h^{\ast }z{⟩}_X$, with both inner products linear in the first argument. Let $\lambda >0$, $x^{†}\in X$, $e\in Y$, $\delta \ge 0$ with $\mathrm{\parallel }e{\mathrm{\parallel }}_Y\le \delta$, and ${\tilde{x}}_h\in X$. Put $y=A{x}^{†},y_{\delta }=y+e,y_{h,\delta }=A_h{x}^{†}+e,d_h=(A-A_h)x^{†}=y_{\delta }-y_{h,\delta }\mathrm{.}$ $R_{\lambda }=(A^{\ast }A+\lambda I_X{)}^{-1}{A}^{\ast },R_{\lambda ,h}=(A_h^{\ast }{A}_h+\lambda I_X{)}^{-1}{A}_h^{\ast },$ where $I_X$ is the identity operator on $X$, and $r_{h,h}=(A_h^{\ast }{A}_h+\lambda I_X){\tilde{x}}_h-A_h^{\ast }{y}_{h,\delta }\mathrm{.}$ Define $\begin{array}{rlrl}{\displaystyle b_{\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}}}& {\displaystyle =x^{†}-R_{\lambda }y,}& {\displaystyle b_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}}& {\displaystyle =R_{\lambda }y-R_{\lambda }{y}_{\delta },}\\ {\displaystyle b_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}}}& {\displaystyle =(R_{\lambda }-R_{\lambda ,h})y_{h,\delta },}& {\displaystyle b_{\mathrm{p}\mathrm{r}\mathrm{e}}}& {\displaystyle =R_{\lambda }{d}_h,}\\ {\displaystyle b_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}}}& {\displaystyle =R_{\lambda ,h}{y}_{h,\delta }-{\tilde{x}}_h\mathrm{.}}\end{array}$ Then the exact error identity and its triangle bound are $x^{†}-{\tilde{x}}_h=b_{\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}}+b_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}+b_{\mathrm{p}\mathrm{r}\mathrm{e}}+b_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}}+b_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}},$ $\mathrm{\parallel }{x}^{†}-{\tilde{x}}_h\mathrm{\parallel }\le \mathrm{\parallel }{b}_{\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}}\mathrm{\parallel }+\mathrm{\parallel }{b}_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}\mathrm{\parallel }+\mathrm{\parallel }{b}_{\mathrm{p}\mathrm{r}\mathrm{e}}\mathrm{\parallel }+\mathrm{\parallel }{b}_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}}\mathrm{\parallel }+\mathrm{\parallel }{b}_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}}\mathrm{\parallel },$ and the four displayed term estimates give $\mathrm{\parallel }{x}^{†}-{\tilde{x}}_h\mathrm{\parallel }\le \mathrm{\parallel }{b}_{\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}}\mathrm{\parallel }+\frac{\delta }{2\sqrt{\lambda }}+\frac{\mathrm{\parallel }{d}_h\mathrm{\parallel }}{2\sqrt{\lambda }}+\mathrm{\parallel }{b}_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}}\mathrm{\parallel }+\frac{\mathrm{\parallel }{r}_{h,h}\mathrm{\parallel }}{\lambda }\mathrm{.}$ If $\mathrm{\parallel }{R}_{\lambda }-R_{\lambda ,h}{\mathrm{\parallel }}_{Y\to X}\le {\eta }_{\lambda ,h}$, where the induced operator norm for a bounded linear map $T:Y\to X$ is $\mathrm{\parallel }T{\mathrm{\parallel }}_{Y\to X}:={\sup }_{u\in Y,\mathrm{\parallel }u{\mathrm{\parallel }}_Y\le 1}\mathrm{\parallel }Tu{\mathrm{\parallel }}_X,$ then $\mathrm{\parallel }{b}_{\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}}\mathrm{\parallel }\le {\eta }_{\lambda ,h}\mathrm{\parallel }{y}_{h,\delta }{\mathrm{\parallel }}_Y$. If a residual evaluation separately supplies ${\widehat{r}}_{h,h}\in X$ and ${\rho }_{h,h}\ge 0$ with $\mathrm{\parallel }{\widehat{r}}_{h,h}-r_{h,h}{\mathrm{\parallel }}_X\le {\rho }_{h,h}$, then the final solve term is at most $(\mathrm{\parallel }{\widehat{r}}_{h,h}{\mathrm{\parallel }}_X+{\rho }_{h,h})\mathrm{/}\lambda$. These pointwise bounds assert no convergence rate as the data, regularization parameter, or discretization changes.

Compact Hilbert-space inverse model

Hilbert adjoint and inner-product convention

Countable Choice hypothesis

Induced operator norm

Five-channel Tikhonov error budget

Exact telescoping chain and conditional error bounds

Finite-matrix residual certificate and returned-output bound

Additional sequence hypotheses for convergence

Clason, Regularization of Inverse Problems, Chapter 8

Hansen, Introduction to Inverse Problems, Chapter 5

Van Leeuwen and Brune, 10 Lectures on Inverse Problems and Imaging, Chapter 3