9
$\begingroup$

This is a specialized version of a previous question: Complexity of Finding the Eigendecomposition of a Matrix .

For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the eigen decomposition. The question is: can we achieve sub-cubic complexity? Thanks.

$\endgroup$
  • $\begingroup$ Does this really need a separate question? Surely if someone knew the answer to this special case they would have said so in the other question. $\endgroup$ – Warren Schudy Nov 18 '10 at 17:11
  • $\begingroup$ I stressed worst-case in my question, so I think this is fair... $\endgroup$ – Lev Reyzin Nov 18 '10 at 17:55
  • 2
    $\begingroup$ Are you sure about that O(N^3) time bound? See my related question about Gaussian elimination. $\endgroup$ – Jeffε Dec 29 '10 at 21:45
  • $\begingroup$ It seems from mathoverflow.net/questions/24287/… you can get $O(n^3)$ for an approximate solution. $\endgroup$ – Lev Reyzin Dec 30 '10 at 20:54
2
$\begingroup$

As I see it, this special case is not easier than the general case. Purely symbolically, you can reduce the problem of finding the singular-value decomposition (SVD) to the problem of diagonalizing a symmetric matrix. One can read off the SVD of M from the eigenvectors and eigenvalues of M* M. Note that the reduction involves only a matrix multiplication to compute M* M. It does not seem that there should be any serious numerical issues.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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