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?
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.