# Robust generalization of matrix rank

I am looking for robust generalizations of matrix rank.

Think of the the following problem: A big matrix of low rank is perturbed by random noise, such that it becomes a full-rank matrix. Is there a generalization of matrix rank that still 'sees' that the perturbed matrix is close to a low-rank matrix?

• If a matrix $A$ is close to one of low rank, then I would guess that some of its singular values (eigenvalues of $A^*A$) are very small, albeit nonzero. So you could look for a spectral gap for $A^*A$ and consider only eigenvalues above that. – Sebastian Goette Jan 7 '16 at 13:28
• search for "stable rank"... – Suvrit Jan 7 '16 at 13:28
• Other pointers to the literature are "numerical rank" or "$\varepsilon$-rank" (trickier to search for, because Google doesn't understand LaTeX). What you will find there is essentially the suggestion of Sebastian Goette: compute singular values, and treat small singular values as zeros. How large "small" can be is very application-specific; a rule of thumb is that if a singular value is smaller than the expected noise level then it should be treated as a zero (or a potential zero). – Federico Poloni Jan 7 '16 at 14:20
• @SebastianGoette so in particular you don't think e.g., users.cms.caltech.edu/~jtropp/conf/Tro09-Column-Subset-SODA.pdf (see column 2) is fitting? Afaik, this quantity is now in "common" use. It does not exactly cover the OP, but may be interesting (esp. because it does not require picking a threshold below which all the singular values can be ignored). – Suvrit Jan 7 '16 at 15:53
• @Suvrit The paper looks good, But my search engine produced things like Stable ranks of subalgebras of the ball algebras instead, which have nothing to do with this problem. Apparently, different communities have their own stable ranks. – Sebastian Goette Jan 7 '16 at 17:39