0
$\begingroup$

We know that the closed-form solution for linear regression is $\beta = (X'X)^{-1}X'Y$.
$X$ is a $N\times M$ matrix, where N is the number of observations and M is the number of features.

However, in the case when we have more features than observations, $M>N$, $X'X$ is not longer invertible since the $M\times M$ matrix of $X'X$ is not full rank. As a result, we can no longer use the closed form solution.

Would it be possible (and reasonable) then to use the gradient descent approach to solve for $\beta$?
It is commonly mentioned that gradient descent is preferred to using the closed-form solution since it doesn't require inverting the $X'X$ matrix which can be time intensive, especially for large $M$.

I was curious if gradient descent can also always guarantee a solution when the closed-form solution can't.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Keep in mind that there is a generalized inverse, too. $\endgroup$
    – Dave
    Nov 4, 2021 at 2:34
  • 1
    $\begingroup$ gradient descent with weight decay can guarantee a unique solution because its equivalent to ridge regression $\endgroup$
    – seanv507
    Nov 4, 2021 at 11:15

1 Answer 1

Reset to default
0
$\begingroup$

It is commonly mentioned that gradient descent is preferred to using the closed-form solution since it doesn't require inverting the X'X matrix which can be time intensive, especially for large M

I am under the impression that inversion of the hat matrix is not how statistical packages fit linear models. Rather, the QR factorization is employed.

Would it be possible (and reasonable) then to use the gradient descent approach to solve for β?

Possible? I believe so. The only condition here is that the minimum is not unique, and so the answer would depend on where you start.

Improve this answer
$\endgroup$
2
  • $\begingroup$ can you please explain why the minimum would not be unique in this instance? $\endgroup$
    – vpy
    Nov 4, 2021 at 3:13
  • $\begingroup$ @vpy Because $X$ has $N<M$ then the dimension of the kernel of $X$ is greater than 0. This means I can write $y = X (\beta - \beta^*)$ for $\beta^*$ in the kernel of $X$. Hence, the solution to the equation $y=X\beta$ is not unique. $\endgroup$
    – Demetri Pananos
    Nov 4, 2021 at 3:46

Your Answer

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

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