Iterative regularization and early stopping — Examples

For $A_N$ and $y^{\delta }$, $r_0=(0,N^{-1}{)}^T$, so ${\beta }_1=N^{-1}$, $u_1=(0,1{)}^T$, ${\alpha }_1=N^{-2}$, and $v_1=(0,1{)}^T$. The first bidiagonalization residual is $A_N{v}_1-{\alpha }_1{u}_1=0$, so ${\beta }_2=0$ and the one-dimensional projected least-squares problem is exact.

Its projected matrix is $B_1=(N^{-2},0{)}^T\in {\mathbb{R}}^{2\times 1}$ and right-hand side is ${\beta }_1{e}_1=(N^{-1},0{)}^T\in {\mathbb{R}}^2$, so the unique minimizer is $z_1=N$. Consequently $x_1^{\delta }=x_0+N{v}_1=(0,N{)}^T$, $A_N{x}_1^{\delta }=y^{\delta }$, and $\mathrm{\parallel }{x}_1^{\delta }-x^{†}{\mathrm{\parallel }}_2=N$. The noise is $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_2=N^{-1}$, so the error-to-noise ratio is $N^2\to \mathrm{\infty }$. This refutes the proposed uniform bound and shows that the projected solve can fit a small noise component in a weak singular direction. The value ${\beta }_2=0$ marks bidiagonalization breakdown; the projected solve still forms the exact one-step iterate before the algorithm tests its final status. For the assigned discrepancy-stopped algorithm, the initial test already returns at index zero because $\mathrm{\parallel }{r}_0{\mathrm{\parallel }}_2={\delta }_N\le \tau {\delta }_N$; this computation concerns continuation to the full projected solve and claims no breakdown return.

By [F6], $e^{\log 2}=2$, and [F3] gives $e^{-\log 2}=1\mathrm{/}2$; hence $F(c^{†})=1\mathrm{/}2$ and $F(c_0)=0$. The derivative of $c\mapsto -c$ is $-1$ by its difference quotient. Therefore [F2], [F4], and [F5] give $(e^{-c}{)}^{\mathrm{\prime }}=-e^{-c}$ and $F^{\mathrm{\prime }}(c)=e^{-c}$, so $F^{\mathrm{\prime }}(0)=1$.

The initial residual satisfies $\mathrm{\mid }{y}^{\delta }-F(c_0)\mathrm{\mid }\ge 2\mathrm{/}5$, while $\tau \delta \le 1\mathrm{/}5$, so the discrepancy test does not stop at $c_0$. Substitution into [F1] gives $c_1=0+(1+1\mathrm{/}4{)}^{-1}(1\mathrm{/}2+\epsilon )=\frac{2}{5}+\frac{4}{5}\epsilon$. Because $\mathrm{\mid }\epsilon \mathrm{\mid }\le 1\mathrm{/}10$, $c_1\ge \frac{2}{5}-\frac{2}{25}=\frac{8}{25}>0$, so the returned rate lies in the physical rate domain $[0,\mathrm{\infty })$.

Since the cap is $N=1$ and $c_1\in U=\mathbb{R}$, the next check returns status discrepancy if its residual is at most $2\delta$; otherwise the cap branch returns budget-exhausted. In both cases the returned state is $c_1$.

