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
- 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?)
- A Survey of the S-Lemma
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- 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
- 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
(52)- 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
- Tensor decompositions on simplicial complexes with invariance
- A strengthened Barvinok-Pataki bound on SDP rank
- Approximate completely positive semidefinite factorizations and their ranks
- Euclidean distance matrices and separations in communication complexity theory
- Lifting for simplicity: concise descriptions of convex sets
- New limits of treewidth-based tractability in optimization
- Bounding the separable rank via polynomial optimization
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- Matrices with high completely positive semidefinite rank
- Rational and real positive semidefinite rank can be different
- Correlation matrices, Clifford algebras, and completely positive semidefinite rank
- Common Information, Noise Stability, and Their Extensions
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Communication of partial ignorance with qubits
- Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
- On polyhedral approximations of the positive semidefinite cone
- Noncommutative polynomials describing convex sets
- Completely positive semidefinite rank
- Complex psd-minimal polytopes in dimensions two and three
- Classical information storage in an \(n\)-level quantum system
- Maximum semidefinite and linear extension complexity of families of polytopes
- The complexity of positive semidefinite matrix factorization
- Gangster operators and invincibility of positive semidefinite matrices
- Two results on the size of spectrahedral descriptions
- Worst-case results for positive semidefinite rank
- Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Positively factorizable maps
- Lifts of non-compact convex sets and cone factorizations
- An almost optimal algorithm for computing nonnegative rank
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
- Some upper and lower bounds on PSD-rank
- Factoring a band matrix over a semiring
- Polytopes of minimum positive semidefinite rank
- Approximate tensor decompositions: disappearance of many separations
- Global completability with applications to self-consistent quantum tomography
- Positive semidefinite indicator property for norm-numerical range
- Four-dimensional polytopes of minimum positive semidefinite rank
- Algorithms for positive semidefinite factorization
- Positive semidefinite rank and nested spectrahedra
- The phaseless rank of a matrix
- A lower bound on the positive semidefinite rank of convex bodies
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem
- Matrices of bounded psd rank are easy to detect
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)
