The Complexity of Positive Semidefinite Matrix Factorization

DOI10.1137/16M1080616zbMath1370.15013arXiv1606.09065MaRDI QIDQ5355204

Yaroslav N. Shitov

Publication date: 7 September 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitysemialgebraic setPSD rank

Mathematics Subject Classification ID

Factorization of matrices (15A23) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Lifting for Simplicity: Concise Descriptions of Convex Sets, Bounding the separable rank via polynomial optimization, Smoothing the Gap Between NP and ER, Matrices of Bounded Psd Rank are Easy to Detect, Computing exact solutions of consensus halving and the Borsuk-Ulam theorem, Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices, Algorithms for positive semidefinite factorization, Factoring a band matrix over a semiring, Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Communication tasks in operational theories

Cites Work

• Positive semidefinite rank
• Worst-case results for positive semidefinite rank
• Solving systems of polynomial inequalities in subexponential time
• 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
• Rational and real positive semidefinite rank can be different
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Realization spaces of 4-polytopes are universal
• Lifts of Convex Sets and Cone Factorizations
• The art gallery problem is ∃ ℝ-complete
• Linear vs. semidefinite extended formulations
• Computing a nonnegative matrix factorization -- provably
• Kapranov rank vs. tropical rank
• Universality of Nash Equilibria