Early Stopping as Implicit Spectral Filtering

Why an Iteration Count Acts Like Regularization

In an ill-posed inverse problem, a small amount of noise in the observed data can produce a large error in the reconstructed solution. Spectral regularization controls that amplification by modifying the contribution of each singular component. Landweber iteration does so without explicitly choosing a penalty parameter: its stopping index determines a spectral filter. Stopping early suppresses components associated with small singular values, while more iterations admit progressively finer components along with more noise.

Let \(A:\mathcal{X}\to\mathcal{Y}\) be a compact linear operator between Hilbert spaces, and suppose the observed data satisfy \(y^\delta=y+\varepsilon\), where \(y=Ax^\dagger\) and \(\|\varepsilon\|\leq\delta\). We seek the minimum-norm solution \(x^\dagger\), so \(x^\dagger\) is orthogonal to the null space of \(A\). Starting from \(x_0^\delta=0\), Landweber iteration with step size \(\eta\) is

Throughout, assume \(0<\eta\leq\|A\|^{-2}\). In a singular system, write \(A v_j=\sigma_j u_j\), with \(\sigma_j>0\), and put \(\lambda_j=\sigma_j^2\). Thus \(0<\lambda_j\leq\|A\|^2\), and \(q_j=1-\eta\lambda_j\) satisfies \(0\leq q_j<1\).

The Filter Induced by Stopping

The value \(g_k(0)=k\eta\) is the continuous extension at zero. Iterating the update gives \(x_k^\delta=g_k(A^*A)A^*y^\delta\). In singular coordinates, if \(y_j^\delta=\langle y^\delta,u_j\rangle\), then

The exact-data part of this coefficient is \(f_k(\lambda_j)\langle x^\dagger,v_j\rangle\); its noise part is \(g_k(\lambda_j)\sigma_j\langle\varepsilon,u_j\rangle\). For every spectral value \(0<\lambda\leq\|A\|^2\), the step-size condition gives \(0\leq1-\eta\lambda<1\). Consequently \(f_k(\lambda)\) increases from zero toward one as \(k\) increases. Small positive \(\lambda\) have factors nearer zero at a given finite \(k\), so their components are delayed. The claim is about spectral values in the allowed range, not arbitrary positive \(\lambda\).

Noise Amplification and Fixed Stopping

A filter factor close to one means the corresponding solution coefficient is recovered from data divided by \(\sigma_j\). That division is potentially unstable when \(\sigma_j\) is small. At any fixed \(k\), however, the Landweber filter limits this amplification. The following bound makes the dependence on the stopping index explicit.

Proof. On a singular component, the multiplier from a data perturbation to the solution is \(\sigma g_k(\lambda)=\{1-(1-\eta\lambda)^k\}/\sqrt{\lambda}\). Put \(t=\eta\lambda\), which lies in \((0,1]\). Since \(1-(1-t)^k\leq kt\) and \(1-(1-t)^k\leq1\),

For the final inequality, if \(t\leq1/k\), then \(k\sqrt{t}\leq\sqrt{k}\); if \(t\geq1/k\), then \(1/\sqrt{t}\leq\sqrt{k}\). Taking the supremum over singular components proves the operator bound. Applying it to \(\varepsilon\), whose norm is at most \(\delta\), proves the stated perturbation bound. \(\square\)

This bound explains why a fixed iteration count gives controlled noise amplification, but it does not make every fixed count a good choice. With fixed \(k\), as \(\delta\) tends to zero the estimator approaches the \(k\)-step exact-data iterate, which can retain substantial bias. Letting \(k\) grow reduces that bias but increases the bound on noise amplification. A residual-based rule uses the observed data to decide when the residual is small enough, rather than using one fixed index for every noise level.

Residual-Based Stopping

The residual at step \(k\) is \(r_k^\delta=y^\delta-Ax_k^\delta\). The update implies \(r_k^\delta=(I-\eta AA^*)^k y^\delta\). In singular coordinates its positive-eigenvalue components are multiplied by \((1-\eta\lambda_j)^k\), while its component in the null space of \(A^*\) is unchanged. Thus its norm is nonincreasing under the step-size condition.

What Discrepancy Stopping Guarantees

The discrepancy principle has a useful convergence guarantee in this setting. It requires exact data of the form \(y=Ax^\dagger\), noise bounded by \(\delta\), a fixed \(\tau>1\), and a nonzero exact datum. If \(y\) has a nonzero component with \(q_j>0\), the stopping index tends to infinity as the noise level shrinks. If \(y\) is supported only on components with \(q_j=0\), one step gives the exact-data solution.

