1
$\begingroup$

I have read Numerically find the nearest positive semi definite matrix to a symmetric matrix and How to find the nearest/a near positive definite from a given matrix?

But the key problem is I need to do this fast. I have a 10K by 10K dense matrix, and finding all the eigenvalues are slow... But usually I know the matrix is only slightly non-PSD. i.e. the negative eigenvalues are small in magnitude and there are also not that many of them.

What's the most numerically efficient method? I am using python, if there is an existing solution that'd be helpful

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

I assume your starting matrix $M$ is already symmetric. Note that you don't have to find all eigenvalues: you only have to find the eigenpairs $(q_i,\lambda_i)$ with $\lambda_i < 0$; then, it follows from the answers you linked that the nearest PSD matrix is $$ M + \sum q_i\, |\lambda_i|\, q_i^T. $$ To compute those eigenpairs, you can use the customary methods for sparse eigenvalues, in your case scipy.sparse.linalg.eigsh with which=SA. You'll have to guess a target number k of eigenvalues that overestimates the number of negative ones.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ To belabor the point a bit: if you get back all negative eigenvectors from eigsh, then you don't know whether or not k was sufficient to find all of them, so you will have to try again with a larger k until you find a nonnegative one. So by guessing an initial k that's usually slightly too high, you save work overall. $\endgroup$ Commented Apr 29 at 14:10

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.