Numerical Inverse Problems and Regularization Error

Uniqueness in [F2] gives linearity of $A^{\ast }$: for scalars $a,b$ and $y_1,y_2\in Y$, conjugate-linearity of the second slot shows that $a{A}^{\ast }{y}_1+b{A}^{\ast }{y}_2$ satisfies the defining identity for $a{y}_1+b{y}_2$, so it equals $A^{\ast }(a{y}_1+b{y}_2)$. For $w=A^{\ast }y$, [F2], [F4] and [F7] give $\mathrm{\parallel }w{\mathrm{\parallel }}^2=⟨Aw,y⟩\le \mathrm{\mid }⟨Aw,y⟩\mathrm{\mid }\le \mathrm{\parallel }A\mathrm{\parallel }\mathrm{\parallel }w\mathrm{\parallel }\mathrm{\parallel }y\mathrm{\parallel }$. Dividing when $w\mathrm{\ne }0$, and treating $w=0$ directly, proves $\mathrm{\parallel }{A}^{\ast }y\mathrm{\parallel }\le \mathrm{\parallel }A\mathrm{\parallel }\mathrm{\parallel }y\mathrm{\parallel }$. Thus $A^{\ast }$ is bounded, and composition and addition make $B_{\lambda }$ linear and bounded with $\mathrm{\parallel }{B}_{\lambda }x\mathrm{\parallel }\le (\mathrm{\parallel }A{\mathrm{\parallel }}^2+\lambda )\mathrm{\parallel }x\mathrm{\parallel }$. The adjoint identity and conjugate symmetry [F6] give $⟨B_{\lambda }x,z⟩=⟨Ax,Az⟩+\lambda ⟨x,z⟩=⟨x,B_{\lambda }z⟩$ for all $x,z\in X$. In particular, $⟨B_{\lambda }x,x⟩=\mathrm{\parallel }Ax{\mathrm{\parallel }}^2+\lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2\ge \lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2$.

By [F4], $\mathrm{\parallel }{B}_{\lambda }x\mathrm{\parallel }\mathrm{\parallel }x\mathrm{\parallel }\ge \mathrm{\mid }⟨B_{\lambda }x,x⟩\mathrm{\mid }=⟨B_{\lambda }x,x⟩\ge \lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2$. Thus $\mathrm{\parallel }{B}_{\lambda }x\mathrm{\parallel }\ge \lambda \mathrm{\parallel }x\mathrm{\parallel }$ for $x\mathrm{\ne }0$; the same inequality is trivial for $x=0$. Hence $B_{\lambda }$ is injective. If $B_{\lambda }{x}_n$ converges, this inequality applied to $x_n-x_m$ makes $(x_n)$ Cauchy; completeness of $X$ and boundedness of $B_{\lambda }$ show its limit lies in $\mathrm{ran}{B}_{\lambda }$. Therefore the range is closed.

If $z\in (\mathrm{ran}{B}_{\lambda }{)}^{\perp }$, [F8] gives $⟨z,B_{\lambda }x⟩=0$ for every $x\in X$. By conjugate symmetry [F6] this is $⟨B_{\lambda }x,z⟩=0$, and the symmetry identity from step 1.1 gives $⟨x,B_{\lambda }z⟩=0$ for every $x\in X$. Taking $x=B_{\lambda }z$ and using positive definiteness [F6] yields $B_{\lambda }z=0$; injectivity from step 2.1 then gives $z=0$. Thus the closed range has zero orthogonal complement.

By [F5] and the Countable Choice assumption [A1], a closed subspace with zero orthogonal complement is all of $X$; so $B_{\lambda }$ is surjective as well as injective. For $y=B_{\lambda }x$, step 2.1 gives $\mathrm{\parallel }{B}_{\lambda }^{-1}y\mathrm{\parallel }=\mathrm{\parallel }x\mathrm{\parallel }\le \mathrm{\parallel }y\mathrm{\parallel }\mathrm{/}\lambda$, proving $\mathrm{\parallel }{B}_{\lambda }^{-1}\mathrm{\parallel }\le 1\mathrm{/}\lambda$.

By linearity and $b=A{x}^{†}+e$, $x^{†}-A_{\tau }^{+}b=(I-A_{\tau }^{+}A)x^{†}-A_{\tau }^{+}e$.

