4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Isn't this equivalent to finding the determinant of $A^*A$? (which doesn't have, yet, an $O(M^2)$ algorithm) $\endgroup$ Jun 19, 2010 at 7:33
  • $\begingroup$ Do you expect your matrices to be sparse? $\endgroup$
    – S. Carnahan
    Jun 19, 2010 at 16:55
  • $\begingroup$ I wish I could make some assumptions about the matrix. In reality there is just such a large diversity of applications that result in different kinds of matrices. I suppose I should try to identify a few of my favorite problems and see what can be done (although in light of the response below it seems apparent that O(M^2) might be a bit too naive). $\endgroup$ Jun 25, 2010 at 16:46

1 Answer 1

6
$\begingroup$

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

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