×

zbMATH — the first resource for mathematics

Worst-case results for positive semidefinite rank. (English) Zbl 1344.90046
The positive semidefinite rank is an extension of the notion of the nonnegative rank of a matrix. The nonnegative rank of a matrix is the smallest possible integer \(k\) such that each entry \((i,j)\) of the matrix can be written as the inner product of two vectors \(a_i\) and \(b_j\) in the cone of nonnegative vectors of size \(k\). The positive semidefinite rank is the smallest possible integer \(k\) such that each entry \((i,j)\) of the matrix can be written as the inner product of two matrices \(A_i\) and \(B_j\) in the cone of positive semidefinite matrices of size \(k\). These ranks can be interpreted as a measure of complexity of a polytope, in the sense that they encode the size of a sparse representation of a polytope through a factorization of its matrix description. The paper under review reports on state-of-the-art results on lower bounds on the positive semidefinite rank, both for generic polytopes and for specific polytopes.

MSC:
90C22 Semidefinite programming
52B11 \(n\)-dimensional polytopes
15A23 Factorization of matrices
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bochnak, J., Coste, M., Roy, M.: Real Algebraic Geometry. Springer, Berlin (1998) · Zbl 0912.14023
[2] Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: Proceedings of FOCS (2012) · Zbl 1343.68308
[3] Briët, J., Dadush, D., Pokutta, S.: On the existence of \(0/1\) polytopes with high semidefinite extension complexity. Math. Program. Ser. B (to appear) · Zbl 1395.90241
[4] Cohen, JE; Rothblum, UG, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Its Appl., 190, 149-168, (1993) · Zbl 0784.15001
[5] Fawzi, H., Parrilo, P.A.: Lower bounds to nonnegative rank via nonnegative nuclear norms. Math. Progam. Ser. B (to appear) · Zbl 1327.90202
[6] Fiorini, S; Kaibel, V; Pashkovich, K; Theis, DO, Combinatorial bounds on nonnegative rank and extended formulations, Discret. Math., 313, 67-83, (2013) · Zbl 1259.90111
[7] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of STOC (2012) · Zbl 1286.90125
[8] Fiorini, S; Rothvoss, T; Tiwary, H, Extended formulations for polygons, Discret. Comput. Geom., 48, 658-668, (2012) · Zbl 1290.68122
[9] Gillis, N; Glineur, F, On the geometric interpretation of the nonnegative rank, Linear Algebra Its Appl., 437, 2685-2712, (2012) · Zbl 1258.65039
[10] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2013) · Zbl 1291.90172
[11] Gouveia, J; Robinson, RZ; Thomas, RR, Polytopes of minimum positive semidefinite rank, Discret. Comput. Geom., 50, 679-699, (2013) · Zbl 1279.52023
[12] Hungerford,T.: Algebra. Holt, Rinehart, and Winston, New York (1974)
[13] Lee T., Theis, D.O.: Support based lower bounds for the positive semidefinite rank of a nonnegative matrix. Linear Algebra Appl. (to appear) · Zbl 1290.68122
[14] Moitra, A.: An almost optimal algorithm for computing nonnegative rank. In: Proceedings of the SODA (2013) · Zbl 1334.68102
[15] Pashkovich, K.: Extended Formulations for Combinatorial Polytopes. PhD thesis, Magdeburg Universität (2012) · Zbl 1259.90111
[16] Renegar, J, On the computational complexity and geometry of the first-order theory of the reals, J. Symb. Comp., 13, 255-352, (1992) · Zbl 0763.68042
[17] Shitov, Y, An upper bound for nonnegative rank, J. Comb. Theory Ser. A, 122, 126-132, (2014) · Zbl 1316.52020
[18] Vavasis, S, On the complexity of nonnegative matrix factorization, SIAM J. Optim., 20, 1364-1377, (2009) · Zbl 1206.65130
[19] Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming. Kluwer, Boston (2000) · Zbl 0962.90001
[20] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
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.