11
$\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.

Improve this question
$\endgroup$
4
  • $\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, 2010 at 17:11
  • $\begingroup$ I stressed worst-case in my question, so I think this is fair... $\endgroup$
    – Lev Reyzin ♦
    Nov 18, 2010 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, 2010 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, 2010 at 20:54

2 Answers 2

Reset to default
5
$\begingroup$

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.

Improve this answer
$\endgroup$
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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