Fetching the paper…

Reading the bibliography…

2016

The complexity of positive semidefinite matrix factorization

Shitov, Yaroslav

Original
PDF
Post on X

Understand

Let $A$ be a matrix with nonnegative real entries.

The PSD rank of $A$ is the smallest integer $k$ for which there exist $k\times k$ real PSD matrices $B_1,\ldots,B_m$, $C_1,\ldots,C_n$ satisfying $A(i|j)=\operatorname{tr}(B_iC_j)$ for all $i,j$.
This paper determines the computational complexity status of the PSD rank.
Namely, we show that the problem of computing this function is polynomial-time equivalent to the existential theory of the reals.

The complexity of positive semidefinite matrix factorization · Around

Built on

D. V. Grigoriev, N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, 5 (1988) 37–64
1988
Earlier work this paper cites.
M. Yannakakis, Expressing combinatorial optimization problems by linear programs, Comput. System Sci. 43 (1991) 441–466
1991
Earlier work this paper cites.
S. Vavasis, On the complexity of nonnegative matrix factorization, SIAM J. Optimization 20 (2009) 1364–1377
2009
Earlier work this paper cites.
S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds, Proceedings of the Forty-fourth Annual Symposium on Theory of Computing (2012) 95–106
2012
Earlier work this paper cites.

Similar

J. Matoušek, Intersection graphs of segments and ∃ ℝ \exists\mathbb{R} , preprint (2014) arXiv:1406.2326
Original
2014
Cited alongside, same era.
H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, R. R. Thomas, Positive semidefinite rank, Mathematical Programming 153 (2015) 133–177
2015
Cited alongside, same era.
J. Gouveia, R. Z. Robinson, R. R. Thomas, Worst-case results for positive semidefinite rank, Mathematical Programming 153 (2015) 201–212
2015
Cited alongside, same era.

Then

J. R. Lee, P. Raghavendra, D. Steurer, Lower bounds on the size of semidefinite programming relaxations, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (2015) 567–576
2015
Later among the works it cites.
H. Fawzi, J. Gouveia, R. Z. Robinson, Rational and real positive semidefinite rank can be different, Operations Research Letters 44 (2016) 59–60
2016
Closest in time.
Y. Shitov, A short proof that NMF is NP-hard, preprint (2016) arXiv:1605.04000
Original
2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…