On the Geometric Interpretation of the Nonnegative Rank

Understand

The nonnegative rank of a nonnegative matrix is the minimum number of nonnegative rank-one factors needed to reconstruct it exactly.

• The problem of determining this rank and computing the corresponding nonnegative factors is difficult; however it has many potential applications, e.g., in data mining, graph theory and computational geometry.
• In particular, it can be used to characterize the minimal size of any extended reformulation of a given combinatorial optimization program.
• In this paper, we introduce and study a related quantity, called the restricted nonnegative rank.