Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix

Abstract

The positive semidefinite rank of a nonnegative $(m\times n)$-matrix~$S$ is the minimum number~$q$ such that there exist positive semidefinite $(q\times q)$-matrices $A_1,\dots ,A_m$, $B_1,\dots ,B_n$ 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.

9 pages

References in corpus (2)

• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Polytopes of Minimum Positive Semidefinite Rank

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