# Optimal solution for linear regression problem

I have an assignment for university about the linear regression problem and the optimal solution.

For the linear regression problem

$$\min_w ||Y - X\omega||^2$$,

$$\omega^*$$ is the optimal solution. I have to show that $$X(\omega^* - w_0) = 0$$ where $$\omega_0 = (X^TX)^+X^TY$$. Also $$X \in \mathcal{R}^{n \times d}, rank(X^TX) \leq d$$.

So I am honest, I don't have any clue where to start. I experimented with dividing it into 2 cases:

1. $$rank(X^TX) < d$$, this means the matrix has linearly dependent rows in it. So there also isn't an inverse possible, $$X^TX^+$$ would be a pseudo-inverse(?). There can be more than one solution, because the linearly independent "line" gives the possibility of infinitely many vectors that can be added to the solution so that i.e. $$\omega_2 = \omega_1 + v$$, where $$v$$ is another vector. But what can I do with this information? How can I proceed to show the above equation with this?

2. $$rank(X^TX) = d$$, this means the matrix is linearly independent and there is an inverse possible. So there is also only one unique solution to the problem. But why?

My problem is that I don't know where to start and I would really just like to understand all of this. So just some tips as to how I need to proceed would be nice.

• Two hints. First, you can simplify the expression $w_0=(X^TX)^+X^Ty = X^+y.\,$ Second, the solution of the linear system can be written in a way which covers the 2 cases you've described. \eqalign{&X^TXw=X^Ty\cr&w=X^+y+Pa} where $P=(I-X^+X)$ is an orthoprojector into the nullspace of $X$, and $a$ is an arbitrary vector. – greg May 5 at 21:27