Linear Regression and Ridge Regression

Question

In Linear regression, we have $\textbf{$\theta$} = \textbf{$\left (X^TX\right )^{-1} X^T y$}$.

In Ridge regression, we have $\textbf{$\theta$} = \textbf{$\left ( \lambda I+ X^TX\right )^{-1} X^T y$}$.

I learnt somewhere that while $\textbf{$X^TX$}$ is not guaranteed to be invertible, $\textbf{$\lambda I + X^TX$}$ is guaranteed to be invertible.

Is this true? If so, why?

Answer 1

Hint: Can you write the eigenvalues of $\lambda I + X^\top X$ in terms of the eigenvalues of $X^\top X$?

The eigenvalues of $X^\top X$ are nonnegative. (Why?) It is possible for it to be not invertible (specifically, if some of the eigenvalues are zero). However, the eigenvalues of $\lambda I + X^\top X$ are of the form $\lambda + \mu$ where $\mu$ is an eigenvalue of $X^\top X$. (Why?) Since $\lambda > 0$ and $\mu \ge 0$, the eigenvalues of $\lambda I + X^\top X$ are all strictly positive, so it is invertible.

Answer 2

If $\lambda > 0$, then $\lambda I + X^TX$ is necessarily invertible since it is the sum of a positive definite and positive semidefinite matrix.

Answer 3

First, replace $\lambda \rightarrow -\tilde{\lambda}$. Then the given expression

$$\boldsymbol{X}^T\boldsymbol{X}-\tilde{\lambda}\boldsymbol{I}$$ is similar to the eigenvalue equation of the matrix $\boldsymbol{X}^T\boldsymbol{X}$. As $\boldsymbol{X}^T\boldsymbol{X}$ is a positive semi-definite matrix we know that its eigenvalues are all $\geq 0$ (see here). This implies that for $\lambda$ the corresponding values are $\leq 0$. If you state that $\lambda > 0$ then you rule out all possible eigenvalues. Hence, the eigenvalue equation

$$ \text{det}\left[\boldsymbol{X}^T\boldsymbol{X}-\tilde{\lambda}\boldsymbol{I}\right]=0$$

does not have any solutions. Hence, $\left[\boldsymbol{X}^T\boldsymbol{X}-\tilde{\lambda}\boldsymbol{I}\right]=\left[\boldsymbol{X}^T\boldsymbol{X}+\lambda\boldsymbol{I}\right]$ is invertible for $\lambda > 0$.