Positive semidefinite rank
From MaRDI portal
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 of size such that . 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.
Recommendations
Cites work
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- A Survey of the S-Lemma
- An almost optimal algorithm for computing nonnegative rank
- Combinatorial bounds on nonnegative rank and extended formulations
- Complexity measures of sign matrices
- Compressibility of Positive Semidefinite Factorizations and Quantum Models
- Computing a nonnegative matrix factorization -- provably
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Expressing combinatorial optimization problems by linear programs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1933860 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 6744339 (Why is no real title available?)
- Hyperbolic programs, and their derivative relaxations
- Learning the parts of objects by non-negative matrix factorization
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- Lower bounds in communication complexity based on factorization norms
- Lower bounds on the size of semidefinite programming relaxations
- Mathematical Description of Linear Dynamical Systems
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- On the complexity of nonnegative matrix factorization
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- On the geometric interpretation of the nonnegative rank
- On the nonnegative rank of distance matrices
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- On vector configurations that can be realized in the cone of positive matrices
- Perturbation of matrices and nonnegative rank with a view toward statistical models
- Polytopes of minimum positive semidefinite rank
- Principal component analysis in linear systems: Controllability, observability, and model reduction
- Principal component analysis.
- Rational and real positive semidefinite rank can be different
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Semidefinite Representation for Convex Hulls of Real Algebraic Curves
- Stochastic factorizations, sandwiched simplices and the topology of the space of explanations
- Testing the dimension of Hilbert spaces
- The algebraic degree of semidefinite programming
- Worst-case results for positive semidefinite rank
Cited in
(57)- A remark on the rank of positive semidefinite matrices subject to affine constraints
- Maximum semidefinite and linear extension complexity of families of polytopes
- Euclidean distance matrices and separations in communication complexity theory
- Completely positive semidefinite rank
- Rational and real positive semidefinite rank can be different
- Algorithms for positive semidefinite factorization
- Positive semidefinite indicator property for norm-numerical range
- A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
- Noncommutative polynomials describing convex sets
- Factoring a band matrix over a semiring
- New limits of treewidth-based tractability in optimization
- Bounding the separable rank via polynomial optimization
- Lifts of non-compact convex sets and cone factorizations
- Positively factorizable maps
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- A strengthened Barvinok-Pataki bound on SDP rank
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Two results on the size of spectrahedral descriptions
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Global completability with applications to self-consistent quantum tomography
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- Matrices with high completely positive semidefinite rank
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Polytopes of minimum positive semidefinite rank
- A lower bound on the positive semidefinite rank of convex bodies
- Matrices of bounded psd rank are easy to detect
- Classical information storage in an \(n\)-level quantum system
- On polyhedral approximations of the positive semidefinite cone
- Lifting for simplicity: concise descriptions of convex sets
- Communication of partial ignorance with qubits
- Four-dimensional polytopes of minimum positive semidefinite rank
- Correlation matrices, Clifford algebras, and completely positive semidefinite rank
- Approximate tensor decompositions: disappearance of many separations
- The phaseless rank of a matrix
- Some upper and lower bounds on PSD-rank
- The complexity of positive semidefinite matrix factorization
- Positive semidefinite rank and nested spectrahedra
- Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
- An almost optimal algorithm for computing nonnegative rank
- Common Information, Noise Stability, and Their Extensions
- Gangster operators and invincibility of positive semidefinite matrices
- Approximate completely positive semidefinite factorizations and their ranks
- An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem
- Complex psd-minimal polytopes in dimensions two and three
- Tensor decompositions on simplicial complexes with invariance
- Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
- Polynomial decompositions with invariance and positivity inspired by tensors
- Multiplicative updates for symmetric-cone factorizations
- Restricted hidden cardinality constraints in causal models
- Signed tropicalization of polar cones
- Tight bounds for the randomized and quantum communication complexities of equality with small error
- Matrix factorization ranks via polynomial optimization
- The extension complexity of polytopes with bounded integral slack matrices
- Sublinear extensions of polygons
- Worst-case results for positive semidefinite rank
This page was built for publication: Positive semidefinite rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745689)
