Search code examples
mathmatrixnumerical-methodsnumerical-stability

positive semi-definite matrices and numerical stability?

i'm trying to do factor analysis for a co-occurrence matrix(C) , which is computed from the term-document matrix(TD) as follows: C=TD*TD'

In theory C should be positive semi-definite , but it isn't and the factor analysis algorithm can't work with it because of this.I can't change the algo because of speed reasons).

I look it up and it might be a numerical stability issue : A simple algorithm for generating positive-semidefinite matrices - answer 2.

What's a good way to proceed here ?

Solution

  • I would do an eigendecomposition of the matrix:

    C=Q D Q^-1

    If your matrix really is positive semidefinite, then all of the eigenvalues (the entries on the diagonal of D) should be non-negative. (This is probably the test that your factor analysis algorithm is doing as well to see if the matrix is positive semidefinite.)

    If you're suffering numeric problems, some of the eigenvalues will probably be barely smaller than zero. Try setting these entries to zero, compute Q D Q^-1 to get a new, corrected C, then submit that to your factor analysis algorithm.

    On the other hand, if you find that your matrix C has truly negative eigenvalues, then you know that you're going wrong somewhere in the construction of C.