# Gradient descent to solve regressions with large features

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.

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

• @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. Nov 4, 2021 at 3:46