## O(n^2) algorithm to approximate the sum of the log of the singular values of a matrix

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

Isn't this equivalent to finding the determinant of $A^*A$? (which doesn't have, yet, an $O(M^2)$ algorithm) – Dror Speiser Jun 19 2010 at 7:33
Do you expect your matrices to be sparse? – S. Carnahan♦ Jun 19 2010 at 16:55
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).  – Gabriel Mitchell Jun 25 2010 at 16:46

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9275961518287659, "perplexity_flag": "head"}