Proof. Write \(T=I-\eta AA^*\). Its eigenvalues on positive singular components are \(q_j=1-\eta\lambda_j\in[0,1)\), and it acts as the identity on the null space of \(A^*\). Since \(y=Ax^\dagger\) is orthogonal to that null space, its exact-data residual is \(T^m y\), with squared norm

For fixed \(m\), the noisy residual differs from this exact-data residual by \(T^m(y^\delta-y)\), whose norm is at most \(\delta\), since \(\|T\|\leq1\). If \(y\) has a nonzero component with \(q_j>0\), then \(R_m>0\) for every fixed \(m\), so for any fixed \(M\), all residuals at indices \(0,\ldots,M\) eventually exceed \(\tau\delta\) as \(\delta\to0\). Thus \(k_\delta\to\infty\). If instead \(y\) is supported only on components with \(q_j=0\), then \(Ty=0\) and \(x_1=x^\dagger\). For sufficiently small \(\delta\), \(\|y^\delta\|\geq\|y\|-\delta>\tau\delta\), while \(\|Ty^\delta\|=\|T(y^\delta-y)\|\leq\delta<\tau\delta\), so \(k_\delta=1\). In this case \(\|x_1^\delta-x_1\|=\|\eta A^*(y^\delta-y)\|\leq\eta\|A\|\delta\to0\), proving convergence. In what follows, assume \(y\) has a nonzero component with \(q_j>0\).

The discrepancy index exists: \(T^m y^\delta\) converges as \(m\to\infty\) to the projection of \(y^\delta\) onto the null space of \(A^*\). That projection has norm at most \(\delta\), because \(y\) is orthogonal to the null space. Since \(\delta<\tau\delta\), some finite iterate meets the threshold.

The exact-data bias at index \(k\) has coefficients \(-q_j^k\langle x^\dagger,v_j\rangle\). Its squared norm tends to zero as \(k\to\infty\): each \(q_j^k\) tends to zero, and the squared coefficients are bounded by the summable sequence \(|\langle x^\dagger,v_j\rangle|^2\). It remains to show that the noise contribution vanishes at the selected index. For \(m\geq1\), \(mR_m^2\to0\). Indeed, for each fixed positive \(\lambda_j\), \(m\lambda_j(1-\eta\lambda_j)^{2m}\to0\); these terms are bounded uniformly in \(m\) and \(j\), since \((1-\eta\lambda)^{2m}\leq e^{-2m\eta\lambda}\) and \(m\lambda e^{-2m\eta\lambda}\leq1/(2e\eta)\). Summability of the squared coefficients then gives the limit.

For \(k_\delta\geq1\), the previous residual exceeds \(\tau\delta\). By the triangle inequality and \(\|T^{k_\delta-1}(y^\delta-y)\|\leq\delta\), \(R_{k_\delta-1}>(\tau-1)\delta\). Since \(k_\delta\to\infty\), the limit just established implies

The noise bound proved above now gives \(\|x_{k_\delta}^\delta-x_{k_\delta}\|\leq\delta\sqrt{\eta k_\delta}\to0\). The exact-data bias tends to zero because \(k_\delta\to\infty\). Adding these two differences proves \(x_{k_\delta}^\delta\to x^\dagger\). \(\square\)

Common Mistake and Practical Interpretation

A common mistake is to say that \(f_k(\lambda)\) increases toward one for every positive \(\lambda\). The statement is valid for spectral values under the stated step-size condition, where \(0<\lambda\leq\|A\|^2\) and \(0\leq1-\eta\lambda<1\). Outside that range, the factor can oscillate or fail to converge; for example, if \(\eta\lambda=2\), then \(f_k(\lambda)=1-(-1)^k\). The step-size restriction is therefore part of the filtering claim, not a technical detail to omit.

Early stopping is useful because one index controls all spectral components at once: it is a regularization choice expressed as an iteration count. A fixed index offers a predetermined compromise between bias and noise amplification. Residual-based stopping instead adapts to the observed residual and, under the theorem’s assumptions, yields convergence as the noise level decreases. Neither description says that every finite index is optimal, or that an observed residual alone reveals the reconstruction error. The practical balance remains between fitting the data and avoiding unstable recovery of small-singular-value components.