The definition in [F2] and the SVD in [F1] give $A_{\tau }^{+}A{x}^{†}={\sum }_{i\in I_{\tau }}⟨x^{†},v_i⟩v_i$; expanding $x^{†}$ in the full orthonormal basis $(v_i)$ therefore makes $(I-A_{\tau }^{+}A)x^{†}={\sum }_{i\in J_{\tau }}⟨x^{†},v_i⟩v_i$. Likewise, $A_{\tau }^{+}e={\sum }_{i\in I_{\tau }}{\sigma }_i^{-1}⟨e,u_i⟩v_i$.

If $I_{\tau }$ is empty, [F2] makes $A_{\tau }^{+}=0$. Otherwise orthonormality of the retained $v_i$ and [F1] give $\mathrm{\parallel }{A}_{\tau }^{+}e{\mathrm{\parallel }}^2={\sum }_{i\in I_{\tau }}\mathrm{\mid }⟨e,u_i⟩{\mathrm{\mid }}^2\mathrm{/}{\sigma }_i^2\le ({\max }_{i\in I_{\tau }}{\sigma }_i^{-1}{)}^2{\sum }_{i\in I_{\tau }}\mathrm{\mid }⟨e,u_i⟩{\mathrm{\mid }}^2$. Since $(u_1,\dots ,u_m)$ is an orthonormal basis of ${\mathbb{F}}^m$, write $e={\sum }_{i=1}^m⟨e,u_i⟩u_i$; conjugate symmetry and orthonormality give $\mathrm{\parallel }e{\mathrm{\parallel }}^2={\sum }_{i=1}^m\mathrm{\mid }⟨e,u_i⟩{\mathrm{\mid }}^2$. Consequently ${\sum }_{i\in I_{\tau }}\mathrm{\mid }⟨e,u_i⟩{\mathrm{\mid }}^2\le \mathrm{\parallel }e{\mathrm{\parallel }}^2$. Taking nonnegative square roots proves the noise bound and the stated bias/noise split.

Let $x=R_{\lambda }g$. Under [A1], [F2] gives the Hilbert adjoint used in the definition of $R_{\lambda }$. By [F1], $(A^{\ast }A+\lambda I_X)x=A^{\ast }g$. Pairing with $x$ and using [F2] gives $⟨A^{\ast }Ax,x{⟩}_X=⟨Ax,Ax{⟩}_Y=\mathrm{\parallel }Ax{\mathrm{\parallel }}^2$ and $⟨A^{\ast }g,x{⟩}_X=⟨g,Ax{⟩}_Y$ by [F2]–[F4]. Hence $\mathrm{\parallel }Ax{\mathrm{\parallel }}^2+\lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2=⟨g,Ax{⟩}_Y$.

The left side of step 1.1 is real and nonnegative. By [F5], with $s=\mathrm{\parallel }Ax\mathrm{\parallel }$ and $t=\mathrm{\parallel }g\mathrm{\parallel }$, step 1.1 gives $\lambda \mathrm{\parallel }x{\mathrm{\parallel }}^2=⟨g,Ax⟩-s^2\le \mathrm{\mid }⟨g,Ax⟩\mathrm{\mid }-s^2\le ts-s^2$. Completing the square gives $ts-s^2=\frac{t^2}{4}-(s-t\mathrm{/}2{)}^2\le t^2\mathrm{/}4$. Since $\lambda >0$, taking nonnegative square roots yields $\mathrm{\parallel }{R}_{\lambda }g\mathrm{\parallel }=\mathrm{\parallel }x\mathrm{\parallel }\le \mathrm{\parallel }g\mathrm{\parallel }\mathrm{/}(2\sqrt{\lambda })$.

The pointwise inequality of step 2.1 holds for every $g\in Y$. Taking the supremum over the unit ball in [F6] gives $\mathrm{\parallel }{R}_{\lambda }\mathrm{\parallel }\le 1\mathrm{/}(2\sqrt{\lambda })$.

By [F7], $A$ is bounded, and [F8] supplies the Hilbert-space hypotheses. By [F1], both shifted normal operators are invertible, so the displayed $R_{\lambda }$ and $R_{\lambda ,h}$ are defined. Multiplying their definitions by their normal operators gives $(A^{\ast }A+\lambda I)R_{\lambda }=A^{\ast }$ and $(A_h^{\ast }{A}_h+\lambda I)R_{\lambda ,h}=A_h^{\ast }$.

