On the Geometric Interpretation of the Nonnegative Rank

Abstract

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. We show that computing this quantity is equivalent to a problem in polyhedral combinatorics, and fully characterize its computational complexity. This in turn sheds new light on the nonnegative rank problem, and in particular allows us to provide new improved lower bounds based on its geometric interpretation. We apply these results to slack matrices and linear Euclidean distance matrices and obtain counter-examples to two conjectures of Beasly and Laffey, namely we show that the nonnegative rank of linear Euclidean distance matrices is not necessarily equal to their dimension, and that the rank of a matrix is not always greater than the nonnegative rank of its square.

References in corpus (2)

• Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization
• Computing a Nonnegative Matrix Factorization -- Provably

Cited by in corpus (28)

• Lifts of convex sets and cone factorizations
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Positive semidefinite rank
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Heuristics for Exact Nonnegative Matrix Factorization
• Introduction to Nonnegative Matrix Factorization
• Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Simple Information Processing Tasks with Unbounded Quantum Advantage
• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Lifting for Simplicity: Concise Descriptions of Convex Sets
• Polytopes of Minimum Positive Semidefinite Rank
• A Universality Theorem for Nested Polytopes
• On the Linear Extension Complexity of Regular n-gons
• An Approximate Shapley-Folkman Theorem
• Worst-Case Results For Positive Semidefinite Rank
• Symmetric Nonnegative Matrix Trifactorization
• Approximate cone factorizations and lifts of polytopes
• Completely positive factorizations associated with Euclidean distance matrices corresponding to an arithmetic progression
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Nonnegative rank depends on the field II
• An upper bound for nonnegative rank
• Lifts of Non-compact Convex Sets and Cone Factorizations
• Time series forecasting from partial observations via Non-negative Matrix Factorization
• On the Similarity to Nonnegative and Metzler Hessenberg Forms
• Matrix product constraints by projection methods
• Polynomial size linear programs for problems in P