##
HISTORICAL TOUR ON THE NONNEGATIVE RANK

NICOLAS GILLIS

The nonnegative rank of a nonnegative matrix is the minimum number of nonnegative
rank-one matrices whose sum is equal to that nonnegative matrix. The notion of
nonnegative rank appeared in the 70’s in the linear algebra community [1]; see [2] for an
early survey. Although the nonnegative rank seems at ﬁrst sight to be a natural
extension of the usual rank of a matrix, it leads to many intriguing questions and its
properties are rather diﬀerent than that of the rank. For example, the nonnegative rank
is NP-hard to compute in general (Vavasis, 2010), and there exists a class of \(n\)-by-\(n\)
nonnegative matrices whose usual rank is equal to 3 but whose nonnegative rank is at
least \(\sqrt{2n}\) (Fiorini, Rothvoss and Tiwary, 2012).

The main goal of this talk is twofold. First, we will highlight some key properties
and results on the nonnegative rank with an historical ﬂavour. This includes
its geometric interpretation, the gap between the rank and the nonnegative
rank, computational complexity results, and the uniqueness of nonnegative rank
factorizations. Second, we will review applications where the nonnegative rank arises,
including analytical chemistry (Wallace, 1960), geoscience and remote sensing
(Imbrie and Van Andel, 1963), computational geometry (Silio 1979, Aggarwal et
al. 1989), probability (Suppes and Zanotti, 1981), extended formulations in
combinatorial optimization (Yannakakis, 1991), and unsupervised data analysis where
nonnegative matrix factorization (NMF, that looks for low-rank approximations with
nonnegativity constraint on the factors) has been particularly impactful (Lee and Seung,
1999).

This talk is partly based on the book [3]; in particular Chapter 1.4 (Introduction -
History) and Chapter 3 (Nonnegative Rank).

### References

[1]
A. Berman and R.J. Plemmons, Rank Factorization of Nonnegative Matrices. SIAM Review
15(3):655, (1973).

[2]
J.E. Cohen and U.G. Rothblum, Nonnegative ranks, Decompositions and Factorization of
Nonnegative Matrices. Linear Algebra and its Applications 190:149-168, (1993).

[3]
Nicolas Gillis, Nonnegative Matrix Factorization. SIAM, Philadelphia, 2020.

University of Mons

Email address: nicolas.gillis@umons.ac.be