zbMATH — the first resource for mathematics

Positive semidefinite rank. (English) Zbl 1327.90174
Summary: Let \(M \in \mathbb R^{p \times q}\) be a nonnegative matrix. The positive semidefinite rank (psd rank) of \(M\) is the smallest integer \(k\) for which there exist positive semidefinite matrices \(A_i\), \(B_j\) of size \(k \times k\) such that \(M_{ij} = \mathrm{trace}(A_i B_j)\). The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects.

90C22 Semidefinite programming
15A23 Factorization of matrices
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv
[1] Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization-provably. In: Proceedings of the 44th Symposium on Theory of Computing (STOC), ACM, pp. 145-162 (2012) · Zbl 1286.15014
[2] Barvinok, A, A remark on the rank of positive semidefinite matrices subject to affine constraints, Discret. Comput. Geom., 25, 23-31, (2001) · Zbl 0969.90096
[3] Barvinok, A.: Approximations of Convex Bodies by Polytopes and by Projections of Spectrahedra. arXiv preprint. arXiv:1204.0471 (2012) · Zbl 1202.94012
[4] Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Pub Co Inc, Singapore (2003) · Zbl 1030.15022
[5] Blekherman, G., Parrilo, P.A., Thomas, R. (eds.): Semidefinite Optimization and Convex Algebraic Geometry, vol 13 of MOS-SIAM Series on Optimization. SIAM (2012) · Zbl 1260.90006
[6] Bocci, C; Carlini, E; Rapallo, F, Perturbation of matrices and nonnegative rank with a view toward statistical models, SIAM J. Matrix Anal. Appl., 32, 1500-1512, (2011) · Zbl 1242.15031
[7] Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[8] Briët, J., Dadush, D., Pokutta, S.: On the existence of 0/1 polytopes with high semidefinite extension complexity. Algorithms. ESA 2013. Lecture Notes in Computer Science. vol 8125, pp. 217-228. Springer, Berlin (2013) · Zbl 1395.90241
[9] Brunner, N; Pironio, S; Acin, A; Gisin, N; Méthot, AA; Scarani, V, Testing the dimension of Hilbert spaces, Phys. Rev. Lett., 100, 210503, (2008) · Zbl 1228.81056
[10] Burgdorf, S., Laurent, M., Piovesan, T.: On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. arXiv preprint arXiv:1502.02842 (2015) · Zbl 1372.81026
[11] Cohen, JE; Rothblum, UG, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl., 190, 149-168, (1993) · Zbl 0784.15001
[12] Dur, M.: Copositive programming-a survey. In: Diehl., M. G., Francois, J., Elias, M. W. (eds.) Recent advances in optimization and its applications in engineering, Springer, Berlin, Heidelberg, pp. 3-20 (2010). doi:10.1007/978-3-642-12598-0_1 · Zbl 0845.65023
[13] Fawzi, H., Saunderson, J., Parrilo, P.A.: Sparse Sum-of-Squares Certificates on Finite Abelian Groups. arXiv preprint. arXiv:1503.01207 (2015) · Zbl 1327.90175
[14] 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 the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ’12, pp 95-106. ACM (2012) · Zbl 1286.90125
[15] Fiorini, S; Kaibel, V; Pashkovich, K; Theis, DO, Combinatorial bounds on nonnegative rank and extended formulations, Discrete Math., 313, 67-83, (2013) · Zbl 1259.90111
[16] Frenkel, PE; Weiner, M, On vector configurations that can berealized in the cone of positive matrices, Linear Alg. Appl., 459, 465-474, (2014) · Zbl 1309.15049
[17] Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the Theory of NP-Completeness. W. H Freeman and Company, San Francisco (1979) · Zbl 0411.68039
[18] Gillis, N; Glineur, F, On the geometric interpretation of the nonnegative rank, Linear Algebra Appl., 437, 2685-2712, (2012) · Zbl 1258.65039
[19] Goemans, M. X.: Smallest compact formulation for the permutahedron. Math. Prog. (2014). pp. 1-7 doi:10.1007/s10107-014-0757-1 · Zbl 1202.94012
[20] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math. Operat. Res., 38, 248-264, (2013) · Zbl 1291.90172
[21] Gouveia, J; Robinson, RZ; Thomas, RR, Polytopes of minimum positive semidefinite rank, Discrete Comput. Geom., 50, 679-699, (2013) · Zbl 1279.52023
[22] Gouveia, J., Fawzi, H., Robinson, R.Z.: Rational and Real Positive Semidefinite Rank can be Different. arXiv preprint. arXiv:1404.4864 (2014)
[23] Gouveia, J., Robinson, R.Z., Thomas, R.R.:Worst-case results for positive semidefinite rank. Math. Program. 1-12 (2015). doi:10.1007/s10107-015-0867-4 · Zbl 1344.90046
[24] Hrubeš, P, On the nonnegative rank of distance matrices, Inf. Process. Lett., 112, 457-461, (2012) · Zbl 1243.15003
[25] Jain, R; Shi, Y; Wei, Z; Zhang, S, Efficient protocols for generating bipartite classical distributions and quantum states, IEEE Trans. Inf. Theory, 59, 5171-5178, (2013) · Zbl 1364.81061
[26] Jolliffe, I.: Principal Component Analysis, 2nd edn. Springer, New York (2002) · Zbl 1011.62064
[27] Kalman, RE, Mathematical description of linear dynamical systems. J. soc. ind. appl. math. ser. A, Control, 1, 152-192, (1963) · Zbl 0145.34301
[28] Laurent, M., Piovesan, T.: Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone. arXiv preprint. arXiv:1312.6643 (2013)
[29] Lee, DD; Seung, HS, Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791, (1999) · Zbl 1369.68285
[30] Lee, T., Theis, D.O.: Support-Based Lower Bounds for the Positive Semidefinite Rank of a Nonnegative Matrix. arXiv preprint. arXiv:1203.3961 (2012)
[31] Lee, J. R., Raghavendra, P., Steurer, D.: Lower Bounds on the Size of Semidefinite Programming Relaxations. arXiv preprint. arXiv:1411.6317 (2014) · Zbl 1321.90099
[32] Lee, T., Wei, Z., de Wolf, R.: Some Upper and Lower Bounds on Psd-rank arXiv preprint. arXiv:1407.4308 (2014)
[33] Linial, N; Shraibman, A, Lower bounds in communication complexity based on factorization norms, Random Struct. Algorithms, 34, 368-394, (2009) · Zbl 1202.94012
[34] Linial, N; Mendelson, S; Schechtman, G; Shraibman, A, Complexity measures of sign matrices, Combinatorica, 27, 439-463, (2007) · Zbl 1164.68006
[35] Lim, L-H; Comon, P, No article title, Nonnegative approximations of nonnegative tensors. J. Chemometrics, 23, 432-441, (2009)
[36] Moitra, A.: An Almost Optimal Algorithm for Computing Nonnegative Rank. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposiumon Discrete Algorithms. chap. 104, pp. 1454-1464 (2013). doi:10.1137/1.9781611973105.104
[37] Mond, D; Smith, J; Straten, D, Stochastic factorizations, sandwiched simplices and the topology of the space of explanations, R. Soc. Proc. Math. Phys. Eng. Sci., 459, 2821-2845, (2003) · Zbl 1051.60076
[38] Moore, B, Principal component analysis in linear systems: controllability, observability, and model reduction, IEEE Trans. Autom. Control, 26, 17-32, (1981) · Zbl 0464.93022
[39] Nie, J; Ranestad, K; Sturmfels, B, The algebraic degree of semidefinite programming, Math. Program., 122, 379-405, (2010) · Zbl 1184.90119
[40] Pashkovich, K.: Extended formulations for combinatorial polytopes. PhD thesis, Otto-von-Guericke-Universität Magdeburg (2012) · Zbl 0969.90096
[41] Pataki, G, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Operat. Res., 23, 339-358, (1998) · Zbl 0977.90051
[42] Pólik, I; Terlaky, T, A survey of the S-lemma, SIAM review., 49, 371-418, (2007) · Zbl 1128.90046
[43] Renegar, J, On the computational complexity and geometry of the first-order theory of the reals. part I: introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals, J. Symb. Comput., 13, 255-299, (1992) · Zbl 0763.68042
[44] Renegar, J, Hyperbolic programs, and their derivative relaxations, Found. Comput. Math., 6, 59-79, (2006) · Zbl 1130.90363
[45] Scheiderer, C.: Semidefinite representation for convex hulls of real algebraic curves. arXiv preprint. arXiv:1208.3865 (2012) · Zbl 1364.81061
[46] Stark, C. J., Harrow, A. W.: Compressibility of positive semidefinite factorizations and quantum models. arXiv preprint arXiv:1412.7437 (2014) · Zbl 1359.94175
[47] Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[48] Vavasis, SA, On the complexity of nonnegative matrix factorization, SIAM J. Optim., 20, 1364-1377, (2009) · Zbl 1206.65130
[49] Wehner, S; Christandl, M; Doherty, AC, Lower bound on the dimension of a quantum system given measured data, Phys. Rev. A, 78, 062112, (2008)
[50] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput., 43, 441-446, (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.