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.