0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 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, 2022 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$
    – Wolfgang Bangerth
    Jan 13, 2022 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$
    – Lutz Lehmann
    Jan 13, 2022 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$
    – Lutz Lehmann
    Jan 13, 2022 at 10:59
  • $\begingroup$ Is your matrix sparse/structured in some way? (ie fast matrix-vector products?) Is it symmetric? $\endgroup$
    – rchilton1980
    Jan 14, 2022 at 1:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.