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

DOI10.1007/978-3-319-00200-2_7MaRDI QIDQ2848995zbMATH OpenOpenAlexFDO

Authors Marianna. E.-Nagy, A. 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

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

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$.

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

Cites work

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

Cited in

(9)

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

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)