# Expected rank - computable approximations

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.

-
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

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.