Ways to measure distance from multivariate Gaussian (Mahalanobis distance)

Question

I have a cluster of p-dimensional points and given a new p-dimensional point $x$ I want to determine whether or not it is likely to belong to this cluster.

The cluster is made up of $n$ p-dimensional points, I am making the assumption that these points are drawn from a multivariate Gaussian distribution with sample mean ${\hat{\mu_X}}$ and sample covariance matrix $\hat{\sigma_X}$.

Given a new point $x$ I am trying to decide if it is likely to belong to this cluster using the following threshold on the Mahalanobis distance: $$\frac{n}{(n-1)^2}\left(X_i-\hat{\mu}_X\right)'\hat{\sigma}_X^{-1}\left(X_i-\hat{\mu}_X\right)>B_{0.95}\left(\frac{p}{2},\frac{n-p-1}{2}\right)$$

However, some clusters have very few sample points $n$ in which case calculating the inverse covariance matrix $\hat{\sigma_X}^{-1}$ becomes impossible.

Are there any other equivalent or more appropriate measure I can use in this case?

Answer 1

You can compute the pseudo-Mahalanobis distance by using the pseudo-inverse:

$$W_i'\hat{\sigma}_W^{-1}W_i$$

where

$$W^*=\left(X_i-\hat{\mu}_X\right)$$

and

$$W=W^*V_{W^*}$$

where

$V_{W^*}$ is the $V$ matrix of the SVD decomposition of $W^*$

Then simply compute the Mahalanobis distances on the matrix $W$ (instead of $X$).

note that you need to replace $p$ in the left hand side of your inequality by $p^*$ (the rank of $V_{W^*}$)

Answer 2

The covariance matrix cannot be inverted if it is not of full rank (in practice, you also want a decently low condition number.

There are two ways to improve the situation:

• add more cases (samples)
• reduce the number of variates (features)

That is:

• cut out features of which your expert knowledge says that they are not contributing to the clustering and/or
• compress your data into fewer features.
  You may be able to do the calculations if you move for example into the space of the first few principal components.

Answer 3

Here is, not an alternative metric, but an alternative method for computing the Mahalanobis distance that does not require inverting the covariance matrix $\hat{\sigma}_X$ :

• Let $y = x - {\hat{\mu_X}}$
• Find lower triangular matrix $L$ so that $ \hat{\sigma}_X = L L^{T}$
• Solve $Lz = y$ for $z$
• Mahalanobis distance $ = \sqrt{z^T z}$

The second step is a Cholesky decomposition, easily done in MATLAB as L=chol(Sigma,'lower'), or Python as L=numpy.linalg.cholesky(Sigma)

(See this question for more)