Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is the computational complexity of Eigen Value decomposition of a correlation matrix?

share|improve this question
    
maybe google helps; also, on what model of computation? maybe the fact that your matrix is symmetric matters more than that it is a correlation matrix. –  Suvrit Jun 25 '11 at 5:30
    
And what is your motivation? –  András Bátkai Jun 26 '11 at 20:13
add comment

2 Answers 2

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})$.

share|improve this answer
    
Hi Brian, I don't see it immediately, but is it easy to prove that complexity of eigenvalue decomposition is the same as matrix multiplication? Matrix inversion is certainly there, but since EVD is inherently iterative, and inexact, I find it hard to believe your second paragraph; am I missing something? –  Suvrit Jun 26 '11 at 17:49
    
Like many other similar computations such as solving a linear programming problem, we're talking about the complexity of obtaining an epsilon approximate solution for some accuracy level. Igor's answer includes a link to a cstheory.stackexchange question whose answers include a link to a STOC paper that appears to discuss how to reduce the eigenvalue decomposition to matrix multiplication. I'm certainly not an expert on this stuff- I'm much more interested in what can be done practically. –  Brian Borchers Jun 26 '11 at 19:33
    
If you'd like an explanation of why Strassen-Winograd and other more sophisticated matrix multiplication algorithms don't work well in practice for matrices of size in the thousands to tens of thousands, I'd be happy to explain that- the basic reason is that Strassen's algorithm trades off matrix multiplications for matrix additions, but matrix additions are relatively more expensive than they should be because matrix addition speed is limited by the poor memory bandwidth of contemporary computers. –  Brian Borchers Jun 26 '11 at 19:33
    
Thanks Brian; actually I had totally forgotten---the cs.SE answer links to a STOC paper that I had once skimmed. But indeed, it is not immediate to see that EVD complexity also boils down to matrix multiplication (in the $\epsilon$-accurate sense) –  Suvrit Jun 27 '11 at 3:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.