Nonnegative rank (linear algebra)

From Wikipedia, the free encyclopedia

In linear algebra, the nonnegative rank of a nonnegative matrix is the smallest number of nonnegative rank-one matrices into which the matrix can be decomposed additively.

Given a nonnegative $m \times n$ matrix A the nonnegative rank of A, denoted by for example with $n n r a n k (A)$ , satisfies: $rank(A) \leq nnrank(A) \leq \min(m,n)$ , where rank(A) denotes the rank of a general matrix A.

[edit] Complexity

Given a nonnegative $m \times n$ matrix A, the nonnegative rank determination problem is to find the nonnegative rank of $A$ . This problem is proved to be NP-hard in [3].

[edit] References

[1] J. Cohen and U. Rothblum. "Nonnegative ranks, decompositions and factorizations of nonnegative matrices". Linear Algebra and its Applications, 190:149–168, 1993.

[2] Abraham Berman and Robert J. Plemmons. Nonnegative Matrices in the Mathematical Sciences, SIAM

[3] Stephen Vavasis, On the complexity of nonnegative matrix factorization, arXiv:0708.4149