Saturation of Tikhonov Regularization

Why Tikhonov Bias Saturates

Regularization suppresses contributions from poorly determined spectral directions, but that suppression leaves a bias even when the data are noiseless. For ordinary Tikhonov regularization, the bias can decrease faster as the target becomes smoother—up to a point. In the solution norm considered here, the worst-case bias over a source class has order \(\lambda\) once the source smoothness reaches one. Greater smoothness does not improve that worst-case order.

The key is the residual filter. In a direction with eigenvalue \(\mu\), Tikhonov leaves a fraction \(\lambda/(\mu+\lambda)\) of the target. Multiplying this residual by a smooth target helps when \(\mu\) is small, but for a fixed positive eigenvalue the residual fraction is asymptotically proportional to \(\lambda\). That persistent contribution sets the saturation rate.

Spectral Setup and Source Classes

Let \(T\) be a compact, positive, self-adjoint, injective operator on a Hilbert space \(\mathcal H\). Assume \(\mathcal H\) has an orthonormal eigenbasis \((e_j)\) for \(T\), with eigenvalues \(0<\mu_j\le M=\|T\|\). In the infinite-dimensional case the eigenvalues can accumulate at zero. For a target \(x^\dagger\), the noiseless inverse equation has right-hand side \(T x^\dagger\). Ordinary Tikhonov regularization with parameter \(\lambda>0\) gives

On the eigenvector \(e_j\), the approximation multiplier is \(\mu_j/(\mu_j+\lambda)\), so the residual multiplier is \(\lambda/(\mu_j+\lambda)\). Thus the bias \(b_\lambda=x_\lambda-x^\dagger\) is

The source condition expresses smoothness relative to \(T\): larger \(s\) weights the coordinates of \(h\) by higher powers of the eigenvalues. It does not mean that every target in a smoother class has larger bias constants; the class radius and the particular target also matter. The saturation statement concerns the order of the worst-case bias as \(\lambda\) tends to zero.

Worked Examples of the Bias Multiplier

Bias Bounds and the Saturation Rate

For a target \(x^\dagger=T^s h\), each coefficient of its bias is \(-\lambda\mu_j^s\langle h,e_j\rangle/(\mu_j+\lambda)\). The largest possible amplification of a unit source vector is therefore the supremum of this scalar multiplier over the spectrum.

Proof. Since the eigenvectors form an orthonormal basis, the bias coefficients give

Indeed, the right side is an upper bound by summing the squared coefficient bounds. Conversely, for any index \(j\), the admissible choice \(h=Re_j\) gives bias norm \(R\lambda\mu_j^s/(\mu_j+\lambda)\); taking the supremum over \(j\) proves equality.

For \(0<s<1\), put \(u=\mu_j/\lambda\). Then

The derivative of \(u^s/(1+u)\) for \(u>0\) is \(u^{s-1}\{s-(1-s)u\}/(1+u)^2\). It is nonnegative up to \(u=s/(1-s)\) and nonpositive thereafter. The maximum is therefore \(s^s(1-s)^{1-s}=c_s\), proving the first bound. For \(s=1\), \(\lambda\mu_j/(\mu_j+\lambda)\le\lambda\). For \(s>1\), use \(\mu_j\le M\) and \(\mu_j/(\mu_j+\lambda)\le1\) to obtain

Finally, if \(M\) is an eigenvalue, its term in the supremum gives \(B_s(\lambda;R)\ge R\lambda M^s/(M+\lambda)\). When \(\lambda\le M\), \(M+\lambda\le2M\), hence this is at least \(R\lambda M^{s-1}/2\). Together with the upper bound this proves the asserted order-\(\lambda\) rate. \(\square\)

The bound for \(s>1\) can also be read directly as a loss of any hoped-for \(\lambda^s\) rate: the multiplier contains \(\mu_j^s\), but at a fixed positive eigenvalue the denominator approaches \(\mu_j\), leaving a term proportional to \(\lambda\). This is the saturation phenomenon for ordinary Tikhonov regularization in the solution norm.

What Happens for a Fixed Smooth Target?

A worst-case bound over a source class is not the same as the bias of one fixed target. For targets in the range of \(T\), one can identify the leading order more precisely. If \(x^\dagger=Tw\), then

Proof. Write \(w=\sum_j w_je_j\). The \(j\)th coefficient of \(b_\lambda/\lambda+w\) is \(\lambda w_j/(\mu_j+\lambda)\). For each fixed \(j\), this coefficient tends to zero. Also, \(0\le\lambda/(\mu_j+\lambda)\le1\), so its squared magnitude is at most \(|w_j|^2\). To verify convergence of the whole norm, take any \(\epsilon>0\). Choose \(J\) so that \(\sum_{j>J}|w_j|^2<\epsilon^2/2\). The squared norm of the tail is then at most \(\epsilon^2/2\), uniformly in \(\lambda\). For the finite set \(j\le J\), each coefficient tends to zero, so for sufficiently small \(\lambda\) the sum of their squared magnitudes is less than \(\epsilon^2/2\). Thus \(\|b_\lambda/\lambda+w\|<\epsilon\) for sufficiently small \(\lambda\), proving convergence. Norm convergence implies \(\|b_\lambda\|/\lambda=\|b_\lambda/\lambda\|\to\|w\|\). \(\square\)

For \(s\ge1\), every target \(x^\dagger=T^s h\) can be written \(Tw\) with \(w=T^{s-1}h\). If this \(w\) is nonzero, the theorem shows that its bias has exact order \(\lambda\), even if it belongs to a source class with \(s>1\). If \(w=0\), injectivity gives \(x^\dagger=0\), whose bias is zero. Thus the class-level lower bound and the fixed-target limit describe two related, but distinct, forms of saturation.

Why the Norm and the Worst Case Matter

The order-one threshold established here is for the bias measured in \(\|\cdot\|_{\mathcal H}\). A different loss can weight spectral coordinates differently and change the corresponding bias bound and saturation threshold. In particular, do not transfer this exponent to a prediction norm without deriving the relevant multiplier in that norm.

A common mistake is to argue that a source condition \(x^\dagger=T^s h\) must yield bias of order \(\lambda^s\) for every \(s\), simply because the target contains \(T^s\). That reasoning overlooks the denominator \(\mu_j+\lambda\): at a fixed positive eigenvalue, \(\lambda\mu_j^s/(\mu_j+\lambda)\) is asymptotic to \(\lambda\mu_j^{s-1}\), not to \(\lambda^s\). The correction is to bound the full multiplier uniformly over the spectrum. For \(s>1\), that supremum is of order \(\lambda\), and a fixed top eigenvalue supplies a matching lower bound.