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

2012/03/18 by Lee, Troy, Theis, Dirk Oliver
#15B48 #90C22 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1203.3961

Abstract

The positive semidefinite rank of a nonnegative (m× n)-matrix~S is the minimum number~q such that there exist positive semidefinite (q× q)-matrices A₁,…,A_m, B₁,…,B_n such that S(k,ℓ) = tr(A_k^* B_ℓ). 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.

Related

• Worst-Case Results For Positive Semidefinite Rank
• An upper bound for nonnegative rank
• Exploring the bounds on the positive semidefinite rank
• Rational and real positive semidefinite rank can be different
• Some upper and lower bounds on PSD-rank