Suppose $A\in\mathbb{R}^{n\times c}$,$u\in\mathbb{R}^n$,$n\gg c$. The time complexity of eigenvalue decomposing directly for matrix $AA^T+\text{diag}(u)$ is $O(n^3)$. And it is easy to avoid $O(n^3)$ for matrix $AA^T+I$. So can we avoid $O(n^3)$ for matrix $AA^T+\text{diag}(u)$? Thanks.



  • 1
    $\begingroup$ There are a few earlier related questions here (see linked): scicomp.stackexchange.com/q/503/713 $\endgroup$ – Kirill Jul 20 '16 at 8:27
  • $\begingroup$ Thanks, it seems that the answer is no. And $AA^T+\text{diag}(u)$ is not diagonally dominant. $\endgroup$ – Echo Jul 22 '16 at 9:26

Your Answer

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

Browse other questions tagged or ask your own question.