Complexity of the positive semidefinite matrix completion problem with a rank constraint.
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. Equivalently, for k ≥ 2, it is NP-hard to test membership in the rank constrained elliptope Ek(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 Ek(G) is also NP-hard for any fixed integer k ≥ 2.
|Keywords||Matrix completion, semidefinite programming, graph realization.|
|THEME||Other (theme 6)|
|Publisher||Springer, Fields Institute Communications, vol. 69|
|Editor||K. Bezdek , A. Deza , Y. Ye|
|Project||Spinoza prijs Lex Schrijver , Semidefinite programming and combinatorial optimization|
Eisenberg-Nagy, M, Laurent, M, & Varvitsiotis, A. (2013). Complexity of the positive semidefinite matrix completion problem with a rank constraint. In K Bezdek, A Deza, & Y Ye (Eds.), Discrete Geometry and Optimization (pp. 105–120). Springer, Fields Institute Communications, vol. 69.