1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – Suvrit
    Commented Mar 23, 2013 at 22:53
  • $\begingroup$ I edited that part of the question. $\endgroup$
    – Marcin Kotowski
    Commented Mar 23, 2013 at 23:09

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .