Back to Search
Start Over
Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Source :
- Springer Berlin Heidelberg
- Publication Year :
- 2015
- Publisher :
- Springer Science and Business Media LLC, 2015.
-
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\'asz 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.
- Subjects :
- Semidefinite programming
021103 operations research
General Mathematics
0211 other engineering and technologies
010103 numerical & computational mathematics
02 engineering and technology
Nonnegative rank
01 natural sciences
Upper and lower bounds
Combinatorics
Matrix (mathematics)
Optimization and Control (math.OC)
Norm (mathematics)
Subadditivity
FOS: Mathematics
Rectangle
0101 mathematics
Communication complexity
Mathematics - Optimization and Control
Software
Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 158
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....cad48b3f3e49aedd7e62f6b8b93cdff9