Some upper and lower bounds on PSD-rank

DOI10.1007/S10107-016-1052-0zbMATH Open1362.15007arXiv1407.4308OpenAlexW1611942784MaRDI QIDQ517316FDOQ517316

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)

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.

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

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

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)

Cites Work

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

Cited In (16)

• Euclidean distance matrices and separations in communication complexity theory
• Algorithms for positive semidefinite factorization
• The complexity of positive semidefinite matrix factorization
• The phaseless rank of a matrix
• Worst-case results for positive semidefinite rank
• 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
• Approximate completely positive semidefinite factorizations and their ranks
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• 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)