Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint

DOI10.1007/978-3-319-00200-2_7zbMath1272.68140arXiv1203.6602OpenAlexW2135628341MaRDI QIDQ2848995

Marianna. E.-Nagy, Antonios Varvitsiotis, Monique Laurent

Publication date: 13 September 2013

Published in: Discrete Geometry and Optimization (Search for Journal in Brave)

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

zbMATH Keywords

correlation matrixelliptopepsd matrix completion

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Unique low rank completability of partially filled matrices, Solving rank-constrained semidefinite programs in exact arithmetic, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, Symmetric completions of cycles and bipartite graphs, A new graph parameter related to bounded rank positive semidefinite matrix completions, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

Cites Work

• Unnamed Item
• The real positive semidefinite completion problem for series-parallel graphs
• Realizability of graphs
• Realizability of graphs in three dimensions
• Extremal correlation matrices
• Orthogonal vector coloring
• The minimum rank of symmetric matrices described by a graph: a survey
• Geometric algorithms and combinatorial optimization
• On the \(p\)-ranks of net graphs
• On the complexity of semidefinite programs
• An exact duality theory for semidefinite programming and its complexity implications
• Multiplicities of eigenvalues and tree-width of graphs
• Steinitz representations of polyhedra and the Colin de Verdière number
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Orthogonal representations over finite fields and the chromatic number of graphs
• Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems
• The Gram Dimension of a Graph
• Grothendieck inequalities for semidefinite programs with rank constraint
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• On the cut polytope
• The real positive definite completion problem: cycle completability
• Geometry of cuts and metrics