Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank

DOI10.1007/S10107-015-0937-7zbMATH Open1346.90662arXiv1404.3240OpenAlexW1603610938MaRDI QIDQ304255FDOQ304255

Authors: Hamza Fawzi, Pablo A. Parrilo 

Publication date: 25 August 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1404.3240

Recommendations

• Lower bounds on nonnegative rank via nonnegative nuclear norms
• On the geometric interpretation of the nonnegative rank
• Lower bounds for maximal cp-ranks of completely positive matrices and tensors
• Some upper and lower bounds on PSD-rank
• Worst-case results for positive semidefinite rank

Mathematics Subject Classification ID

Convex programming (90C25) Factorization of matrices (15A23) Positive matrices and their generalizations; cones of matrices (15B48)

Cites Work

• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Title not available (Why is that?)
• On the complexity of nonnegative matrix factorization
• Semidefinite Programming
• Lectures on algebraic statistics
• Title not available (Why is that?)
• Expressing combinatorial optimization problems by linear programs
• On the ratio of optimal integral and fractional covers
• On the geometric interpretation of the nonnegative rank
• Symmetry groups, semidefinite programs, and sums of squares
• Gaussian elimination is not optimal
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Semidefinite Optimization and Convex Algebraic Geometry
• On maximum, typical and generic ranks
• On multiplication of 2 \(\times\) 2 matrices
• Title not available (Why is that?)
• Sums of even powers of real linear forms
• Title not available (Why is that?)
• Lifts of Convex Sets and Cone Factorizations
• Positive definite completions of partial Hermitian matrices
• The convex geometry of linear inverse problems
• On the computational complexity of membership problems for the completely positive cone and its dual
• Combinatorial bounds on nonnegative rank and extended formulations
• Perturbation of matrices and nonnegative rank with a view toward statistical models
• Lower bounds in communication complexity
• The Matching Polytope has Exponential Extension Complexity
• On the hardness of approximating minimization problems
• On the cp-rank and minimal cp factorizations of a completely positive matrix
• Title not available (Why is that?)
• Regularizing the abstract convex program
• Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
• On the fractional intersection number of a graph
• Fixed points of the EM algorithm and nonnegative rank boundaries
• Tensors of nonnegative rank two
• Invariant Semidefinite Programs
• Stochastic factorizations, sandwiched simplices and the topology of the space of explanations
• Common information and unique disjointness
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• The common information of two dependent random variables
• Decomposable Tensors as a Quadratic Variety
• Fractional Covers and Communication Complexity
• Title not available (Why is that?)
• Symmetric Tensors and Symmetric Tensor Rank
• Finding approximately rank-one submatrices with the nuclear norm and \(\ell_1\)-norm
• An information complexity approach to extended formulations
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Positive semidefinite rank
• Semidefinite programming relaxations for graph coloring and maximal clique problems

Cited In (13)

• A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector
• Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
• On the linear extension complexity of regular \(n\)-gons
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Algebraic boundary of matrices of nonnegative rank at most three
• Bounding the separable rank via polynomial optimization
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Positive semidefinite rank and nested spectrahedra
• Fixed points of the EM algorithm and nonnegative rank boundaries
• Dimension reduction for semidefinite programs via Jordan algebras
• Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks

Uses Software

• YALMIP
• frlib

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)