Lower bounds on nonnegative rank via nonnegative nuclear norms

Abstract

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.

v2: Updated title + minor updates. This is the final version accepted for publication at Mathematical Programming Series B, special issue on "Lifts of Convex Sets". The final publication is available at Springer via http://dx.doi.org/10.1007/s10107-014-0837-2

References in corpus (8)

• Symmetry groups, semidefinite programs, and sums of squares
• Lifts of convex sets and cone factorizations
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Polytopes of Minimum Positive Semidefinite Rank
• Correlation/Communication complexity of generating bipartite states
• Approximate cone factorizations and lifts of polytopes

Cited by in corpus (6)

• Introduction to Nonnegative Matrix Factorization
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• On the Linear Extension Complexity of Regular n-gons
• Worst-Case Results For Positive Semidefinite Rank
• Some upper and lower bounds on PSD-rank
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization