Some upper and lower bounds on PSD-rank

DOI10.1007/S10107-016-1052-0MaRDI QIDQ517316zbMATH OpenOpenAlexFDO

Authors Troy Lee, Zhaohui Wei, Ronald de Wolf

Publication date 23 March 2017

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

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

zbMATH Keywords

extended formulationpositive semidefinite factorizationpositive semidefinite ranksemidefinite programmingslack matrix

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Factorization of matrices (15A23) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Semidefinite programming (90C22)

Abstract: Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.

Review text

Let \(A\) be a nonnegative \(m\)-by-\(n\) matrix. A positive semidefinite factorization of size \(r\) of \(A\) is given by \(r\)-by-\(r\) positive semidefinite matrices \(E_1, \dots , E_m\) and \(F_1, \dots , F_n\) satisfying \(A(i, j) = \text{Tr}(E_i, F_j)\) for all \(i, j\). The positive semidefinite rank (PSD-rank) of \(A\) is the smallest \(r\) such that \(A\) has a positive semidefinite factorization of size \(r\). The PSD-rank has applications to combinatorial optimization and communication complexity. The authors investigate properties of the PSD-rank; they study several bounds on the PSD-rank with particular attention to lower bounds.

Recommendations

• Positive semidefinite rank
• The complexity of positive semidefinite matrix factorization
• Worst-case results for positive semidefinite rank
• Completely positive semidefinite rank
• Matrices of bounded psd rank are easy to detect

Cites work

• Communication Complexity
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• Lifts of Convex Sets and Cone Factorizations
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Lower bounds on the size of semidefinite programming relaxations
• On Polyhedral Approximations of the Second-Order Cone
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Positive semidefinite rank
• Quantum strategic game theory

Cited in

(17)

• Euclidean distance matrices and separations in communication complexity theory
• Algorithms for positive semidefinite factorization
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Two results on the size of spectrahedral descriptions
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• A lower bound on the positive semidefinite rank of convex bodies
• Matrices of bounded psd rank are easy to detect
• Communication of partial ignorance with qubits
• The phaseless rank of a matrix
• The complexity of positive semidefinite matrix factorization
• Communication tasks in operational theories
• Approximate completely positive semidefinite factorizations and their ranks
• Complex psd-minimal polytopes in dimensions two and three
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Tight bounds for the randomized and quantum communication complexities of equality with small error
• Positive semidefinite rank
• Worst-case results for positive semidefinite rank

This page was built for publication: Some upper and lower bounds on PSD-rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517316)