SVD or PCA can be used find the largest eigenvalue, but at a cost of $O(n^3)$ complexity. Lanczos algorithm runs much faster on a sparse matrix with complexity $O(dn^2)$ where $d$ is the average number of non-zeros in a row. It is better, but still quadratic.

My question is does anyone know any sub quadratic algorithm to find just the largest eigenvalue. It can be a very approximate algorithm that just capture the magnitude of the largest eigenvalue.

  • $\begingroup$ That depends on what you define as Lanczos, I guess. Your stated complexity $O(dn^2)$ for Lanczos assumes that you used $n$ Lanczos steps for a theoretically exact triangularization (in the absence of rounding errors). But that is not how you should use Lanczos in practice, both accuracy and speed will be bad if you apply it so naively. Better ask that sort of question at scicomp.stackexchange.com, they can give you practical advice how to efficiently solve this sort of problem (for example by using a suitable library). $\endgroup$ Jun 27, 2017 at 20:13


Your Answer

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

Browse other questions tagged or ask your own question.