Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
arXiv:1404.3240 · doi:10.1007/s10107-015-0937-7
Abstract
The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of "positive" ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contribution of the paper is a new method to obtain lower bounds for such ranks which improve on previously known bounds. Additionally the bounds we propose can be computed by semidefinite programming. The idea of the lower bound relies on an atomic norm approach where the atoms are self-scaled according to the vector (or matrix, in the case of nonnegative rank) of interest. This results in a lower bound that is invariant under scaling and that is at least as good as other existing norm-based bounds. We mainly focus our attention on the two important cases of nonnegative rank and cp-rank where our bounds satisfying interesting properties: For the nonnegative rank we show that our lower bound can be interpreted as a non-combinatorial version of the fractional rectangle cover number, while the sum-of-squares relaxation is closely related to the Lovász theta number of the rectangle graph of the matrix. We also prove that the lower bound inherits many of the structural properties satisfied by the nonnegative rank such as invariance under diagonal scaling, subadditivity, etc. We also apply our method to obtain lower bounds on the cp-rank for completely positive matrices. In this case we prove that our lower bound is always greater than or equal the plain rank lower bound, and we show that it has interesting connections with combinatorial lower bounds based on edge-clique cover number.
References in corpus (10)
- The Convex Geometry of Linear Inverse Problems
- Symmetry groups, semidefinite programs, and sums of squares
- Lifts of convex sets and cone factorizations
- On the Geometric Interpretation of the Nonnegative Rank
- Positive semidefinite rank
- Fixed points of the EM algorithm and nonnegative rank boundaries
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Invariant semidefinite programs
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- The matching polytope has exponential extension complexity
Cited by in corpus (10)
- Fixed points of the EM algorithm and nonnegative rank boundaries
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Dimension reduction for semidefinite programs via Jordan algebras
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- On the Linear Extension Complexity of Regular n-gons
- A Gramian Description of the Degree 4 Generalized Elliptope
- Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization