What is the computational complexity of Eigen Value decomposition of a correlation matrix?
2
-
$\begingroup$ 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. $\endgroup$– SuvritCommented Jun 25, 2011 at 5:30
-
$\begingroup$ And what is your motivation? $\endgroup$– András BátkaiCommented Jun 26, 2011 at 20:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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
-
$\begingroup$ 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? $\endgroup$– SuvritCommented Jun 26, 2011 at 17:49
-
$\begingroup$ 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. $\endgroup$ Commented Jun 26, 2011 at 19:33
-
$\begingroup$ 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. $\endgroup$ Commented Jun 26, 2011 at 19:33
-
$\begingroup$ 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) $\endgroup$– SuvritCommented Jun 27, 2011 at 3:03
$\begingroup$
$\endgroup$
answered Jun 26, 2011 at 18:33