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$ – gung - Reinstate Monica Feb 25 '14 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$ – Charlie Parker Feb 26 '14 at 3:00
  • 1
    $\begingroup$ No need to apologize. We just want to be clear. Thanks for editing. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\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$ – Charlie Parker Feb 25 '14 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 '14 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$ – Charlie Parker Feb 26 '14 at 20:34
  • 1
    $\begingroup$ Yes, your assumptions are correct. $\endgroup$ – SomeEE Feb 26 '14 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$ – Charlie Parker Feb 27 '14 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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