Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm interested in finding the expected rank of some random matrix $A$ (I don't want to specify its distribution right now, since my question makes sense in general).

Computing $\mathbb{E} \ \mathrm{rk}(A)$ is usually infeasible, as rank is a rather awful function to consider or optimize etc. Are there quantities which could serve as proxies for the rank, but whose averages would be easier to compute in this setting? In other words, I'm looking for functions $f(A)$ such that $\mathbb{E}f(A)$ can be computed and $f(A)$ is a reasonable approximation to $\mathrm{rk}(A)$. An example would be $\mathrm{tr}(A)$, which would be close to the rank if the eigenvalues of $A$ are close to $1$.

Since replacing rank with some nicer (e.g. convex) function seems to be a common approach e.g. in optimization, I'd be also interested in references.

share|improve this question
the question needs a little bit more precision: what is $B$? if $B$ is fixed, then the exact rank (not even expected) is just rank of $B$? –  Suvrit Mar 23 '13 at 22:53
I edited that part of the question. –  Marcin Kotowski Mar 23 '13 at 23:09

1 Answer 1

Given the generality with which the question is now phrased, one of the answers you are looking for is (maybe you already thought about it):

The trace norm: $\|A\|_{\mbox{*}} = \sum_i \sigma_i(A)$, that is, the sum of the singular values of $A$. This norm is the "closest" convex proxy to the rank function (in the same sense as $\|x\|_1$ is the convex proxy to $\|x\|_0$, the cardinality function.

Googling for "trace norm" or "nuclear norm" and other such keywords will bring up a lot of useful references.

You might also find the inequalities on this Wikipedia page on Matrix Concentration Inequalities useful.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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