Positive semidefinite rank

Let M ∈ R p × q be a nonnegative matrix. 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 × k such that M i j = trace ( A i B j ) . The psd rank has many appealing geometric interpretations, including se...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2015-10, Vol.153 (1), p.133-177
Main Authors: Fawzi, Hamza, Gouveia, João, Parrilo, Pablo A., Robinson, Richard Z., Thomas, Rekha R.
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Computation
Full Length Paper
Geometry
Linear programming
Machine learning
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical models
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Matrices (mathematics)
Numerical Analysis
Polyhedra
Polyhedrons
Principal components analysis
Random variables
Representations
Scholarships & fellowships
Studies
System theory
Texts
Theorems
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let M ∈ R p × q be a nonnegative matrix. 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 × k such that M i j = 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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-015-0922-1