Reindexing by $n\mapsto n+1$ is a linear isometry from ${\mathrm{\ell }}^2(I,\mathbb{R})$ onto ${\mathrm{\ell }}^2(\mathbb{N},\mathbb{R})$, so [F7] makes $X=Y$ Hilbert spaces. All coordinates below are indexed by $j\ge 1$, and $(Ax{)}_j=2^{-j}{x}_j$. By [F8], $\mathrm{\parallel }Ax{\mathrm{\parallel }}^2={\sum }_{j\ge 1}{4}^{-j}\mathrm{\mid }{x}_j{\mathrm{\mid }}^2\le \frac{1}{4}\mathrm{\parallel }x{\mathrm{\parallel }}^2$, with equality at $e_1$; hence $A$ is bounded linear and [F5] gives $\mathrm{\parallel }A\mathrm{\parallel }=1\mathrm{/}2$. The truncation $(A_{N}x{)}_j=2^{-j}{x}_j$ for $j\le N$ and $0$ otherwise satisfies $\mathrm{\parallel }{A}_{N}x{\mathrm{\parallel }}^2={\sum }_{j=1}^N{4}^{-j}\mathrm{\mid }{x}_j{\mathrm{\mid }}^2\le \frac{1}{4}\mathrm{\parallel }x{\mathrm{\parallel }}^2$. It is bounded linear with range having ordered basis $e_1,\dots ,e_N$ (the empty basis if $N=0$), so [F3] makes it compact. Also $\mathrm{\parallel }A-A_N\mathrm{\parallel }={\sup }_{j>N}{2}^{-j}=2^{-(N+1)}\to 0$, so [F4] makes $A$ compact. Thus $0<\omega =1<2\mathrm{/}\mathrm{\parallel }A{\mathrm{\parallel }}^2=8$. The data norm is $\mathrm{\parallel }{y}^{\delta }{\mathrm{\parallel }}^2={\delta }^2{\sum }_{j=1}^{\mathrm{\infty }}{2}^{-j}={\delta }^2$.

By [F6] and [F8], $A^{\ast }{e}_j=2^{-j}{e}_j$: for every $x$, $⟨Ax,e_j⟩=2^{-j}{x}_j=⟨x,2^{-j}{e}_j⟩$, and the adjoint is unique. Thus $A{A}^{\ast }{e}_j=4^{-j}{e}_j$, and the un-stopped path from [F1] has residual coordinates given by [F2]: $\delta 2^{-j\mathrm{/}2}(1-4^{-j}{)}^k$. Their squared sum is dominated termwise by ${\delta }^2{2}^{-j}$, whose tail tends to zero by the geometric-series formula. Given $ϵ>0$, choose a finite initial segment with omitted bound below $ϵ$; on that finite segment every residual coordinate tends to zero. Hence the full squared residual sum tends to zero. Each coordinate factor also decreases with $k$, so the residual norm is nonincreasing.

Here $A^{\ast }A{e}_j=4^{-j}{e}_j$. Substituting into [F2] gives $x_{k,j}^{\delta }=\delta 2^{j\mathrm{/}2}(1-(1-4^{-j}{)}^k)$. For an integer $n\ge 2$, Bernoulli's inequality gives $(1+1\mathrm{/}(n-1){)}^n\ge 1+n\mathrm{/}(n-1)>2$, hence $(1-1\mathrm{/}n{)}^n<1\mathrm{/}2$. Taking $n=4^j$ shows $\mathrm{\mid }{x}_{k_j,j}^{\delta }\mathrm{\mid }\ge \delta 2^{j\mathrm{/}2}\mathrm{/}2$, which tends to infinity. Thus $\mathrm{\parallel }{x}_{k_j}^{\delta }-x^{†}\mathrm{\parallel }\to \mathrm{\infty }$ although the residual tends to zero; this is semiconvergence and shows why the method needs an explicit stopping rule.

Let $\mathbf{1}=(1,1,1{)}^T$. By [F4], $A=\frac{1}{4}(I+{\mathbf{11}}^T)$. Thus $A\mathbf{1}=\mathbf{1}$, and for every $v\perp \mathbf{1}$ one has ${\mathbf{1}}^{T}v=0$ and $Av=\frac{1}{4}v$. These orthogonal subspaces span ${\mathbb{R}}^3$, so [F3]–[F5] give $\mathrm{\parallel }A\mathrm{\parallel }=1$ and $0<1<2\mathrm{/}\mathrm{\parallel }A{\mathrm{\parallel }}^2$.

Since $x^{†}$ is a zero-sum eigenvector, $A^{T}A{x}^{†}=\frac{1}{16}{x}^{†}$. Applying [F2] gives $x_k=[1-(1-1\mathrm{/}16{)}^k]x^{†}=[1-(15\mathrm{/}16{)}^k]x^{†}$. At $k=1$ this is $\frac{1}{16}(1,0,-1{)}^T$, and the scalar coefficient tends to $1$ as $k\to \mathrm{\infty }$.