# Eigen-decomposition one eigenpair by one eigenpair?

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.

• 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.
– Community Bot
Jan 12 at 18:36
• 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. Jan 13 at 5:30
• 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. Jan 13 at 8:58
• @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. Jan 13 at 10:59
• Is your matrix sparse/structured in some way? (ie fast matrix-vector products?) Is it symmetric? Jan 14 at 1:58