### Abstract

*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

*E*, defined by the set of all partial matrices with an all-ones diagonal and off-diagonal entries specified at the edges of

_{k}(G)*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*(G) is also

_{k}*NP*-hard for any fixed integer

*k*≥ 2.

Original language | English |
---|---|

Title of host publication | Discrete Geometry and Optimization |

Editors | K. Bezdek, A. Deza, Y. Ye |

Place of Publication | Heidelberg |

Publisher | Springer Verlag |

Pages | 105-120 |

Number of pages | 336 |

ISBN (Print) | 9783319001999 |

Publication status | Published - 2013 |

### Publication series

Name | Fields Institute Communications |
---|---|

Number | 69 |

### Fingerprint

### Cite this

*Discrete Geometry and Optimization*(pp. 105-120). (Fields Institute Communications; No. 69). Heidelberg: Springer Verlag.

}

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

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 -