Lower bounds on nonnegative rank via nonnegative nuclear norms

Understand

The nonnegative rank of an entrywise nonnegative matrix A of size mxn is the smallest integer r such that A can be written as A=UV where U is mxr and V is rxn and U and V are both nonnegative.

• The nonnegative rank arises in different areas such as combinatorial optimization and communication complexity.
• Computing this quantity is NP-hard in general and it is thus important to find efficient bounding techniques especially in the context of the aforementioned applications.
• In this paper we propose a new lower bound on the nonnegative rank which, unlike most existing lower bounds, does not explicitly rely on the matrix sparsity pattern and applies to nonnegative matrices with arbitrary support.