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

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.

• You'd need to show $\Omega$ is positive definite. Where does $h$ come from exactly? How is it defined? Nov 6, 2016 at 20:40
• I was curious if $\Omega$ is always PD? What if I put knots at every distinct x value? Jul 17, 2019 at 13:34
• @vtshen My answer shows that $\Omega$ is PD in two ways. If you have further questions, you can click Ask Question at the top of the page to ask a new question.
– Sycorax
Jul 17, 2019 at 13:57
• @Sycorax thanks for the response. I asked another question, but was flagged as duplicate Jul 17, 2019 at 14:00
• I cannot comment to the previous answer but there seems to be an issue. Namely $\Omega$ is usually not of full rank. It is the integral over the the second derivative squared. So when we take a linear functions which also lie in the spline space we get that for such coefficients the inner product will be zero. Now if $B$ is vastly degenerate, for example assume all points are the same then also the inner product for the matrix $B$ will be zero for a linear function. Therefore there is a non zero one. This means that it s not strictly convex. In application this is avoided by adding a very smal Jan 7, 2021 at 15:55

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.
• +1. I guess you can accept you own answer... As you said, as $\Omega$ is a Gram matrix after all so that kind of settles it, I can't see a further aspect coming in! Dec 30, 2016 at 0:31