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 first sight to be a natural extension of the usual rank of a matrix, it leads to many intriguing questions and its properties are rather different 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 flavour. 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