Positive semidefinite matrices and numerical stability?

Question

I am trying to do factor analysis for a match matrix (C), which is computed from a term document matrix (TD) as follows: C = TD * TD

In theory, C should be positive semi-definite, but this is not so, and the factor analysis algorithm cannot work with it because of this. I cannot change the algorithm due to speed reasons).

I watch it, and it could be a problem with numerical stability: A simple algorithm for generating positive semidefinite matrices is answer 2.

What a good way to continue here?

Answer 1

I would make my own representation of the matrix:

C=QDQ^-1 

If your matrix is ​​really positive semi-definite, then all eigenvalues ​​(entries on the diagonal D) should be non-negative. (This is probably a test that your factor analysis algorithm also does to see if the matrix is ​​positive semidefinite.)

If you suffer from numerical problems, some of the eigenvalues ​​are likely to be just under zero. Try setting these entries to zero, calculate QDQ^-1 to get a new, adjusted C, and then feed it to the factor analysis algorithm.

On the other hand, if you find that your matrix C has really negative eigenvalues, then you know that you are mistaken somewhere in the construction of C.

Answer 2

It is impossible to comment, I will need to respond to the SplittingField comment with a nitpick, which forms C = TD * TD ' squares TD condition number rather than double it. Equivalent and much more stable for finding eigendecomposition C would be performing singular decomposition (SVD) on TD. You get a condition number as a bonus: the ratio of the largest singular value to the smallest singular value is the condition number of the matrix, and the base 10 logarithm is an estimate of how many decimal digits you lose, you went through using C in your calculations (of course, if the minimum the only value is 0, your problem is exceptional!)

Answer 3

First of all, there are methods for restoring the “pathologies” of matrices with negative eigenvalues ​​- remember that the matrix is ​​taken from a series of calculations and, as a rule, these steps, which lead to pathologies in the first place. It is not entirely appropriate to accept the fact that, since the matrix has small negative eigenvalues ​​close to zero, it is a “bad” matrix. Rather, do some work to correct the pathologies. As for SVD, I agree that this is one of the best approaches, but I do not often use it in my work so much that it is so expensive to calculate. However, if you have one or more matrix elements equal to zero, i.e. The matrix is ​​sparse, then you should use SVD, as this will be one of the only methods that will work.