2
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\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$ – Thomas Klimpel Jun 27 '17 at 20:13

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.