Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 78 / 5

Use the Euclidean norm and its induced operator norm. The spectral theorem for real symmetric matrices gives $\Vert A\Vert ={\lambda }_n$ and $\Vert A^{-1}\Vert =1/{\lambda }_1$. If $e=y_{\delta }-y$, then the direct inverse has error $A^{-1}e$, soFor nonzero $y$, the relation $\Vert y\Vert =\Vert Ax\Vert \le {\lambda }_n\Vert x\Vert$ also givesThis is the spectral condition number of a positive-definite matrix. The worst relative amplification is attained by exact data along an eigenvector for ${\lambda }_n$ and noise along one for ${\lambda }_1$. A large $\kappa$ therefore makes the reconstruction sensitive to relative data errors. Absolute sensitivity additionally depends on ${\lambda }_1$ itself: scaling every eigenvalue equally leaves $\kappa$ unchanged but changes $1/{\lambda }_1$. Since the matrix is finite dimensional and positive definite, the inverse exists and is continuous; the issue is ill-conditioning rather than mathematical nonexistence or discontinuity.

For $\alpha >0$, Tikhonov regularization minimizes the strictly convex quadraticDifferentiating in every direction gives the Tikhonov normal equation $(A^{T}A+\alpha I)v=A^T{y}_{\delta }$. Symmetry of $A$ therefore givesThe spectral filter suppresses unstable division by small eigenvalues. Put $e_i=(y_{\delta }-y,u_i)$ and $x_i=(x,u_i)$. The exact noise-bias decomposition for linear regularization isBy orthonormality and the triangle inequality,The scalar gain satisfies $\lambda /({\lambda }^2+\alpha )\le 1/(2\sqrt{\alpha })$, because $(\lambda -\sqrt{\alpha }{)}^2\ge 0$. Hence the Tikhonov stability bound givesThis explicitly separates data noise from regularization bias. For a known bound $X\ge \Vert x\Vert >0$, minimizing this last bound gives an a priori regularization parameter choiceOne data-based bound is $X=(\Vert y_{\delta }\Vert +\delta )/{\lambda }_1$. More generally, $\alpha (\delta )\to 0$ and $\delta /\sqrt{\alpha (\delta )}\to 0$ make the robust estimate converge to zero.

For this fixed finite matrix, the sharper gain bound ${\max }_i{\lambda }_i/({\lambda }_i^2+\alpha )\le 1/{\lambda }_1$ is also available. Thus the ${\delta }^{2/3}$ rate is a consequence of the robust bound, not an optimality claim: choosing $\alpha X/{\lambda }_1^2\le C\delta /{\lambda }_1$ gives an $O(\delta /{\lambda }_1)$ estimate. No unique statistically optimal parameter is specified without further assumptions on the signal or noise.

The simpler shifted inverse is Lavrentiev regularization. Its expansion in the orthonormal eigenbasis isUsing $y=Ax$, the exact component error isConsequently the noise-bias decomposition for linear regularization givesFor a prior or data-based bound $X\ge \Vert x\Vert$, balancing noise and approximation bias in the last expression givesFor example $X=(\Vert y_{\delta }\Vert +\delta )/{\lambda }_1$ is computable from the data and the stated noise bound. With fixed positive ${\lambda }_1$, $\alpha \to 0$ and $\delta /\alpha \to 0$ are sufficient for the robust bound to converge.

The first bound is stronger in the finite-dimensional setting. If $X>0$, choosing $\alpha =\delta /X$ gives $\Vert x_{\alpha }^{\delta }-x\Vert \le 2\delta /({\lambda }_1+\delta /X)$. The unregularized inverse already has error at most $\delta /{\lambda }_1$; the balancing rule is a useful stabilized choice rather than a necessary cure for an unbounded inverse. A universal noise-only optimal $\alpha$ cannot be inferred without information about the size or spectral content of $x$.