Ex. 18.7

Ex. 18.7

Consider a linear regression problem where $p\gg N$, and assume the rank of $\mathbf{\text{X}}$ is $N$. Let the SVD of $\mathbf{\text{X}}=\mathbf{\text{U}}\mathbf{\text{D}}{\mathbf{\text{V}}}^T=\mathbf{\text{R}}{\mathbf{\text{V}}}^T$,where $\mathbf{\text{R}}$ is $N\times N$ nonsingular, and $\mathbf{\text{V}}$ is $p\times N$ with orthonormal columns.

(a) Show that there are infinitely many least-squares solutions all with zero residuals.

(b) Show that the ridge-regression estimate for $\beta$ can be written

$${\hat{\beta }}_{\lambda }=\mathbf{\text{V}}({\mathbf{\text{R}}}^T\mathbf{\text{R}}+\lambda \mathbf{\text{I}}{)}^{-1}{\mathbf{\text{R}}}^T\mathbf{\text{y}}$$

(c) Show that when $\lambda =0$, the solution ${\hat{\beta }}_0=\mathbf{\text{V}}{\mathbf{\text{D}}}^{-1}{\mathbf{\text{U}}}^T\mathbf{\text{y}}$ has residuals all equal to zero, and is unique in that it has the smallest Euclidean norm amongst all zero-residual solutions.

Soln. 18.7

(a) Since $\mathbf{\text{X}}\in {\mathbb{R}}^{p\times N}$ has rank $N\le p$, we know there exists $\alpha \ne 0$ such that $\mathbf{\text{X}}\alpha =0$. If ${\hat{\beta }}_0$ has zero residuals, so does ${\hat{\beta }}_0+k\alpha$ for any $k\in \mathbb{R}$. Therefore there are infinitely many least-squares solutions all with zero residuals.

(b) This is the same as Ex. 18.4.

(c) Note that

$$\mathbf{\text{X}}{\hat{\beta }}_0=\mathbf{\text{U}}\mathbf{\text{D}}{\mathbf{\text{V}}}^T\mathbf{\text{V}}{\mathbf{\text{D}}}^{-1}{\mathbf{\text{U}}}^T\mathbf{\text{y}}=\mathbf{\text{y}},$$

so ${\hat{\beta }}_0$ has zero residual.

Suppose that ${\hat{\beta }}_0+\beta$ has zero residual for some $\beta \ne \mathbf{\text{0}}$, that is, $\mathbf{\text{X}}({\hat{\beta }}_0+\beta )=\mathbf{\text{y}}$. Since ${\hat{\beta }}_0$ has zero residual, we know

$$\mathbf{\text{X}}\beta =\mathbf{\text{R}}{\mathbf{\text{V}}}^T\beta =0.$$

Note that $\mathbf{\text{R}}$ is $N\times N$ nonsingular, so we have ${\mathbf{\text{V}}}^T\beta =0$. Now consider the Euclidean norm of ${\hat{\beta }}_0+\beta$, we have

$$\begin{array}{rcl}& & ({\hat{\beta }}_0+\beta {)}^T({\hat{\beta }}_0+\beta )\\ & =& {\hat{\beta }}_0^T{\hat{\beta }}_0+{\beta }^T\beta +2{\hat{\beta }}_0^T\beta \\ & =& {\hat{\beta }}_0^T{\hat{\beta }}_0+{\beta }^T\beta +2{\mathbf{\text{y}}}^T\mathbf{\text{U}}{\mathbf{\text{D}}}^{-1}{\mathbf{\text{V}}}^T\beta \\ & =& {\hat{\beta }}_0^T{\hat{\beta }}_0+{\beta }^T\beta +0.\end{array}$$

Since ${\beta }^T\beta >0$, we know that ${\hat{\beta }}_0$ has the smallest Euclidean norm.