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

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

2012-03-29

arxiv.org/abs/1203.6602v1

Mathematics

Optimization and Control

18 pages, 3 figures

Scientific paper

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\ge 2$. Equivalently, for $k\ge 2$, it is $\NP$-hard to test membership in the rank constrained elliptope $\EE_k(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 $\EE_k(G)$ is also $\NP$-hard for any fixed integer $k\ge 2$.

Affiliated with

Also associated with

No associations

Rating

Complexity of the positive semidefinite matrix completion problem with a rank constraint does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of the positive semidefinite matrix completion problem with a rank constraint, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of the positive semidefinite matrix completion problem with a rank constraint will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-58340