10
$\begingroup$

I am working on some clustering techniques, where for a given cluster of d-dimension vectors I assume a multivariate normal distribution and calculate the sample d-dimensional mean vector and the sample covariance matrix.

Then when trying to decide if a new, unseen, d-dimensional vector belongs to this cluster I am checking its distance via this measure: $$\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{-p}{2}\right)$$

Which requires me to calculate the inverse of the covariance matrix $\hat{\sigma}_X$. But given some samples I cannot guarantee that the covariance matrix will be invertible, what should I do in the case that it is not?

Thanks

$\endgroup$
  • $\begingroup$ it depends on what is causing the matrix to not be invertible. Possible causes can be (a) the sample you used to compute the covariance matrix is too small (b) your sample is of sufficient size but it's member are not drawn from a continuous distribution so that some of the column/row of your sample repeat. $\endgroup$ – user603 Feb 12 '13 at 14:04
  • $\begingroup$ I think the sample size becomes to small $\endgroup$ – Aly Feb 12 '13 at 14:06
  • $\begingroup$ @Anony-Mousse I have made sure I am now using at least as many samples as dimensions, otherwise the matrix will be rank deficient. So far no problems, but I think with the sample covariance it can be non-invertible? $\endgroup$ – Aly Feb 12 '13 at 14:36
  • 1
    $\begingroup$ Why should $MM^T$ always be invertible? With a single observation the mean is equal to that observation, so the sample covariance is the zero matrix, which won't invert. I think a matrix has to be of full rank to be inverted, and it will only be of full rank if the number of samples >= the dimension $\endgroup$ – Corone Feb 12 '13 at 14:54
  • 1
    $\begingroup$ @corone makes that a strict > $\endgroup$ – user603 Feb 12 '13 at 15:10
13
$\begingroup$

If your samples dimensionality is less than the vector space dimensionality, singular matrices may arise. If you have less samples than $d+1$ (when $d$ is your dimensionality), this situation will even necessarily arise: $k+1$ samples span at most a $d$ dimensional hyperplane. Given such a small sample, you obviously cannot compute a variance in the orthogonal space.

This is why it's common to not use literal PCA, but instead perform singular value decomposition, which can be used to compute the pseudoinverse of a matrix. If the matrix is invertible, the pseudoinverse will be the inverse.

However, if you are seeing non-invertible matrixes, chances are that your distance from the cluster will be meaningless if the vector is outside of the hyperplane the cluster repesents, because you do not know the variance in the orthogonal space (you can think of this variance as 0!) SVD can compute the pseudoinverse, but the "variances" will still be not determined by your data.

In this case, you should probably have been doing global dimensionality reduction first. Increasing the sample size will only help when you actually have non-redundant dimensions: no matter how many samples you draw from a distributions with $y=x$, the matrix will always be non-invertible, and you will not be able to judge the deviation $x-y$ with respect to a standard deviation (which is 0).

Furthermore, depending on how you compute the covariance matrix, you might be running into numerical issues due to catastrophic cancellation. The simplest workaround is to always center the data first, to get zero mean.

$\endgroup$
  • $\begingroup$ sorry for replying here but i am working on the same issue. i am comparing clustering distances via Mahalanobis distance which requires inverse covariance matrix. however in my case i am getting same error. so i tried SingularValueDecomposition but this time all distances are equal 1.4 :D i can not figure it out $\endgroup$ – MonsterMMORPG Mar 1 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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