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)

  • 2
    $\begingroup$ 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? $\endgroup$ Feb 25, 2014 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 26, 2014 at 3:00
  • 1
    $\begingroup$ No need to apologize. We just want to be clear. Thanks for editing. $\endgroup$ Feb 26, 2014 at 3:05

1 Answer 1


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.

  • $\begingroup$ Could you remind me what a full column rank is? (sorry it's been a while since I did my linear algebra course) Thanks! $\endgroup$ Feb 25, 2014 at 17:33
  • 2
    $\begingroup$ 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$. $\endgroup$
    – SomeEE
    Feb 25, 2014 at 17:44
  • $\begingroup$ What is N and what is d? I am assuming that d is the number of features for one row of X (i.e. one training data has size d) and N is the number of training data points? $\endgroup$ Feb 26, 2014 at 20:34
  • 1
    $\begingroup$ Yes, your assumptions are correct. $\endgroup$
    – SomeEE
    Feb 26, 2014 at 20:38
  • $\begingroup$ So what I understand so far is that we need to have independent columns of X, right? However, what does that imply on the training points that we get for X? (i.e. what does that imply on the rows of X) $\endgroup$ Feb 27, 2014 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.