Mahalanobis distance: What if S is not invertible? [duplicate]

Question

The Mahalanobis distance is a distance metric used to measure the distance between two points in some feature space. Unlike the Euclidean distance, it uses the covariance matrix to "adjust" for covariance among the various features.

The Mahalanobis distance formula uses the inverse of the covariance matrix. What if the covariance matrix is not invertible?

Answer 1

If the covariance matrix isn't full rank, there exists a linear combination of your variables which has zero variance. That linear combination should always equal some constant! (Note: any eigenvector of covariance matrix associated with a zero eigenvalue defines a linear combination that should have zero variance.)

If in your data you have a point where the linear combination does not equal that constant, in some sense, the Mahlanobis distance is infinite: in units of the standard deviation (which is zero), the point is infinitely far from the mean.

On the other hand, if the linear combination that should be zero is in fact zero, there's no problem. But how would you calculate the distance? Two basic approaches are:

1. Use pseudo inverse instead of inverse. (Simple!) md = x' * pinv(Sigma) * x
2. Reduce the number of dimensions until everything is full rank. Your data is actually in a lower dimensional space than the current number of variables, and you can transform your data and covariance matrix to operate directly in that lower dimensional space.
   • Eg. Use singular value decomposition [U, S, V] = svd(X). $Y = X V$ and $\Sigma_Y = V' * \Sigma_X * V$ and then drop dimensions associated with zero (or near zero) singular values.

(Note: above formulas assume everything already demeaned)

Example:

Let's imagine the a simple two variable case where $x_1$ and $x_2$ are mean zero, $2 x_1 = x_2 $, and the covariance matrix is given by:

$$\Sigma = \left[ \begin{array}{cc} 1 & 2 \\ 2 & 4\end{array}\right] $$

$2x_1 - x_2$ should always be zero! It has zero variance:

$$ \left[ \begin{array}{c} 2& -1\end{array}\right] \left[ \begin{array}{cc} 1 & 2 \\ 2 & 4\end{array}\right] \left[ \begin{array}{c} 2\\-1\end{array}\right] = 0 $$

In this case, for computing the distance, we could either:

1. Use the pseudo inverse of $\Sigma$
2. Only use one of the variables (either $x_1$ or $x_2$) and use the appropriate submatrix of $\Sigma$
3. Do svd stuff mentioned earlier. (Makes sense for high dimensions but rather silly for two dimensions.)

Answer 2

If you are going to use the sample covariance matrix and you don't have enough samples, your covariance is ill conditioned, won't be invertible and you are going to get VERY POOR estimation results.

There are many ways to practically deal with this. Here are the main strategies I would use:

1.There is a whole field of research that aims to regularize this problem and compute a better estimate of the covariance matrix when you do not have enough samples. The most common thing I see statistics loving people using, is either using the pseudo inverse covariance matrix or using a form of shrinkage. Shrinkage is extremely common. If you are looking for something more recent, I suggest this paper.

2.An alternative strategy, more related to the machine learning world, is to use the strategy adopted by Random Forests called Bagging. In Bagging, you randomly select a small subset of the features, so, you will need a lot less samples for your covariance matrix to be properly conditioned. Then you can use an ensemble of such well conditioned classifiers and get a better result.

As a rule of thumb, you should use about x10 times the number of samples as there are dimensions in your data. You don't only want your covariance to be well conditioned, you also want it to be accurate.