5
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ You mean apart from $Tr((AA^T)^2)$? At some point the SVD becomes cheaper than the multiple full matrix products. $\endgroup$ Jul 18, 2023 at 19:58
  • $\begingroup$ @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 $\endgroup$ Jul 20, 2023 at 0:17

1 Answer 1

4
$\begingroup$

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$$

Using 10% of the rows to approximate expectations appears to give reasonable result:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.