Positive semidefinite rank

Abstract

Let M be a p-by-q matrix with nonnegative entries. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices $A_i,B_j$ of size $k\times k$ such that $M_{ij}=\text{trace}(A_i{B}_j)$. The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects.

35 pages

References in corpus (2)

• Testing the Hilbert space dimension
• A lower bound on the dimension of a quantum system given measured data

Cited by in corpus (28)

• Identifying Nonconvexity in the Sets of Limited-Dimension Quantum Correlations
• Sparse sum-of-squares certificates on finite abelian groups
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Matrices with high completely positive semidefinite rank
• Shared randomness and device-independent dimension witnessing
• Communication of partial ignorance with qubits
• Simple Information Processing Tasks with Unbounded Quantum Advantage
• Algorithms for Positive Semidefinite Factorization
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Lifting for Simplicity: Concise Descriptions of Convex Sets
• Equivariant semidefinite lifts and sum-of-squares hierarchies
• Completely positive semidefinite rank
• Tensor decompositions on simplicial complexes with invariance
• Learning optimal quantum models is NP-hard
• Separability for mixed states with operator Schmidt rank two
• Two results on the size of spectrahedral descriptions
• Noncommutative polynomials describing convex sets
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• On polyhedral approximations of the positive semidefinite cone
• Maximal Elements of Quantum Communication
• Polynomial decompositions with invariance and positivity inspired by tensors
• Equivariant semidefinite lifts of regular polygons
• Approximate tensor decompositions: disappearance of many separations
• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
• Representability for Quantum Theory beyond Particle-Number Conservation
• Random Exclusion Codes: Quantum Advantages of Single-Shot Communication
• Approximate Completely Positive Semidefinite Factorizations and their Ranks