# Estimating the sum of 4th powers of singular values?

Suppose $$A$$ is an $$m\times n$$ matrix with $$\operatorname{Tr}(AA^T)=1$$. Let $$\sigma_i$$ be the vector of singular values of $$A$$. How would I cheaply estimate the following quantity?

$$\rho(A)=\sum_i \sigma_i^4$$

Motivation: $$1/\rho(A)$$ is a measure of "effective rank" of $$AA^T$$, a numerically stable alternative to algebraic rank. Called $$R$$ in Bartlett paper, Definition 3.

• You mean apart from $Tr((AA^T)^2)$? At some point the SVD becomes cheaper than the multiple full matrix products. Commented Jul 18, 2023 at 19:58
• @LutzLehmann thanks, that was a useful tip since that quantity is just the sum over squares of pairwise row dot products, which we can estimate using subset of rows Commented Jul 20, 2023 at 0:17

Following the suggestion of Lutz, sum of fourth powers of singular values is just $$\operatorname{Tr}((AA^T)^2)=\|AA^T\|_F^2=\sum_{ij} \langle a_i, a_j\rangle^2$$ where $$a_i$$ is i'th row of $$A$$
Treating row indices $$i$$,$$j$$ as uniform random variables in $$1\ldots,n$$, we have:
$$\sum_{ij} \langle a_i, a_j\rangle^2=n E_i\langle a_i, a_i\rangle^2+n(n-1)E_{i\ne j}\langle a_i, a_j\rangle^2$$