Sum of sqrt of eigenvalues without computing all eigenvalues

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?

• Do you need absolute accuracy or just reasonably accurate numerical approximation? May 23 '19 at 10:36
• I would take an approximation, although I was hoping for something absolutely accurate (in theory), so that the only comes from computing. 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.