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

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.