What is the computational complexity of Eigen Value decomposition of a correlation matrix?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In practice using algorithms in EISPACK or LAPACK on floating point single or double precision symmetric matrices, computing the EVD takes $O(n^3)$ time. The constant hidden within the big $O$ is considerably larger than for Cholesky factorization. In theory (but such algorithms are not practically useful for typical double precision floating point computations on matrices with dimensions in the thousands to 10's of thousands), you can do as well as matrix multiplication, for which the best current complexity is if I recall correctly $O(n^{2.376})$. 