Adding and subtracting the intermediate vectors $R_{\lambda }y$, $R_{\lambda }{y}_{\delta }$, and $R_{\lambda ,h}{y}_{\delta }$ cancels the intervening terms and proves the stated four-term identity. Since $y_{\delta }=y+e$, [F2] gives $\mathrm{\parallel }{R}_{\lambda }y-R_{\lambda }{y}_{\delta }\mathrm{\parallel }=\mathrm{\parallel }{R}_{\lambda }e\mathrm{\parallel }\le \delta \mathrm{/}(2\sqrt{\lambda })$.

Adding and subtracting $x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}$ gives the optional stopping/roundoff identity. The normal equation for $R_{\lambda ,h}{y}_{\delta }$ and the definition of $r_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}$ imply $(A_h^{\ast }{A}_h+\lambda I)(x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}-R_{\lambda ,h}{y}_{\delta })=r_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}$. By [F1], the stopping term is at most $\mathrm{\parallel }{r}_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}\mathrm{\parallel }\mathrm{/}\lambda$; the other term is exactly the stated roundoff difference.

In the refined datum case, $y_{\delta }-y_{h,\delta }=(A{x}^{†}+e)-(A_h{x}^{†}+e)=d_h$. Inserting $R_{\lambda }{y}_{h,\delta }$ and $R_{\lambda ,h}{y}_{h,\delta }$ into the chain therefore gives the displayed five-term identity by cancellation.

Let $z=R_{\lambda ,h}{y}_{\delta }$. The normal equation in step 1.1 gives $(A_h^{\ast }{A}_h+\lambda I)(\tilde{x}-z)=r_h$. By [F1], $\mathrm{\parallel }\tilde{x}-z\mathrm{\parallel }\le \mathrm{\parallel }{r}_h\mathrm{\parallel }\mathrm{/}\lambda$. The triangle inequality [F9] applied to the four-term identity, using step 1.2 for its noise term, proves the stated total error bound.

Applying [F2] to $d_h$ bounds its pre-inversion contribution by $\mathrm{\parallel }{R}_{\lambda }{d}_h\mathrm{\parallel }\le \mathrm{\parallel }{d}_h\mathrm{\parallel }\mathrm{/}(2\sqrt{\lambda })$. Applying [F1] to $r_{h,h}=(A_h^{\ast }{A}_h+\lambda I)({\tilde{x}}_h-R_{\lambda ,h}{y}_{h,\delta })$ gives the stated refined solve-residual bound. Under the residual-evaluation hypothesis, the triangle inequality [F9] gives $\mathrm{\parallel }{r}_{h,h}\mathrm{\parallel }\le \mathrm{\parallel }{\widehat{r}}_{h,h}\mathrm{\parallel }+{\rho }_{h,h}$.

In the finite-matrix case with $A_h=A$ and the exact regularized output $\tilde{x}=R_{\lambda }{y}_{\delta }$, [F5]–[F6] identify $R_{\lambda }$ with the canonical Tikhonov minimizer. The baseline identity from step 1.2 then reduces to the displayed finite-matrix bias/noise formula.

By [F4], an assumed operator-norm bound $\mathrm{\parallel }{R}_{\lambda }-R_{\lambda ,h}\mathrm{\parallel }\le {\eta }_{\lambda ,h}$ gives $\mathrm{\parallel }(R_{\lambda }-R_{\lambda ,h})y_{\delta }\mathrm{\parallel }\le {\eta }_{\lambda ,h}\mathrm{\parallel }{y}_{\delta }\mathrm{\parallel }$. Also, the triangle inequality [F9] gives $\mathrm{\parallel }{r}_h\mathrm{\parallel }\le \mathrm{\parallel }{\widehat{r}}_h\mathrm{\parallel }+\mathrm{\parallel }{r}_h-{\widehat{r}}_h\mathrm{\parallel }\le \mathrm{\parallel }{\widehat{r}}_h\mathrm{\parallel }+{\rho }_h$ under the stated residual-evaluation hypothesis. These are conditional estimates, not automatic stability claims.

