Why the columns of design matrix for linear models with additive Gaussian noise linear independent?

Question

This question comes from page 142 of the book "Pattern Recognition and Machine Learning" by Christopher M. Bishop. Since it takes pages to arrive at the result, I excerpt the major settings as follows.

The goal is to derive the maximum likelihood solution for parameters $\bf w$ in a deterministic linear model with additive Gaussian noise $$t={\bf w}^T{\bf\phi}({\bf x})+\epsilon$$ where ${\bf w}=(w_0,\ldots,w_{M-1})^T$ and ${\bf\phi}$ is a vector of basis functions $(\phi_0,\ldots,\phi_{M-1})^T$ and hence should be in bold typeface.

Now consider a data set of inputs ${\bf X}=\{{\bf x}_1,\ldots,{\bf x}_N\}$ with corresponding target values ${\bf t}=(t_1,\ldots,t_N)^T$. Taking the (transpose of the) gradient of the log likelihood function and setting this gradient to zero gives

The book proceeds with solving for $\bf w$ to obtain $${\bf w}_{\mathrm{ML}}=({\bf\Phi}^T{\bf\Phi})^{-1}{\bf\Phi}^T{\bf t}.$$

Here $\bf\Phi$ is an $N\times M$ matrix, called the design matrix:

.

My questions is, matrix ${\bf\Phi}^T{\bf\Phi}$ is invertible only if $\bf\Phi$ has linearly independent columns. If we denote columns of $\bf\Phi$ by ${\bf\varphi}_j, j=1,\ldots,M$ (again should be bold-faced), why are ${\bf\varphi}_j$'s linearly independent? In general, if $M>N$, these columns are necessarily linear dependent in $\mathbb R^N$, so how could ${\bf\Phi}^T{\bf\Phi}$ be invertible to form the Moore-Penrose pseudo-inverse? Such a linear independence is also needed in subsequent geometrical interpretation in which $M<N$ and the subspace spanned by these column vectors is claimed to have dimensionality $M$. I checked the book but see nowhere make this claim. Neither can I figure out the independence from general definition of basis functions in the book. I'll appreciate it if you help me understand such a linear independence between ${\bf\varphi}_j$'s.

Answer 1

You are right, $\boldsymbol{\Phi}^T\boldsymbol{\Phi}$ is only invertible if all the columns of $\boldsymbol{\Phi}$ are independent, which is impossible if $M>N$ and should be presumed for $M\le N$. And if Bishop did not mention this explicitly, it is unfortunate.

However, recall that the observations $\mathbf x_i$ could usually be considered as samples from some continuous probability distribution, and thus the columns of $\mathbf \Phi$ could be considered as samples from a continuous distribution, too. Now, with respect to this probability measure, the set of matrices $\mathbf\Phi$ with $N\ge M$ that are not of maximal rank is of measure zero, i.e. those "singular" matrices $\mathbf\Phi$ occur with probability zero. Thus, from this point of view, it is justified to presume maximal rank of $\mathbf \Phi$ for $N\ge M$. But, again, you are right, and the singular situation should have at least been mentioned.