Some upper and lower bounds on PSD-rank

DOI10.1007/s10107-016-1052-0zbMath1362.15007arXiv1407.4308OpenAlexW1611942784MaRDI QIDQ517316

Troy Lee, Zhao Hui 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) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Communication of partial ignorance with qubits ⋮ Complex psd-minimal polytopes in dimensions two and three ⋮ Euclidean distance matrices and separations in communication complexity theory ⋮ The Phaseless Rank of a Matrix ⋮ Two Results on the Size of Spectrahedral Descriptions ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Communication tasks in operational theories

Cites Work

• Unnamed Item
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Positive semidefinite rank
• Expressing combinatorial optimization problems by linear programs
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Quantum strategic game theory
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• The Matching Polytope has Exponential Extension Complexity
• Communication Complexity
• Lifts of Convex Sets and Cone Factorizations
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• On Polyhedral Approximations of the Second-Order Cone

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