For stored finite data, or for supplied isometric coordinates $A_h=VM{U}^{\ast }$ and returned output $U\widehat{x}$, apply [F10] to the coefficient matrix $M$ (the matrix case uses identity embeddings) and datum $g=y_{\delta }$ or $g=y_{h,\delta }$. The exact normal residual lifts isometrically to $r_h$ or $r_{h,h}$, with any certified coordinate-data and orthogonal-output allowances from [F10]. Hence steps 2.2 and 3.1 apply. For the exact direct augmented solve, $x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}=R_{\lambda ,h}g$, and [F10] bounds the returned-output term by $(\mathrm{\parallel }\widehat{r}\mathrm{\parallel }+\rho )\mathrm{/}\lambda$. The analytic identity and its independent bias, noise and discretization terms are unchanged.

Put $F_k={\sum }_{j=1}^k{f}_j$. Since $F_1=f_1\in {\mathcal{L}}^2$, induction using [F3] shows $F_k\in {\mathcal{L}}^2$ and $\mathrm{\parallel }{F}_k{\mathrm{\parallel }}_2\le {\sum }_{j=1}^k\mathrm{\parallel }{f}_j{\mathrm{\parallel }}_2$ for every $k\le N$. The pointwise triangle inequality [F10] gives $0\le g\le F_N$, hence [F4] applied to their squares gives $\mathrm{\parallel }g{\mathrm{\parallel }}_2\le \mathrm{\parallel }{F}_N{\mathrm{\parallel }}_2\le {\sum }_j\mathrm{\parallel }{f}_j{\mathrm{\parallel }}_2$. This is the claimed $L^2$ error bound by the definition of $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_{2,H}$.

At each $\omega$, expanding the squared inner-product norm and pairing the two cross terms gives $g(\omega {)}^2={\sum }_j{f}_j(\omega {)}^2+2{\sum }_{i<j}\mathrm{Re}⟨d_i(\omega ),d_j(\omega ){⟩}_H$. By [F5], $\mathrm{\mid }⟨d_i,d_j{⟩}_H\mathrm{\mid }\le f_i{f}_j$, and $(f_i-f_j{)}^2\ge 0$ gives $2f_i{f}_j\le f_i^2+f_j^2$. Thus each cross term is integrable: [F2] makes each $f_i^2$ integrable, [F7] makes their finite sum integrable, and [F4] bounds the integral of the absolute cross term by that sum. All squared-norm terms are integrable by [F2]. The expansion uses [F9] and [F8]. Integrating the finite identity and using [F6]–[F7] gives the displayed cross-term formula; the formula gives exact root-sum-square if and only if the finite sum of cross integrals is zero. Separate vanishing is sufficient, but nonzero cross integrals may cancel.

For the stated inverse-problem application, [F1] supplies the finite chain under [A1]. Whenever its differences satisfy the scalar hypotheses of this corollary, steps 1.1 and 1.2 apply to that chain.

The stored augmented matrix has full column rank, since $\mathrm{\parallel }[A;\alpha I]z{\mathrm{\parallel }}_2^2=\mathrm{\parallel }Az{\mathrm{\parallel }}_2^2+{\alpha }^2\mathrm{\parallel }z{\mathrm{\parallel }}_2^2\ge {\alpha }^2\mathrm{\parallel }z{\mathrm{\parallel }}_2^2$. If $C+{\mathrm{\Delta }}_Q=\widehat{Q}\widehat{R}$, then $\mathrm{\parallel }\widehat{R}z\mathrm{\parallel }=\mathrm{\parallel }(C+{\mathrm{\Delta }}_Q)z\mathrm{\parallel }\ge (\alpha -{ϵ}_Q)\mathrm{\parallel }z\mathrm{\parallel }$. Under the sufficient margin, the further triangular perturbation preserves a positive lower bound. Thus the nonsingularity premise in [F2] holds under the stated check. The theorem still explicitly requires successful arithmetic; exact full rank alone does not ensure rounded success.

