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 proceeding › Chapter › Scientific › peer-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

Matrix Completion Problem
Positive Semidefinite Matrix
NP-complete problem
Partial Matrix
Integer
Symmetric matrix
Decision problem
Convex Hull
Partial

Cite this

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). (Fields Institute Communications; No. 69). Heidelberg: Springer Verlag.
Nagy, M. ; Laurent, M. ; Varvitsiotis, A. / Complexity of the positive semidefinite matrix completion problem with a rank constraint. Discrete Geometry and Optimization. editor / K. Bezdek ; A. Deza ; Y. Ye. Heidelberg : Springer Verlag, 2013. pp. 105-120 (Fields Institute Communications; 69).
@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",

}

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. Fields Institute Communications, no. 69, Springer Verlag, Heidelberg, pp. 105-120.

Complexity of the positive semidefinite matrix completion problem with a rank constraint. / Nagy, M.; Laurent, M.; Varvitsiotis, A.

Discrete Geometry and Optimization. ed. / K. Bezdek; A. Deza; Y. Ye. Heidelberg : Springer Verlag, 2013. p. 105-120 (Fields Institute Communications; No. 69).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific › peer-review

TY - CHAP

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

AU - Nagy, M.

AU - Laurent, M.

AU - Varvitsiotis, A.

N1 - Pagination: 336

PY - 2013

Y1 - 2013

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

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

M3 - Chapter

SN - 9783319001999

T3 - Fields Institute Communications

SP - 105

EP - 120

BT - Discrete Geometry and Optimization

A2 - Bezdek, K.

A2 - Deza, A.

A2 - Ye, Y.

PB - Springer Verlag

CY - Heidelberg

ER -

Nagy M, Laurent M, Varvitsiotis A. Complexity of the positive semidefinite matrix completion problem with a rank constraint. In Bezdek K, Deza A, Ye Y, editors, Discrete Geometry and Optimization. Heidelberg: Springer Verlag. 2013. p. 105-120. (Fields Institute Communications; 69).