8
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sebastian Goette
    Commented Jan 7, 2016 at 13:28
  • 1
    $\begingroup$ search for "stable rank"... $\endgroup$
    – Suvrit
    Commented Jan 7, 2016 at 13:28
  • 2
    $\begingroup$ 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). $\endgroup$
    – Federico Poloni
    Commented Jan 7, 2016 at 14:20
  • 1
    $\begingroup$ @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). $\endgroup$
    – Suvrit
    Commented Jan 7, 2016 at 15:53
  • $\begingroup$ @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. $\endgroup$
    – Sebastian Goette
    Commented Jan 7, 2016 at 17:39

2 Answers 2

Reset to default
1
$\begingroup$

The rank of a fuzzy matrix and its evaluation

A new type of matrix rank, which is called margin rank in this article, is introduced to a fuzzy matrix defined to be rectangular array of fuzzy numbers. The new rank is, in general, a real number and consistent with the conventional integer-valued rank, defined for the crisp matrix. The margin rank indicates the margin of retaining the rank of the mean matrix, which enables us to represent the grade of some characteristics described by the ordinary rank of a matrix. In this article the definition of the new rank and a procedure for its evaluation are shown with several examples.

Improve this answer
$\endgroup$
0
$\begingroup$

You can perform Principle Component Analysis and consider the rank of the resulting matrix. This is similar to what Sebastian Goette suggested.

Improve this answer
$\endgroup$

You must log in to answer this question.

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