{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T10:05:45Z","timestamp":1775729145120,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T00:00:00Z","timestamp":1437004800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T00:00:00Z","timestamp":1437004800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-11-1-0305"],"award-info":[{"award-number":["FA9550-11-1-0305"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundacao para a Ciencia e a Tecnologia, through European program COMPETE\/FEDER"},{"name":"US NSF Graduate Research Fellowship","award":["DGE-1256082"],"award-info":[{"award-number":["DGE-1256082"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1115293"],"award-info":[{"award-number":["DMS-1115293"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10107-015-0922-1","type":"journal-article","created":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T09:15:08Z","timestamp":1436951708000},"page":"133-177","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":71,"title":["Positive semidefinite rank"],"prefix":"10.1007","volume":"153","author":[{"given":"Hamza","family":"Fawzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jo\u00e3o","family":"Gouveia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo A.","family":"Parrilo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard Z.","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rekha R.","family":"Thomas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,16]]},"reference":[{"key":"922_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013162 (2012)","DOI":"10.1145\/2213977.2213994"},{"issue":"1","key":"922_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s004540010074","volume":"25","author":"A Barvinok","year":"2001","unstructured":"Barvinok, A.: A remark on the rank of positive semidefinite matrices subject to affine constraints. Discret. Comput. Geom. 25(1), 23\u201331 (2001)","journal-title":"Discret. Comput. Geom."},{"key":"922_CR3","unstructured":"Barvinok, A.: Approximations of Convex Bodies by Polytopes and by Projections of Spectrahedra. arXiv preprint. \n                    arXiv:1204.0471\n                    \n                   (2012)"},{"key":"922_CR4","doi-asserted-by":"publisher","DOI":"10.1142\/5273","volume-title":"Completely Positive Matrices","author":"A Berman","year":"2003","unstructured":"Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Pub Co Inc, Singapore (2003)"},{"key":"922_CR5","doi-asserted-by":"crossref","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R. (eds.): Semidefinite Optimization and Convex Algebraic Geometry, vol 13 of MOS-SIAM Series on Optimization. SIAM (2012)","DOI":"10.1137\/1.9781611972290"},{"issue":"4","key":"922_CR6","doi-asserted-by":"publisher","first-page":"1500","DOI":"10.1137\/110825455","volume":"32","author":"C Bocci","year":"2011","unstructured":"Bocci, C., Carlini, E., Rapallo, F.: Perturbation of matrices and nonnegative rank with a view toward statistical models. SIAM J. Matrix Anal. Appl. 32(4), 1500\u20131512 (2011)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"922_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"SP Boyd","year":"2004","unstructured":"Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"922_CR8","doi-asserted-by":"crossref","unstructured":"Bri\u00ebt, 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\u2013228. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40450-4_19"},{"issue":"21","key":"922_CR9","doi-asserted-by":"publisher","first-page":"210503","DOI":"10.1103\/PhysRevLett.100.210503","volume":"100","author":"N Brunner","year":"2008","unstructured":"Brunner, N., Pironio, S., Acin, A., Gisin, N., M\u00e9thot, A.A., Scarani, V.: Testing the dimension of Hilbert spaces. Phys. Rev. Lett. 100(21), 210503 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"922_CR10","unstructured":"Burgdorf, S., Laurent, M., Piovesan, T.: On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. arXiv preprint \n                    arXiv:1502.02842\n                    \n                   (2015)"},{"key":"922_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0024-3795(93)90224-C","volume":"190","author":"JE Cohen","year":"1993","unstructured":"Cohen, J.E., Rothblum, U.G.: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra Appl. 190, 149\u2013168 (1993)","journal-title":"Linear Algebra Appl."},{"key":"922_CR12","doi-asserted-by":"publisher","unstructured":"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\u201320 (2010). doi:\n                    10.1007\/978-3-642-12598-0_1","DOI":"10.1007\/978-3-642-12598-0_1"},{"key":"922_CR13","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.A.: Sparse Sum-of-Squares Certificates on Finite Abelian Groups. arXiv preprint. \n                    arXiv:1503.01207\n                    \n                   (2015)","DOI":"10.1109\/CDC.2015.7403148"},{"key":"922_CR14","doi-asserted-by":"crossref","unstructured":"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 \u201912, pp 95\u2013106. ACM (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"1","key":"922_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.disc.2012.09.015","volume":"313","author":"S Fiorini","year":"2013","unstructured":"Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. Discrete Math. 313(1), 67\u201383 (2013)","journal-title":"Discrete Math."},{"key":"922_CR16","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1016\/j.laa.2014.07.017","volume":"459","author":"PE Frenkel","year":"2014","unstructured":"Frenkel, P.E., Weiner, M.: On vector configurations that can berealized in the cone of positive matrices. Linear Alg. Appl. 459, 465\u2013474 (2014). doi:\n                    10.1016\/j.laa.2014.07.017","journal-title":"Linear Alg. Appl."},{"key":"922_CR17","volume-title":"Computers and Intractability: A guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"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)"},{"issue":"11","key":"922_CR18","doi-asserted-by":"publisher","first-page":"2685","DOI":"10.1016\/j.laa.2012.06.038","volume":"437","author":"N Gillis","year":"2012","unstructured":"Gillis, N., Glineur, F.: On the geometric interpretation of the nonnegative rank. Linear Algebra Appl. 437(11), 2685\u20132712 (2012)","journal-title":"Linear Algebra Appl."},{"key":"922_CR19","doi-asserted-by":"publisher","unstructured":"Goemans, M. X.: Smallest compact formulation for the permutahedron. Math. Prog. (2014). pp. 1\u20137 doi:\n                    10.1007\/s10107-014-0757-1","DOI":"10.1007\/s10107-014-0757-1"},{"issue":"2","key":"922_CR20","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1287\/moor.1120.0575","volume":"38","author":"J Gouveia","year":"2013","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Lifts of convex sets and cone factorizations. Math. Operat. Res. 38(2), 248\u2013264 (2013)","journal-title":"Math. Operat. Res."},{"issue":"3","key":"922_CR21","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s00454-013-9533-x","volume":"50","author":"J Gouveia","year":"2013","unstructured":"Gouveia, J., Robinson, R.Z., Thomas, R.R.: Polytopes of minimum positive semidefinite rank. Discrete Comput. Geom. 50(3), 679\u2013699 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"922_CR22","unstructured":"Gouveia, J., Fawzi, H., Robinson, R.Z.: Rational and Real Positive Semidefinite Rank can be Different. arXiv preprint. \n                    arXiv:1404.4864\n                    \n                   (2014)"},{"key":"922_CR23","doi-asserted-by":"publisher","unstructured":"Gouveia, J., Robinson, R.Z., Thomas, R.R.:Worst-case results for positive semidefinite rank. Math. Program. 1\u201312 (2015). doi:\n                    10.1007\/s10107-015-0867-4","DOI":"10.1007\/s10107-015-0867-4"},{"key":"922_CR24","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.ipl.2012.02.009","volume":"112","author":"P Hrube\u0161","year":"2012","unstructured":"Hrube\u0161, P.: On the nonnegative rank of distance matrices. Inf. Process. Lett. 112, 457\u2013461 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"922_CR25","doi-asserted-by":"publisher","first-page":"5171","DOI":"10.1109\/TIT.2013.2258372","volume":"59","author":"R Jain","year":"2013","unstructured":"Jain, R., Shi, Y., Wei, Z., Zhang, S.: Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Trans. Inf. Theory 59(8), 5171\u20135178 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"922_CR26","volume-title":"Principal Component Analysis","author":"I Jolliffe","year":"2002","unstructured":"Jolliffe, I.: Principal Component Analysis, 2nd edn. Springer, New York (2002)","edition":"2"},{"issue":"2","key":"922_CR27","first-page":"152","volume":"1","author":"RE Kalman","year":"1963","unstructured":"Kalman, R.E.: Mathematical description of linear dynamical systems. J. Soc. Ind. Appl. Math. Ser. A. Control 1(2), 152\u2013192 (1963)","journal-title":"Control"},{"key":"922_CR28","unstructured":"Laurent, M., Piovesan, T.: Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone. arXiv preprint. \n                    arXiv:1312.6643\n                    \n                   (2013)"},{"issue":"6755","key":"922_CR29","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1038\/44565","volume":"401","author":"DD Lee","year":"1999","unstructured":"Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401(6755), 788\u2013791 (1999)","journal-title":"Nature"},{"key":"922_CR30","unstructured":"Lee, T., Theis, D.O.: Support-Based Lower Bounds for the Positive Semidefinite Rank of a Nonnegative Matrix. arXiv preprint. \n                    arXiv:1203.3961\n                    \n                   (2012)"},{"key":"922_CR31","doi-asserted-by":"crossref","unstructured":"Lee, J. R., Raghavendra, P., Steurer, D.: Lower Bounds on the Size of Semidefinite Programming Relaxations. arXiv preprint. \n                    arXiv:1411.6317\n                    \n                   (2014)","DOI":"10.1145\/2746539.2746599"},{"key":"922_CR32","unstructured":"Lee, T., Wei, Z., de Wolf, R.: Some Upper and Lower Bounds on Psd-rank arXiv preprint. \n                    arXiv:1407.4308\n                    \n                   (2014)"},{"issue":"3","key":"922_CR33","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1002\/rsa.20232","volume":"34","author":"N Linial","year":"2009","unstructured":"Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms 34(3), 368\u2013394 (2009)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"922_CR34","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00493-007-2160-5","volume":"27","author":"N Linial","year":"2007","unstructured":"Linial, N., Mendelson, S., Schechtman, G., Shraibman, A.: Complexity measures of sign matrices. Combinatorica 27(4), 439\u2013463 (2007)","journal-title":"Combinatorica"},{"issue":"7\u20138","key":"922_CR35","first-page":"432","volume":"23","author":"L-H Lim","year":"2009","unstructured":"Lim, L.-H., Comon, P.: Nonnegative approximations of nonnegative tensors. J. Chemometrics 23(7\u20138), 432\u2013441 (2009)","journal-title":"Nonnegative approximations of nonnegative tensors. J. Chemometrics"},{"key":"922_CR36","doi-asserted-by":"publisher","unstructured":"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\u20131464 (2013). doi:\n                    10.1137\/1.9781611973105.104","DOI":"10.1137\/1.9781611973105.104"},{"issue":"2039","key":"922_CR37","doi-asserted-by":"publisher","first-page":"2821","DOI":"10.1098\/rspa.2003.1150","volume":"459","author":"D Mond","year":"2003","unstructured":"Mond, D., Smith, J., van Straten, D.: Stochastic factorizations, sandwiched simplices and the topology of the space of explanations. R. Soc. Proc. Math. Phys. Eng. Sci. 459(2039), 2821\u20132845 (2003)","journal-title":"R. Soc. Proc. Math. Phys. Eng. Sci."},{"issue":"1","key":"922_CR38","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1109\/TAC.1981.1102568","volume":"26","author":"B Moore","year":"1981","unstructured":"Moore, B.: Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans. Autom. Control 26(1), 17\u201332 (1981)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"2","key":"922_CR39","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s10107-008-0253-6","volume":"122","author":"J Nie","year":"2010","unstructured":"Nie, J., Ranestad, K., Sturmfels, B.: The algebraic degree of semidefinite programming. Math. Program. 122(2), 379\u2013405 (2010)","journal-title":"Math. Program."},{"key":"922_CR40","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. PhD thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg (2012)"},{"issue":"2","key":"922_CR41","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.23.2.339","volume":"23","author":"G Pataki","year":"1998","unstructured":"Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Operat. Res. 23(2), 339\u2013358 (1998)","journal-title":"Math. Operat. Res."},{"issue":"3","key":"922_CR42","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/S003614450444614X","volume":"49","author":"I P\u00f3lik","year":"2007","unstructured":"P\u00f3lik, I., Terlaky, T.: A survey of the S-lemma. SIAM review. 49(3), 371\u2013418 (2007)","journal-title":"SIAM review."},{"issue":"3","key":"922_CR43","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J Renegar","year":"1992","unstructured":"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(3), 255\u2013299 (1992)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"922_CR44","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s10208-004-0136-z","volume":"6","author":"J Renegar","year":"2006","unstructured":"Renegar, J.: Hyperbolic programs, and their derivative relaxations. Found. Comput. Math. 6(1), 59\u201379 (2006)","journal-title":"Found. Comput. Math."},{"key":"922_CR45","unstructured":"Scheiderer, C.: Semidefinite representation for convex hulls of real algebraic curves. arXiv preprint. \n                    arXiv:1208.3865\n                    \n                   (2012)"},{"key":"922_CR46","doi-asserted-by":"crossref","unstructured":"Stark, C. J., Harrow, A. W.: Compressibility of positive semidefinite factorizations and quantum models. arXiv preprint \n                    arXiv:1412.7437\n                    \n                   (2014)","DOI":"10.1109\/ISIT.2015.7282962"},{"issue":"1","key":"922_CR47","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49\u201395 (1996)","journal-title":"SIAM Rev."},{"issue":"3","key":"922_CR48","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/070709967","volume":"20","author":"SA Vavasis","year":"2009","unstructured":"Vavasis, S.A.: On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20(3), 1364\u20131377 (2009)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"922_CR49","doi-asserted-by":"publisher","first-page":"062112","DOI":"10.1103\/PhysRevA.78.062112","volume":"78","author":"S Wehner","year":"2008","unstructured":"Wehner, S., Christandl, M., Doherty, A.C.: Lower bound on the dimension of a quantum system given measured data. Phys. Rev. A 78(6), 062112 (2008)","journal-title":"Phys. Rev. A"},{"issue":"3","key":"922_CR50","first-page":"441","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. 43(3), 441\u2013446 (1991)","journal-title":"J. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0922-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0922-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0922-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0922-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:15:14Z","timestamp":1589645714000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0922-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,16]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["922"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0922-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,16]]},"assertion":[{"value":"1 April 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}