Is it possible to conduct an Eigen-decomposition of a matrix one eigenpair by one eigenpair?

And related to this question, what is the time complexity of truncated eigendecomposition?

I am trying (hard) to find a way to reduce the time complexity of my algorithm which involves the calculation of eigendecomposition of a positive definite matrix. The full eigendecomposition is $O(n^3)$ in general. However, I may not need full eigendecomposition. I only need to stop when the $\lambda_i$, i.e. the $i$-th largest eigenvalue (and its eigenvector), is less than $\epsilon>0$.

Is there a way to do that? We might assume we know the number of eigenvalues greater or equal to $\epsilon$, if necessary, e.g. something like truncated eigendecomposition.

  • 1
    $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Jan 12 at 18:36
  • 1
    $\begingroup$ If you only need the largest eigenvalues, what you are doing sounds like a rank-revealing QR or SVD decomposition to me. Have you looked into that? These are widely implemented operations; you don't have to do it yourself. $\endgroup$ Jan 13 at 5:30
  • 4
    $\begingroup$ The following should already be known, it would be nice if this could be indicated in the question: The power iteration or inverse power iteration (with modifications for complex eigenvalues) give one eigenvalue at a time. One would need to add some matrix reduction or deflation method to get to the next pair. // Subspace iterations extend this concept by iterating several vectors at the same time and forcing them to stay orthogonal or linearly independent in some other way. $\endgroup$ Jan 13 at 8:58
  • $\begingroup$ @FedericoPoloni : That is true. It seems unlikely that one can get a result about the structure of all eigenvalues without using some $O(n^3)$ operations, even if aggressive matrix splitting is used to quickly reduce the dimension. $\endgroup$ Jan 13 at 10:59
  • $\begingroup$ Is your matrix sparse/structured in some way? (ie fast matrix-vector products?) Is it symmetric? $\endgroup$ Jan 14 at 1:58

Your Answer

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

Browse other questions tagged or ask your own question.