Fetching the paper…
Reading the bibliography…
This paper presents various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes.
Expressing combinatorial optimization problems by linear programs
M. Yannakakis · 1991
Earlier work this paper cites.
On the Computational Complexity and Geometry of the First-Order Theory of the Reals
J. Renegar · 1992
Earlier work this paper cites.
Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
J.E. Cohen and U.G. Rothblum · 1993
Earlier work this paper cites.
Real Algebraic Geometry
J. Bochnak, M. Coste, M. Roy · 1998
Earlier work this paper cites.
Handbook of Semidefinite Programming
H. Wolkowicz, R. Saigal, L. Vandenberghe · 2000
Earlier work this paper cites.
On the Complexity of Nonnegative Matrix Factorization
S. Vavasis · 2009
Earlier work this paper cites.
Approximation Limits of Linear Programs (Beyond Hierarchies)
G. Braun, S. Fiorini, S. Pokutta, D. Steurer · 2012
Cited alongside, same era.
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf · 2012
Cited alongside, same era.
Extended formulations for polygons
S. Fiorini, T. Rothvoss, H. Tiwary · 2012
Cited alongside, same era.
On the Geometric Interpretation of the Nonnegative Rank
N. Gillis and F. Glineur · 2012
Cited alongside, same era.
Extended Formulations for Combinatorial Polytopes
K. Pashkovich · 2012
Cited alongside, same era.
On the existence of 0 / 1 0/1 polytopes with high semidefinite extension complexity
J. Briët, D. Dadush, S. Pokutta
Cited in the paper.
Combinatorial Bounds on Nonnegative Rank and Extended Formulations
S. Fiorini, V. Kaibel, K. Pashkovich, D.O. Theis · 2013
Closest in time.
Lifts of Convex Sets and Cone Factorizations
J. Gouveia, P.A. Parrilo, R.R. Thomas · 2013
Closest in time.
Polytopes of Minimum Positive Semidefinite Rank
J. Gouveia, R.Z. Robinson, R.R. Thomas · 2013
Closest in time.
An Almost Optimal Algorithm for Computing Nonnegative Rank
A. Moitra · 2013
Closest in time.
An Upper Bound For Nonnegative Rank
Y. Shitov · 2014
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
New lower bounds on nonnegative rank using conic programming
H. Fawzi and P.A. Parrilo
Cited in the paper.
Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix
T. Lee, D.O. Theis
Cited in the paper.