Why is $B^TB+\lambda\Omega$ positive definite?

Question

In spline regression, it is not uncommon for the basis expansion to create a rank-deficient design matrix $B_{n\times p}$, but it is well-known that penalization of the estimation procedure solves the problem. I don't know how to show that penalization means that $B^TB+\lambda\Omega$ is positive definite. (I know that PD matrices are invertible.)

To set the stage, we seek $\min_{\alpha\in\mathbb{R}^p} \sum_i|| y_i-f(x_i)||^2+\lambda\int_a^b [f''(t)]^2dt $ for the $f(x)$ given by the basis expansion $f(x_i)=\sum_j\alpha_j h_j(x_i)$. Collecting the basis vectors in $B$, I can show rather easily that this optimization reduces to

$$ \hat{\alpha}=(B^TB+\lambda\Omega)^{-1}B^Ty. $$

where $\Omega_{ij}=\int_a^b h_j^{\prime\prime}(t) h_i^{\prime\prime}(t)dt$.

Here is my reasoning so far. We know that $B$ is rank-deficient because $p>n$. This implies that $B^TB$ is also rank deficient; I can also show that at least one eigenvalue is 0 and that it is positive semidefinite.

But now I'm stuck because I don't know how to reason about $\Omega$ or to show that $B^TB+\lambda\Omega$ is PD for any $\lambda>0$. I know that $\Omega$ is a Gram matrix, but that only gets us as far as showing that $\Omega$ is PSD.

Answer 1

Showing that $B^TB+\lambda\Omega$ is PD amounts to showing that $\Omega$ is PD. (Thanks to Matthew Gunn for pointing that out in the comments.)

This is because $B^TB$ is, in the case that $p>n$, rank deficient and therefore PSD. This is because the quadratic form $a^TB^TBa\ge0\forall a\in\{\mathbb{R}^n\setminus0\}$ because we can rewrite it as $||Ba||_2^2\ge0$ because the square of any real number is nonnegative. So we have $a^T(B^TB+\Omega)a=a^TB^TBa+a^T\Omega a >0$ because if $\Omega$ is PD, then $a^T\Omega a>0$, the quantity $a^TB^TBa+a^T\Omega a$ is the sum of a nonnegative and a positive number, which must be positive. Therefore $B^TB+\Omega$ is PD as long as $\Omega$ is PD.

So we need to reason about $\Omega$. It fits the definition of a Gram matrix because it is given by the standard inner product on functions (that's stipulated in the question). The basis functions are linearly independent (because they form a basis), therefore $\Omega$ is PD.

$\Omega$ is PD iff its columns are independent. We can write $\Omega=A^TA.$ If the vectors of $A$ are linearly dependent, then we have $\Omega a=A^TAa=A^T0=0$ for some $a\neq 0$ because $Aa=0$ by definition of linear dependence, and $|\Omega|=|A^TA|=|A|^2=0$ by the properties of the determinant.

It's easy to show that this is true for any $\lambda>0$; all the same arguments apply because positive numbers are closed under multiplication.