  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. The idea involves computing a certain nuclear norm with nonnegativity
constraints which allows to lower bound the nonnegative rank, in the same way
the standard nuclear norm gives lower bounds on the standard rank. Our lower
bound is expressed as the solution of a copositive programming problem and can
be relaxed to obtain polynomial-time computable lower bounds using semidefinite
programming. We compare our lower bound with existing ones, and we show
examples of matrices where our lower bound performs better than currently known
ones.
