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

M. Nagy, M. Laurent, A. Varvitsiotis

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

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 k ≥ 2. In other words, for k ≥ 2, it is NP-hard to test membership in the rank constrained elliptope Ek(G) , defined by the set of all partial matrices with an all-ones diagonal and 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 Ek(G) is also NP-hard for any fixed integer k ≥ 2.
Original languageEnglish
Title of host publicationDiscrete Geometry and Optimization
EditorsK. Bezdek, A. Deza, Y. Ye
Place of PublicationHeidelberg
PublisherSpringer Verlag
Pages105-120
Number of pages336
ISBN (Print)9783319001999
Publication statusPublished - 2013

Publication series

NameFields Institute Communications
Number69

Fingerprint Dive into the research topics of 'Complexity of the positive semidefinite matrix completion problem with a rank constraint'. Together they form a unique fingerprint.

Cite this