By [F3], $\alpha =\sqrt{\lambda }(1+\delta )$, $\mathrm{\mid }\delta \mathrm{\mid }\le u$, whence $\mathrm{\mid }{\alpha }^2-\lambda \mathrm{\mid }\le (2u+u^2)\lambda$. For any $z$, Cauchy-Schwarz gives $\mathrm{\parallel }(A^{\ast }A+\lambda I)z\mathrm{\parallel }\mathrm{\parallel }z\mathrm{\parallel }\ge ⟨(A^{\ast }A+\lambda I)z,z⟩=\mathrm{\parallel }Az{\mathrm{\parallel }}^2+\lambda \mathrm{\parallel }z{\mathrm{\parallel }}^2\ge \lambda \mathrm{\parallel }z{\mathrm{\parallel }}^2$. The normal equation [F4] therefore implies $\mathrm{\parallel }\widehat{x}-x_{\lambda }\mathrm{\parallel }\le \mathrm{\parallel }r\mathrm{\parallel }\mathrm{/}\lambda \le (\mathrm{\parallel }\widehat{r}\mathrm{\parallel }+\rho )\mathrm{/}\lambda$ using the assumed residual certificate, supplied by [F1] under the stated evaluation hypotheses. Replacing the coefficient in a residual by ${\alpha }^2$ changes that exact residual by $({\alpha }^2-\lambda )\widehat{x}$, giving the stated additional allowance.

For complex inputs identify $z=z_R+i{z}_I$ with $(z_R,z_I)\in {\mathbb{R}}^{2n}$. The real matrix $A_R=\left(\begin{array}{cc}\mathrm{Re}A& -\mathrm{Im}A\\ \mathrm{Im}A& \mathrm{Re}A\end{array}\right)$ represents exactly the same linear map, preserves vector norms, and satisfies $\mathrm{\parallel }{A}_R{\mathrm{\parallel }}_2=\mathrm{\parallel }A{\mathrm{\parallel }}_2$, $\mathrm{\parallel }{A}_R{\mathrm{\parallel }}_F=\sqrt{2}\mathrm{\parallel }A{\mathrm{\parallel }}_F$ by direct component sums. Apply [F2] to $[A_R;\alpha I_{2n}]$ and datum $((\mathrm{Re}y,\mathrm{Im}y),0)$; this is exactly the original complex objective. Mapping its output back needs only component pairing, so introduces no arithmetic error or unmodeled complex division.

In exact arithmetic with the intended $\sqrt{\lambda }$, full-rank augmented QR returns the unique minimizer in [F4], hence $x_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}=x_{\lambda }$. Step 1.2 bounds the returned computed output's difference from that target, including square-root representation and all solve error through its certified residual. For an iterative stopping target different from $x_{\lambda }$, retain separate stopping and output terms rather than calling their sum pure roundoff.

In the supplied Hilbert representation, $U^{\ast }U=I$, $V^{\ast }V=I$, and $A_h^{\ast }=U{A}^{\ast }{V}^{\ast }$. The subspaces $\mathrm{ran}U$ and its orthogonal complement are invariant under $A_h^{\ast }{A}_h+\lambda I$; on the complement that operator is $\lambda I$ and its right-hand side $A_h^{\ast }y$ has zero component. Thus the exact normal solution is $U{x}_{\lambda }$, with coefficient datum $V^{\ast }y$. Direct substitution gives $r_h=U((A^{\ast }A+\lambda I)\widehat{x}-A^{\ast }{V}^{\ast }y)$, and isometry preserves its norm. For every coefficient vector $e$, put $w=A^{\ast }e$. Then $\mathrm{\parallel }w{\mathrm{\parallel }}_2^2=⟨Aw,e⟩\le \mathrm{\mid }⟨Aw,e⟩\mathrm{\mid }\le \mathrm{\parallel }A{\mathrm{\parallel }}_2\mathrm{\parallel }w{\mathrm{\parallel }}_2\mathrm{\parallel }e{\mathrm{\parallel }}_2$ by [F5]–[F6]; dividing for $w\mathrm{\ne }0$ (and checking $w=0$ directly) gives $\mathrm{\parallel }{A}^{\ast }e{\mathrm{\parallel }}_2\le \mathrm{\parallel }A{\mathrm{\parallel }}_2\mathrm{\parallel }e{\mathrm{\parallel }}_2$. Perturbing the datum therefore adds $U{A}^{\ast }({\widehat{y}}_c-V^{\ast }y)$ of norm at most $\mathrm{\parallel }A{\mathrm{\parallel }}_2{ϵ}_y$; an orthogonal output component adds $\lambda z$. Triangle inequality gives the stated allowances. These explicit coordinate hypotheses preserve the general Hilbert theorem while justifying its concrete finite solve.