How to prove this regularized matrix is invertible?

So I'm taking Andrew Ng's course on machine learning (great course, only comment is that its lacking a lot of math) and we came across the analytical solution to a model using Normal equations with the regularization penalty.

Andrew claims that it is possible to prove that the matrix below, inside the parentheses, is always invertible but I'm stuck wondering how to do it.

$$\theta = (X^TX + \lambda [M])^{-1} X^Ty$$

where $M$ is an $(n+1)(n+1)$ matrix and $\lambda$ is the regularization parameter

$$M = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

• What is $\lambda[M]$? Oct 31, 2016 at 8:07

$X^TX$ is either PD or PSD.* If it's PD, it's already invertible. If it's PSD, its smallest eigenvalue is $0$. For any $\lambda>0$, you're making the smallest eigenvalue inside the parentheses positive.

*Consider $(Xa)^2$; we can write $||Xa||^2_2\ge0\implies a^TX^TXa\ge 0$. The LHS is nonnegative, so the RHS must also be. And the RHS is immediately the definition of PSD; $a\neq 0$.

As whuber points out, $(X^TX)_{1,1}$ must be positive for this to work. This will be true whenever the first column of $X$ is not a 0 vector. (We can verify that easily: the 1,1 entry is the inner product of the first column of X with itself, which must be nonnegative for real values because it is formed as the sum of squares and squares of reals are nonnegative.)

• Thank you so much, obvious only after you pointed it out. +1 Oct 31, 2016 at 4:10
• The logic of this argument is somewhat unclear. The answer must come down to the fact that the $1,1$ entry of $X^\prime X$ is strictly positive--and that requires more information than has been used so far. This is a trivial matter, though, because if that entry indeed is zero, then the entire first column of $X$ must be zero and presumably this possibility has been ruled out.
– whuber
Oct 31, 2016 at 14:23

We are seeing regularization is adding a diagonal elements in $X^TX$, then, $X^TX$ is the full rank matrix. Full rank is invertible matrix.

• IMO I find this easier than the accepted one Apr 10, 2017 at 13:21

Iff $$\vec{u}=\langle1, 0, 0, \ldots, 0\rangle$$ is a null vector for $$X$$ (meaning the first column of $$X$$ is 0), the matrix $$X^TX + \lambda M$$ will be singular.

In the $$3x3$$ case, $$\lambda M\vec{u} = \left[ \begin{matrix} 0 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{matrix} \right] \begin{bmatrix} 1\\0\\0 \end{bmatrix} = \vec{0}$$

Thus, $$\left( X^TX + \lambda M \right) \vec{u} = X^TX\vec{u} + \lambda M \vec{u} = X^T\vec{0} + \vec{0} = \vec{0}$$

In checking with positive definiteness, we know that $$\vec{v}^T \lambda M\vec{v} > 0$$ only if $$\vec{v}\neq k\vec{u}$$ for some nonzero $$k$$. Since $$X^TX$$ is symmetric, it is automatically PSD, so $$\vec{v}^T\left(X^TX + \lambda M\right)\vec{v} > 0$$ if $$\vec{v}\neq k\vec{u}$$.

Assuming $$\vec{v} = k\vec{u}$$,

\begin{align*} \vec{v}^T\left(X^TX + \lambda M\right)\vec{v} &= (k\vec{u})^T\left(X^TX + \lambda M\right)k\vec{u}\\ &= (k\vec{u})^T\left(X^TX\right)k\vec{u} + (k\vec{u})^T\left(\lambda M\right)k\vec{u}\\ &= k^2\vec{u}^T\left(X^TX\right)\vec{u} + \lambda k^2\vec{u}^T M\vec{u}\\ &= k^2\vec{u}^T\left(X^TX\right)\vec{u} + \lambda k^2\vec{u}^T \vec{0}\\ &= k^2\vec{u}^T\left(X^TX\right)\vec{u}\\ &= k^2\left(\vec{u}^T X^T\right)X\vec{u}\\ &= k^2(X\vec{u})^T X\vec{u}\\ &= k^2\|X\vec{u}\|_2^2\\ &\geq 0 \end{align*}

This shows there exists a vector for which $$X^T X$$ may generally not be considered nonsingular.

Working backwards, if you assume the matrix $$X^TX + \lambda M$$ is singular, you know there is some nonzero vector $$\vec{v}$$ for which $$\left(X^TX + \lambda M\right)\vec{v}=\vec{0}$$ and, therefore, $$\vec{v}^T\left(X^TX + \lambda M\right)\vec{v} = 0$$.

For $$\vec{v} = \langle v_1, v_2, \ldots, v_n\rangle$$, $$M\vec{v} = \langle 0, v_2, \ldots, v_n\rangle$$ and $$\vec{v}^T M\vec{v} = \sum_{k=2}^{n} v_k^2$$.

\begin{align*} 0 &= \vec{v}^T\left(X^TX + \lambda M\right)\vec{v}\\ &= \vec{v}^T\left(X^TX\right)\vec{v} + \vec{v}^T\lambda M\vec{v}\\ &= \|X\vec{v}\|_2^2 + \lambda\sum_{k=2}^{n} v_k^2\\ \end{align*}

Clearly, this is only true if $$v_k = 0$$ for $$2 \leq k \leq n$$. Therefore, $$\vec{v}=k\vec{u}$$ for some nonzero $$k$$, meaning that $$X$$ has a zero first column.

In practice, this will not happen, since each entry in the first column of $$X$$ is set to 1.