# Linear regression closed form solution and having enough training points

I was trying to understand better when we can learn a unique parameter for linear regression and how much data is required to get one.

Say that we want to learn a parameter $\theta$ such that empirical risk is minimized $R_n(\theta)$. For that we want:

\begin{align} \bigtriangledown R_{n}( \theta )_{\theta = \hat{\theta}} &= 0 \\ \bigtriangledown\frac{1}{n} \sum^n_{t=1} (y^{(t)} - \theta \cdot x^{(t)}) &= \frac{1}{n}\sum^n_{t=1}-y^{(t)}x^{(t)} + \frac{1}{n} \sum^n_{t=1}x^{(t)} {x^{(t)}}^{T}\theta \end{align}

If we let $b = \frac{1}{n}\sum^n_{t=1}y^{(t)}x^{(t)}$, and $A = \frac{1}{n} \sum^n_{t=1}x^{(t)} {x^{(t)}}^{T}\theta$, then we can re-write it as:

\begin{align} -b + A \hat{\theta} &= 0 \\ A \hat{\theta} &= b \end{align}

or also more commonly known as:

\begin{align} b &= \frac{1}{n}x^{T}y \\ A &=\frac{1}{n}X^{T}X \\ X^{T}X \hat{\theta} &= X^{T}y \end{align}

But it was not clear to me what conditions we required for $A$ or $X$ so that $A$ was invertible. It obvious that $A$ should span the $R^d$ where $d$ is the dimensionality of the data, but how does that translate how the training data should span that subspace? I guess I am specifically unsure about when $A$ is invertible in relation to $X^T X$.

This is mainly a linear algebra question, however, since I posted this in the context of machine learning too, it would nice to get a response that explains what conditions we need to have of the training points such that such that $X^TX$ is invertible. i.e what conditions we need on the rows of X such that $X^TX$ is invertible.

(Also, I am interested on an answer that is informative, but if it comes with a proof of the claims that will make me most happy)

• You refer to regression in the title & use that tag, however in the body of the question, you seem to be discussing a classifier. In machine learning, people often think of regression & classification as being somewhat distinct. Can you clarify what topic you are thinking about? Are you thinking about both at a greater level of abstraction? – gung - Reinstate Monica Feb 25 '14 at 17:48
• Oh dam, your right, I did write the word classifier. That was me being completely careless and using the term classifier incorrectly. I agree classifier and regression are very different. I apologize I will correct that. – Charlie Parker Feb 26 '14 at 3:00
• No need to apologize. We just want to be clear. Thanks for editing. – gung - Reinstate Monica Feb 26 '14 at 3:05

It is necessary and sufficient that $X$ has full column rank where $X$ is arranged such that the $i^{th}$ row of $X$ is the $i^{th}$ observed vector.
• For $N > d$ it just means that the rows of $X$ span $\mathbb{R}^d$. In the applied setting you usually can access a rank function and you want to check $rank(X)=d$. – SomeEE Feb 25 '14 at 17:44