Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix
arXiv:1203.3961
Abstract
The positive semidefinite rank of a nonnegative -matrix~ is the minimum number~ such that there exist positive semidefinite -matrices , such that $S(k,\ell) = \mbox{tr}(A_k^* B_\ell)$. The most important, lower bound technique for nonnegative rank is solely based on the support of the matrix S, i.e., its zero/non-zero pattern. In this paper, we characterize the power of lower bounds on positive semidefinite rank based on solely on the support.
arXiv comment9 pages
References in corpus (3)
Cited by in corpus (9)
- Algorithms for Positive Semidefinite Factorization
- Worst-Case Results For Positive Semidefinite Rank
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Some upper and lower bounds on PSD-rank
- Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity
- Computing The Extension Complexities of All 4-Dimensional 0/1-Polytopes
- Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization
- Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices
- Nondeterministic Communication Complexity of Random Boolean Functions