20
$\begingroup$

In linear regression there are two approaches for minimizing the cost function: The first one is using gradient descent. The second one is setting the derivative of the cost function to zero and solving the resulting equation. When the equation is solved, the parameter values which minimizes the cost function is given by the following well-known formula:

$$ \beta = (X^TX)^{-1}X^TY $$

where $\beta$ is the parameter values, $X$ is the design matrix, and $Y$ is the response vector.

Note that to have a solution $X^TX$ must be invertible. I think that even if $X^TX$ is non-invertible we can still minimize the cost function using the first approach (gradient descent). If this is true, what bothers me is which property of gradient descent makes it not vulnerable to this kind of problem.

thanks

$\endgroup$
2
  • $\begingroup$ This is not true "Note that to have a solution $X^TX$ must be invertible." In order to have UNIQUE solution that must be true but if it is not then you can have an infinity of solutions. $\endgroup$
    – user25658
    Sep 7, 2013 at 18:13
  • $\begingroup$ The least squares solution is $X^\dagger=(X^TX)^\dagger X^T=X^T(XX^T)^\dagger$. You can sometimes replace pseudo-inverse $\dagger$ with regular inverse in these formulas $\endgroup$ Jul 14, 2022 at 18:05

3 Answers 3

16
$\begingroup$

What you really want to solve is $$X^T X\beta = X^TY.$$ This equation has a single solution if $X^TX$ is invertible(non-singular). If it's not, you have more solutions. You then need to analyze why, i.e. there will be something about $X$ which makes $X^TX$ singular. In mathematical terms, the columns of $X$ are linearly dependent. In econometric terms, there are multi-collinearities.

I don't know for certain about your particular problem, but I doubt that the method you employ to minimize the cost function has any bearing on the invertibility of $X^T X$. The problem is in the specification.

There exists methods for analyzing which columns are linearly dependent/multi-collinear, in which way. They may be helpful for finding specification errors. In econometrics these are typically resolved by exhibiting suitable estimable functions, or change the specification of your original problem. You should search the literature for some of these concepts to find something which suits your problem and prior knowledge.

$\endgroup$
10
$\begingroup$

We can obtain a solution to $$\beta=(X^TX)^{-1}X^TY$$ even if $(X^TX)^{-1}$ is singular. However, the solution will not be unique. We can get around the problem of $(X^TX)^{-1}$ being singular by using generalized inverses to solve the problem.

A matrix $X^g$ is a generalized inverse of the matrix $A$ if and only if it satisfies $AX^gA=A$.

So, using the definition of a generalized inverse, we can write a solution to the least squares equation as

$$\beta=(X^TX)^gX^TY$$

$\endgroup$
1
  • 2
    $\begingroup$ I think to mantain a consistent notation the segond paragraph should be written as "A matrix $X^g$ is a generalized inverse of the matrix $X$ if and only if it satisfies $XX^gX=X$." That is, all X or all A. $\endgroup$
    – Pere
    Sep 25, 2016 at 14:25
0
$\begingroup$

Use the Moore-Penrose inverse! It's usually the "best" generalized inverse, in that it minimizes the sum of squared residuals (which is what you want if you assume gaussian noise in $Y$) and it is unique. It is what your gradient descent should converge to, but because the loss is quadratic it can also be solved directly (e.g. using the SVD).

Also look into Weighted Least Squares and Generalized Least Squares for immediate generalizations to handling data with more complicated variances/correlations.

$\endgroup$
1
  • 1
    $\begingroup$ All least squares regression methods minimize the sum of squared residuals. The pseudoinverse method is no different than other OLS methods this regard. Also, when the problem is underdetermined (as the OP is asking about), gradient descent will not generally converge to the same solution as the pseudoinverse method. $\endgroup$
    – user20160
    Mar 5, 2020 at 22:24

Your Answer

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

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