I have a dense Hermitian matrix that is approximately unitary, so it has eigenvalues that are $\sim \pm1$. I would like to compute all the eigenvectors corresponding to the $+1$ eigenvalue (not necessarily a small fraction of the total number of eigenvalues). Is there some more efficient way to accomplish this than tridiagonal QR?

  • $\begingroup$ Look for the kernel of $A-I$? $\endgroup$ – Federico Poloni Apr 8 '14 at 10:50
  • $\begingroup$ Now that I re-read your question, it is not clear to me whether you mean "the eigenvalues that are exactly +1", or "those that are closer to +1 than to -1 and hopefully come from +1 eigenvalues of the unperturbed unitary matrix". Could you clarify? $\endgroup$ – Federico Poloni Apr 9 '14 at 20:04
  • $\begingroup$ I mean the latter. The eigenvalues "should" be clustered around $\pm1$, but practically, get spread out a bit, while still respecting the upper bound (but not the lower). Typically, of the set closer to $+1$, the vast majority of them are almost exactly $1$. $\endgroup$ – Victor Liu Apr 9 '14 at 21:41

A thing you might try:

1) perform a few iterations of the matrix sign iteration $A\mapsto \frac{1}{2}(A+A^{-1})$; the eigenvectors are unchanged, while the eigenvalues converge quadratically to $\pm 1$. When $A-A^{-1}$ is small enough, stop the iteration.

2) compute the kernel of $A-I$.

More information on the matrix sign iteration on the book N. Higham, Functions of Matrices.

This method trades off eigensolves for QR factorizations; it might be faster than QR, depending on the size of the matrices, of the perturbation, and other machine-related factors difficult to quantify.


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.