Lower bounds on nonnegative rank via nonnegative nuclear norms
From MaRDI portal
(Redirected from Publication:745679)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4032351 (Why is no real title available?)
- scientific article; zbMATH DE number 1933860 (Why is no real title available?)
- Approximate cone factorizations and lifts of polytopes
- Approximation of the stability number of a graph via copositive programming
- Combinatorial bounds on nonnegative rank and extended formulations
- Communication Complexity
- Computing a nonnegative matrix factorization -- provably
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- Expressing combinatorial optimization problems by linear programs
- Finding approximately rank-one submatrices with the nuclear norm and _1-norm
- Information-theoretic approximations of the nonnegative rank
- Lifts of Convex Sets and Cone Factorizations
- Lower bounds in communication complexity
- Matrix mathematics. Theory, facts, and formulas
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- On the complexity of nonnegative matrix factorization
- On the geometric interpretation of the nonnegative rank
- Polytopes of minimum positive semidefinite rank
- Pre- and Post-Processing Sum-of-Squares Programs in Practice
- Quantum strategic game theory
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Smallest compact formulation for the permutahedron
- Sparse and unique nonnegative matrix factorization through data preprocessing
- Symmetry groups, semidefinite programs, and sums of squares
Cited in
(19)- Information-theoretic approximations of the nonnegative rank
- The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Worst-case results for positive semidefinite rank
- On the nonnegative rank of distance matrices
- 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
- On the geometric interpretation of the nonnegative rank
- A remark on low rank matrix recovery and noncommutative Bernstein type inequalities
- An upper bound for nonnegative rank
- A Yannakakis-type theorem for lifts of affine semigroups
- Two relaxation methods for rank minimization problems
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- An almost optimal algorithm for computing nonnegative rank
- Common Information, Noise Stability, and Their Extensions
- An almost optimal algorithm for computing nonnegative rank
- Nonnegative rank vs. binary rank
- Some upper and lower bounds on PSD-rank
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)
