Non-negative decomposition of a non-negative matrix

Question

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.

Answer 1

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).