Worst-case results for positive semidefinite rank

DOI10.1007/s10107-015-0867-4zbMath1344.90046arXiv1305.4600OpenAlexW2079335920MaRDI QIDQ745690

Richard Z. Robinson, 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/1305.4600

zbMATH Keywords

semidefinite programmingmatrix factorizationrepresentations of polytopes

Mathematics Subject Classification ID

Factorization of matrices (15A23) Semidefinite programming (90C22) (n)-dimensional polytopes (52B11)

Related Items

Rank functions of tropical matrices, Heuristics for exact nonnegative matrix factorization, Approximation Limits of Linear Programs (Beyond Hierarchies), Matrices of Bounded Psd Rank are Easy to Detect, On representing the positive semidefinite cone using the second-order cone, An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem, On Ranks of Regular Polygons, The Complexity of Positive Semidefinite Matrix Factorization, Positive semidefinite rank and nested spectrahedra, The Phaseless Rank of a Matrix, Polygons as sections of higher-dimensional polytopes, Algorithms for positive semidefinite factorization, Positive semidefinite rank, Semidefinite Descriptions of the Convex Hull of Rotation Matrices, A Semidefinite Hierarchy for Containment of Spectrahedra, Approximate cone factorizations and lifts of polytopes

Cites Work

• Polytopes of minimum positive semidefinite rank
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Extended formulations for polygons
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• 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
• On the geometric interpretation of the nonnegative rank
• Combinatorial bounds on nonnegative rank and extended formulations
• An upper bound for nonnegative rank
• On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• On the Complexity of Nonnegative Matrix Factorization
• Lifts of Convex Sets and Cone Factorizations
• Linear vs. semidefinite extended formulations
• An Almost Optimal Algorithm for Computing Nonnegative Rank
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Unnamed Item
• Unnamed Item