zbMATH — the first resource for mathematics

Positive semidefinite rank and nested spectrahedra. (English) Zbl 1395.14041
Summary: The set of matrices of given positive semidefinite rank is semialgebraic. In this paper we study the geometry of this set, and in small cases we describe its boundary. For general values of positive semidefinite rank we provide a conjecture for the description of this boundary. Our proof techniques are geometric in nature and rely on nesting spectrahedra between polytopes.

14P10 Semialgebraic sets and related spaces
15B48 Positive matrices and their generalizations; cones of matrices
15A23 Factorization of matrices
Full Text: DOI arXiv
[1] Fawzi, H; Parrilo, PA, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, Math Program, 158, 417-465, (2016) · Zbl 1346.90662
[2] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math Oper Res, 38, 248-264, (2013) · Zbl 1291.90172
[3] Gouveia, J; Parrilo, PA; Thomas, RR, Approximate cone factorizations and lifts of polytopes, Math Program, 151, 613-637, (2015) · Zbl 1319.52010
[4] Cohen, JE; Rothblum, UG, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl, 190, 149-168, (1993) · Zbl 0784.15001
[5] Gillis, N; Glineur, F, On the geometric interpretation of the nonnegative rank, Linear Algebra Appl, 437, 2685-2712, (2012) · Zbl 1258.65039
[6] Kubjas, K; Robeva, E; Sturmfels, B, Fixed points of the EM algorithm and nonnegative rank boundaries, Ann Stat, 43, 422-461, (2015) · Zbl 1308.62035
[7] Vavasis, SA, On the complexity of nonnegative matrix factorization, SIAM J Optim, 20, 1364-1377, (2009) · Zbl 1206.65130
[8] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J Comput Syst Sci, 43, 441-466, (1991) · Zbl 0748.90074
[9] Fiorini, S; Massar, S; Pokutta, S, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, Proceedings of the forty-fourth annual ACM symposium on Theory of computing, (2012), ACM, New York · Zbl 1286.90125
[10] Rothvoß, T, The matching polytope has exponential extension complexity, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, (2014), ACM, New York · Zbl 1315.90038
[11] Lee, JR; Raghavendra, P; Steurer, D, On the power of symmetric LP and SDP relaxations, Proceedings of the 2014 IEEE 29th Conference on Computational Complexity, (2014), IEEE, Washington, DC
[12] Fawzi, H; Saunderson, J; Parrilo, PA, Equivariant semidefinite lifts and sum-of-squares hierarchies, SIAM J Optim, 25, 2212-2243, (2015) · Zbl 1327.90175
[13] Lee, JR; Raghavendra, P; Steurer, D, Lower bounds on the size of semidefinite programming relaxations, Proceedings of the forty-seventh annual ACM symposium on Theory of computing, (2015), ACM, New York · Zbl 1321.90099
[14] Fawzi, H; Gouveia, J; Parrilo, PA, Positive semidefinite rank, Math Program, 153, 133-177, (2015) · Zbl 1327.90174
[15] Gouveia, J; Pashkovich, K; Robinson, RZ, Four dimensional polytopes of minimum positive semidefinite rank, J Comb Theory A, 145, 184-226, (2017) · Zbl 1360.52006
[16] Gouveia, J; Robinson, RZ; Thomas, RR, Polytopes of minimum positive semidefinite rank, Discrete Comput Geom, 50, 679-699, (2013) · Zbl 1279.52023
[17] Gouveia, J; Robinson, RZ; Thomas, RR, Worst-case results for positive semidefinite rank, Math Program, 153, 201-212, (2015) · Zbl 1344.90046
[18] Basu, S; Pollack, R; Roy, M-F, Algorithms in real algebraic geometry, (2005), Springer, Berlin Heidelberg
[19] Bruns, W; Vetter, U, Determinantal rings, (1988), Springer, Berlin Heidelberg
[20] Gallier, J, Notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi diagrams and Delaunay triangulations
[21] Rostalski, P; Sturmfels, B, Dualities in convex algebraic geometry, Rend Mat Appl, 30, 285-327, (2010) · Zbl 1234.90012
[22] Sturmfels, B, Solving systems of polynomial equations, (2002), American Mathematical Society, Providence · Zbl 1101.13040
[23] Kraft, H; Procesi, C, Classical invariant theory, a primer
[24] Sinn, R; Sturmfels, B, Generic spectrahedral shadows, SIAM J Optim, 25, 1209-1220, (2015) · Zbl 1346.14132
[25] Vandaele, A; Gillis, N; Glineur, F, Heuristics for exact nonnegative matrix factorization, J Global Optim, 65, 369-400, (2016) · Zbl 1341.65057
[26] Klauck, H; Lee, T; Theis, DO, Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl seminar 15082), Dagstuhl Rep, 5, 2192-5283, (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.