Ex. 18.12

Ex. 18.12

Suppose we wish to select the ridge parameter $\lambda$ by 10-fold cross-validation in a $p\gg N$ situation (for any linear model). We wish to use the computational shortcuts described in Section 18.3.5. Show that we need only to reduce the $N\times p$ matrix $\mathbf{\text{X}}$ to the $N\times N$ matrix $\mathbf{\text{R}}$ once, and can use it in all the cross-validation runs.

Soln. 18.12

The $N\times N$ matrix $\mathbf{\text{R}}$ is constructed via SVD of $\mathbf{\text{X}}$ in (18.13). For each observation $x_i,i=1,...,N$, (18.13) defines a corresponding $r_i,i=1,...,N$.

To perform 10-fold cross-validation, we divide the training sample $\mathbf{\text{X}}$ into 10 subsets $N_i,i=1,...,10$ with size $N/10$. Correspondingly, we divide the matrix $\mathbf{\text{R}}$ into 10 subsets with the same division indices as $\mathbf{\text{X}}$. We separate each subset $N_i$ aside and train on the remaining subsets. Recall the theorem described in (18.16)-(18.17) in the text, each training session (indexed by $j=1,...,10$) essential becomes solving

$$\underset{{\beta }_0,\beta }{\mathrm{argmin}}\sum _{i\notin N_j}L(y_i,{\beta }_0+x_i^T\beta )+\lambda {\beta }^T\beta ,$$

which has the same optimal solution if we solve for $r_i$ for $i\notin N_j$ like (18.17). Therefore, we only need to construct $\mathbf{\text{R}}$ once.