@inbook{c4a21d4f202b40efa5763fd27cd08273,
title = "Complexity of the positive semidefinite matrix completion problem with a rank constraint",
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.",
author = "M. Nagy and M. Laurent and A. Varvitsiotis",
note = "Pagination: 336",
year = "2013",
language = "English",
isbn = "9783319001999",
series = "Fields Institute Communications",
publisher = "Springer Verlag",
number = "69",
pages = "105--120",
editor = "K. Bezdek and A. Deza and Y. Ye",
booktitle = "Discrete Geometry and Optimization",
address = "Germany",
}