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 \(\ell_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
(17)- A remark on low rank matrix recovery and noncommutative Bernstein type inequalities
- Common Information, Noise Stability, and Their Extensions
- On the nonnegative rank of distance matrices
- Information-theoretic approximations of the nonnegative rank
- Bounds on Dimension Reduction in the Nuclear Norm
- An upper bound for nonnegative rank
- Two relaxation methods for rank minimization problems
- Nonnegative rank vs. binary rank
- Worst-case results for positive semidefinite rank
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- An almost optimal algorithm for computing nonnegative rank
- On the geometric interpretation of the nonnegative rank
- An almost optimal algorithm for computing nonnegative rank
- Some upper and lower bounds on PSD-rank
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- On the linear extension complexity of regular \(n\)-gons
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)
