4
$\begingroup$

Consider a matrix $A\in{\bf M}_{n\times m}({\mathbb R})$, whose entries are non-negative. Let $r$ be the rank of $A$.

It is well-known that $A$ decomposes as $x_1y_1^T+\cdots+x_ry_r^T$ with $x_j\in{\mathbb R}^n$ and $y_i\in{\mathbb R}^m$. But is this still true if we require in addition that $x_1,\ldots,y_r$ be non-negative ?

If not, what is the minimal number $s$ of terms in such a non-negative decomposition $x_1y_1^T+\cdots+x_sy_s^T$ ? By minimal, I mean that for every non-negative $n\times m$ matrix $A$ of rank $r$, a non-negative decomposition exists with $s$ terms.

Of course $s\le\min(n,m)$ works because either a row or a column is of the form $xy^T$. If $r=1$, then $s=1$ works (obvious); that is, the answer to the first question is positive.

$\endgroup$

1 Answer 1

6
$\begingroup$

This seems to be the well-known (and difficult) task of computing the nonnegative rank of a matrix.

It seems that the true complexity of computing the nn-rank is unknown, while verifying whether nn-rank equals actual rank is NP-Hard (the Wikipedia page comments on this).

$\endgroup$
3
  • $\begingroup$ Thanks a lot ! I guessed that it should be documented. I didn't know the terminology. $\endgroup$ Feb 19, 2015 at 14:28
  • $\begingroup$ @DenisSerre I think also known as factor rank $\endgroup$
    – Turbo
    Nov 29, 2015 at 19:48
  • $\begingroup$ @Suvrit how about approximating $s$? $\endgroup$
    – user94040
    Oct 27, 2016 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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