Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
From MaRDI portal
(Redirected from Publication:304255)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5968745 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1933860 (Why is no real title available?)
- scientific article; zbMATH DE number 1421280 (Why is no real title available?)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- An information complexity approach to extended formulations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Combinatorial bounds on nonnegative rank and extended formulations
- Common information and unique disjointness
- Decomposable Tensors as a Quadratic Variety
- Expressing combinatorial optimization problems by linear programs
- Finding approximately rank-one submatrices with the nuclear norm and \(\ell_1\)-norm
- Fixed points of the EM algorithm and nonnegative rank boundaries
- Fractional Covers and Communication Complexity
- Gaussian elimination is not optimal
- Invariant Semidefinite Programs
- Lectures on algebraic statistics
- Lifts of Convex Sets and Cone Factorizations
- Lower bounds in communication complexity
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- On maximum, typical and generic ranks
- On multiplication of 2 \(\times\) 2 matrices
- On the complexity of nonnegative matrix factorization
- On the computational complexity of membership problems for the completely positive cone and its dual
- On the cp-rank and minimal cp factorizations of a completely positive matrix
- On the fractional intersection number of a graph
- On the geometric interpretation of the nonnegative rank
- On the hardness of approximating minimization problems
- On the ratio of optimal integral and fractional covers
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Perturbation of matrices and nonnegative rank with a view toward statistical models
- Positive definite completions of partial Hermitian matrices
- Positive semidefinite rank
- Regularizing the abstract convex program
- Self-Scaled Barriers and Interior-Point Methods for Convex Programming
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Stochastic factorizations, sandwiched simplices and the topology of the space of explanations
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- Sums of even powers of real linear forms
- Symmetric Tensors and Symmetric Tensor Rank
- Symmetry groups, semidefinite programs, and sums of squares
- Tensors of nonnegative rank two
- The common information of two dependent random variables
- The convex geometry of linear inverse problems
Cited in
(13)- Bounding the separable rank via polynomial optimization
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- Dimension reduction for semidefinite programs via Jordan algebras
- A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Algebraic boundary of matrices of nonnegative rank at most three
- Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Positive semidefinite rank and nested spectrahedra
- On the linear extension complexity of regular \(n\)-gons
- Fixed points of the EM algorithm and nonnegative rank boundaries
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
This page was built for publication: Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q304255)
