Let $A$ be a positive-definite matrix with eigenvalues $e_1, ..., e_n$. I want to compute $\sum\limits_{i=1}^{n} \sqrt{e_i}$ without calculating all eigenvalues first (or rather: with a method faster than calculating all eigenvalues which takes a time of $\mathcal{O}(n^3)$.

The sum of the eigenvalues of a matrix is equal to its trace, i.e. $\sum\limits_{i=1}^{n} e_i = tr(A)$. I could use the Cholesky decomposition of $A = L^T L$. The eigenvalues of $L$ would be $\sqrt{e_i}$, thus $tr(L)$ is the quantity I am looking for, but the cholesky decomposition also has a runtime of $\mathcal{O}(n^3)$.

Is there a faster way to calculate this?

  • $\begingroup$ Do you need absolute accuracy or just reasonably accurate numerical approximation? $\endgroup$
    – Radost
    May 23 '19 at 10:36
  • $\begingroup$ I would take an approximation, although I was hoping for something absolutely accurate (in theory), so that the only comes from computing. $\endgroup$
    – tehfurbolg
    May 23 '19 at 10:55

Observe that $$\sum\limits_{i=1}^{n} \sqrt{e_i} = tr(\sqrt{A})$$ The matrix square root$\sqrt{A}$ can be computed using iterative methods (for example see this), which also require $O(n^3)$ operations. However this can be faster than full eigenvalue decomposition if low accuracy suffices.


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.