Positive semidefinite rank

DOI10.1007/s10107-015-0922-1zbMath1327.90174arXiv1407.4095OpenAlexW3099415239MaRDI QIDQ745689

Richard Z. Robinson, Pablo A. Parrilo, Hamza Fawzi, João Gouveia, Rekha R. Thomas

Publication date: 14 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Factorization of matrices (15A23) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Lifting for Simplicity: Concise Descriptions of Convex Sets, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Bounding the separable rank via polynomial optimization, Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone, Communication of partial ignorance with qubits, Global completability with applications to self-consistent quantum tomography, Matrices with high completely positive semidefinite rank, Sparse sums of squares on finite abelian groups and improved semidefinite lifts, A Lower Bound on the Positive Semidefinite Rank of Convex Bodies, Matrices of Bounded Psd Rank are Easy to Detect, A strengthened Barvinok-Pataki bound on SDP rank, 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, The Complexity of Positive Semidefinite Matrix Factorization, Tensor decompositions on simplicial complexes with invariance, Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting), Maximum semidefinite and linear extension complexity of families of polytopes, Positive semidefinite rank and nested spectrahedra, Lifts of non-compact convex sets and cone factorizations, Euclidean distance matrices and separations in communication complexity theory, Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices, Correlation matrices, Clifford algebras, and completely positive semidefinite rank, Classical information storage in an \(n\)-level quantum system, Positively factorizable maps, Approximate tensor decompositions: Disappearance of many separations, Four-dimensional polytopes of minimum positive semidefinite rank, The Phaseless Rank of a Matrix, Some upper and lower bounds on PSD-rank, Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization, An Almost Optimal Algorithm for Computing Nonnegative Rank, Completely positive semidefinite rank, Rational and real positive semidefinite rank can be different, Two Results on the Size of Spectrahedral Descriptions, Noncommutative polynomials describing convex sets, Algorithms for positive semidefinite factorization, Factoring a band matrix over a semiring, A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Common Information, Noise Stability, and Their Extensions, On Polyhedral Approximations of the Positive Semidefinite Cone, New limits of treewidth-based tractability in optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polytopes of minimum positive semidefinite rank
• On vector configurations that can be realized in the cone of positive matrices
• On the nonnegative rank of distance matrices
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Worst-case results for positive semidefinite rank
• The algebraic degree of semidefinite programming
• Complexity measures of sign matrices
• 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
• Expressing combinatorial optimization problems by linear programs
• A remark on the rank of positive semidefinite matrices subject to affine constraints
• On the geometric interpretation of the nonnegative rank
• Combinatorial bounds on nonnegative rank and extended formulations
• Rational and real positive semidefinite rank can be different
• Principal component analysis.
• Hyperbolic programs, and their derivative relaxations
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Compressibility of Positive Semidefinite Factorizations and Quantum Models
• Stochastic factorizations, sandwiched simplices and the topology of the space of explanations
• Testing the Dimension of Hilbert Spaces
• Perturbation of Matrices and Nonnegative Rank with a View toward Statistical Models
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone
• On the Complexity of Nonnegative Matrix Factorization
• Principal component analysis in linear systems: Controllability, observability, and model reduction
• Semidefinite Representation for Convex Hulls of Real Algebraic Curves
• Semidefinite Programming
• Semidefinite Optimization and Convex Algebraic Geometry
• Lifts of Convex Sets and Cone Factorizations
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Learning the parts of objects by non-negative matrix factorization
• Linear vs. semidefinite extended formulations
• Computing a nonnegative matrix factorization -- provably
• Mathematical Description of Linear Dynamical Systems
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• A Survey of the S-Lemma
• Lower bounds in communication complexity based on factorization norms