Welcome to MathOverflow

Question

1

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

flag	asked Jun 25 2011 at 5:20 Yerriswamy 11●1

	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. – S. Sra Jun 25 2011 at 5:30
	And what is your motivation? – András Bátkai Jun 26 2011 at 20:13

Igor Rivin · Answer 1 · 2011-06-26 18:33:49Z UTC

2

See

http://cstheory.stackexchange.com/questions/2611/complexity-of-finding-the-eigendecomposition-of-a-matrix

answered Jun 26 2011 at 18:33

Igor Rivin
31.1k●3●37●71

Brian Borchers · Answer 2 · 2011-06-25 17:13:12Z UTC

3

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

answered Jun 25 2011 at 17:13

Brian Borchers
2,453●1●3●8

	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? – S. Sra Jun 26 2011 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 2011 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 2011 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) – S. Sra Jun 27 2011 at 3:03

Complexity of EVD

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.