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

semidefinite programmingextended formulationpositive semidefinite rankslack matrixpositive semidefinite factorization

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• 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
• 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

(16)

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

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)