0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – greg May 5 at 21:27

Your Answer

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

Browse other questions tagged or ask your own question.