O(n^2) algorithm to approximate the sum of the log of the singular values of a matrix Given an $M \times N$ matrix of rank $N$ ($M \ge N$) with $i^{th}$ singular value $\sigma_i$, does their exist an $O(M^2)$ algorithm for approximating the sum $ H =\sum_{i=1}^N \log(\sigma_i)$ with absolute error less than $M^{-\alpha}\log(\frac{\sigma_{max}}{\sigma_{min}})$ and $\alpha > 0$? Such an algorithm would be useful for fast computation of the entropy of normal distributions that arise in the probabilistic formulation of linear inverse problems.
 A: $O(M^2)$ is barely enough time to read the entire matrix, let alone to do any meaningful computations.  Suppose for instance that M=N was A was a permutation matrix except with the 1 coefficients replaced by coefficients between 1 and 2, so $\sigma_{max} / \sigma_{min} \sim 2$.  In order to compute H to the desired accuracy, one has to locate every last non-trivial entry of the permutation matrix, which can barely be done in $O(M^2)$ operations (and in fact one has to lose a log or two to do the required high precision arithmetic).
If one is willing to have a little less accuracy (or perhaps if one places some "incoherence"  assumptions on the matrix that spreads it out more than in the above permutation matrix-like example), then there is a chance that random sampling methods would work.  Under reasonable hypotheses on the matrix, the singular values of a randomly selected set of rows or columns (or a random minor) are approximately proportional to the singular values of the whole.  There is a certain amount of literature on this subject (see e.g. this paper).
