Lower bounds on nonnegative rank via nonnegative nuclear norms

DOI10.1007/S10107-014-0837-2zbMATH Open1327.90202arXiv1210.6970OpenAlexW2067114382MaRDI QIDQ745679FDOQ745679

Pablo A. Parrilo, Hamza Fawzi

Publication date: 14 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1210.6970

Mathematics Subject Classification ID

Convex programming (90C25) Factorization of matrices (15A23) Positive matrices and their generalizations; cones of matrices (15B48)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Complexity of Nonnegative Matrix Factorization
• Computing a nonnegative matrix factorization -- provably
• Expressing combinatorial optimization problems by linear programs
• On the geometric interpretation of the nonnegative rank
• Symmetry groups, semidefinite programs, and sums of squares
• Approximation of the stability number of a graph via copositive programming
• Polytopes of minimum positive semidefinite rank
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Communication Complexity
• Pre- and Post-Processing Sum-of-Squares Programs in Practice
• Lifts of Convex Sets and Cone Factorizations
• Combinatorial bounds on nonnegative rank and extended formulations
• Lower Bounds in Communication Complexity
• The Matching Polytope has Exponential Extension Complexity
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Smallest compact formulation for the permutahedron
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Finding Approximately Rank-One Submatrices with the Nuclear Norm and $\ell_1$-Norm
• Approximate cone factorizations and lifts of polytopes
• Information-theoretic approximations of the nonnegative rank
• Quantum strategic game theory
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States

Cited In (11)

• Information-theoretic approximations of the nonnegative rank
• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• Worst-case results for positive semidefinite rank
• On the linear extension complexity of regular \(n\)-gons
• Bounds on Dimension Reduction in the Nuclear Norm
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• A remark on low rank matrix recovery and noncommutative Bernstein type inequalities
• Two relaxation methods for rank minimization problems
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Common Information, Noise Stability, and Their Extensions
• Some upper and lower bounds on PSD-rank

Uses Software

• YALMIP

This page was built for publication: Lower bounds on nonnegative rank via nonnegative nuclear norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745679)