Linear regression and non-invertibility

Question

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

Answer 1

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.

Answer 2

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$$

Answer 3

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.