Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 205 / 5 / b / Solution

The leave-one-out residual identity for a linear smoother, obtained from the block matrix inverse or the Sherman–Morrison formula, isHence

Compute once the spectral decomposition $K=U\mathrm{diag}(d_1,\dots ,d_n)U^T$ in $O(n^3)$ operations and the vector $U^{T}Y$ in $O(n^2)$. For each ${\lambda }_{\ell }$, setThen computeBoth calculations take $O(n^2)$ operations per tuning parameter, after which the displayed leave-one-out formula costs $O(n)$. All $L$ scores therefore require $O(n^3+L{n}^2)$ operations.