Complexity of the positive semidefinite matrix completion problem with a rank constraint

DOI10.1007/978-3-319-00200-2_7zbMATH Open1272.68140arXiv1203.6602OpenAlexW2135628341MaRDI QIDQ2848995FDOQ2848995

Authors: Marianna. E.-Nagy, A. Varvitsiotis, Monique Laurent 

Publication date: 13 September 2013

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

Abstract: We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most $k$. We show that this problem is $NP$-hard for any fixed integer $kge2$. Equivalently, for $kge2$, it is $NP$-hard to test membership in the rank constrained elliptope $E{E}_k(G)$, i.e., the set of all partial matrices with off-diagonal entries specified at the edges of $G$, that can be completed to a positive semidefinite matrix of rank at most $k$. Additionally, we show that deciding membership in the convex hull of $E{E}_k(G)$ is also $NP$-hard for any fixed integer $kge2$.

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

Recommendations

• Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems
• Unique low rank completability of partially filled matrices
• scientific article; zbMATH DE number 1182568
• The CP-matrix completion problem
• The real positive semidefinite completion problem for series-parallel graphs

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)

Cites Work

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

Cited In (8)

• Symmetric completions of cycles and bipartite graphs
• Solving rank-constrained semidefinite programs in exact arithmetic
• DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
• Unique low rank completability of partially filled matrices
• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• A new algorithm for positive semidefinite matrix completion
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property

This page was built for publication: Complexity of the positive semidefinite matrix completion problem with a rank constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848995)