{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T00:08:27Z","timestamp":1774051707864,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,12]],"date-time":"2014-11-12T00:00:00Z","timestamp":1415750400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10107-014-0837-2","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T15:38:42Z","timestamp":1415979522000},"page":"41-66","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Lower bounds on nonnegative rank via nonnegative nuclear norms"],"prefix":"10.1007","volume":"153","author":[{"given":"Hamza","family":"Fawzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo A.","family":"Parrilo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,12]]},"reference":[{"key":"837_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization\u2014provably. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC \u201912, pp. 145\u2013162. ACM (2012)","DOI":"10.1145\/2213977.2213994"},{"key":"837_CR2","doi-asserted-by":"crossref","DOI":"10.1515\/9781400833344","volume-title":"Matrix Mathematics: Theory, Facts, and Formulas","author":"DS Bernstein","year":"2009","unstructured":"Bernstein, D.S.: Matrix Mathematics: Theory, Facts, and Formulas, 2nd edn. Princeton University Press, Princeton (2009)","edition":"2"},{"key":"837_CR3","unstructured":"Braun, G., Jain, R., Lee, T., Pokutta, S.: Information-theoretic approximations of the nonnegative rank. ECCC preprint TR13-158 (2013)"},{"key":"837_CR4","doi-asserted-by":"crossref","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":"837_CR5","doi-asserted-by":"crossref","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":"837_CR6","doi-asserted-by":"crossref","unstructured":"D\u00fcr, M.: Copositive programming \u2013 a survey. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and its Applications in Engineering, pp. 3\u201320. Springer, Berlin (2010). doi: 10.1007\/978-3-642-12598-0_1","DOI":"10.1007\/978-3-642-12598-0_1"},{"issue":"4","key":"837_CR7","doi-asserted-by":"crossref","first-page":"2502","DOI":"10.1137\/100814251","volume":"23","author":"X Doan","year":"2013","unstructured":"Doan, X., Vavasis, S.: Finding approximately rank-one submatrices with the nuclear norm and $$\\ell _1$$ \u2113 1 -norm. SIAM J. Optim. 23(4), 2502\u20132540 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"837_CR8","doi-asserted-by":"crossref","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. Discret. Math. 313(1), 67\u201383 (2013)","journal-title":"Discret. Math."},{"key":"837_CR9","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Parrilo, P.A.: Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank. arXiv:1404.3240 (2014)","DOI":"10.1007\/s10107-015-0937-7"},{"issue":"11","key":"837_CR10","doi-asserted-by":"crossref","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":"837_CR11","first-page":"3349","volume":"13","author":"N Gillis","year":"2012","unstructured":"Gillis, N.: Sparse and unique nonnegative matrix factorization through data preprocessing. J. Mach. Learn. Res. 13, 3349\u20133386 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"837_CR12","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Smallest compact formulation for the permutahedron. Math. Program. 1\u20137 (2014). doi: 10.1007\/s10107-014-0757-1","DOI":"10.1007\/s10107-014-0757-1"},{"issue":"1","key":"837_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1), 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"key":"837_CR14","doi-asserted-by":"crossref","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Approximate cone factorizations and lifts of polytopes. arXiv:1308.2162 (2013)","DOI":"10.1007\/s10107-014-0848-z"},{"issue":"2","key":"837_CR15","doi-asserted-by":"crossref","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. Oper. Res. 38(2), 248\u2013264 (2013)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"837_CR16","doi-asserted-by":"crossref","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. Discret. Comput. Geom. 50(3), 679\u2013699 (2013)","journal-title":"Discret. Comput. Geom."},{"key":"837_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511569166","volume-title":"Summing and Nuclear Norms in Banach Space Theory","author":"GJO Jameson","year":"1987","unstructured":"Jameson, G.J.O.: Summing and Nuclear Norms in Banach Space Theory, vol. 8. Cambridge University Press, Cambridge (1987)"},{"issue":"8","key":"837_CR18","doi-asserted-by":"crossref","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":"837_CR19","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (2006)"},{"issue":"4","key":"837_CR20","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E Klerk","year":"2002","unstructured":"Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"key":"837_CR21","doi-asserted-by":"crossref","unstructured":"L\u00f6fberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004)","DOI":"10.1109\/CACSD.2004.1393890"},{"issue":"5","key":"837_CR22","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1109\/TAC.2009.2017144","volume":"54","author":"J L\u00f6fberg","year":"2009","unstructured":"L\u00f6fberg, J.: Pre- and post-processing sum-of-squares programs in practice. IEEE Trans. Autom. Control 54(5), 1007\u20131011 (2009)","journal-title":"IEEE Trans. Autom. Control"},{"key":"837_CR23","unstructured":"Lov\u00e1sz, L.: Communication complexity: a survey. In: Korte, B., Promel, H.J., Graham, R.L. (eds.) Paths, Flows, and VLSI-Layout, pp. 235\u2013265. Springer, New York (1990)"},{"key":"837_CR24","doi-asserted-by":"crossref","unstructured":"Lee, T., Shraibman, A.: Lower Bounds in Communication Complexity Found. Trends Theor. Comput. Sci. 3(4), 263\u2013399 (2009)","DOI":"10.1561\/0400000040"},{"key":"837_CR25","unstructured":"Parrilo, P.A.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000)"},{"key":"837_CR26","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: The matching polytope has exponential extension complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 263\u2013272, ACM (2014)","DOI":"10.1145\/2591796.2591834"},{"issue":"3","key":"837_CR27","doi-asserted-by":"crossref","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":"3","key":"837_CR28","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"837_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, S.: Quantum strategic game theory. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 39\u201359, ACM (2012)","DOI":"10.1145\/2090236.2090241"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0837-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0837-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0837-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T10:37:15Z","timestamp":1566038235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0837-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,12]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["837"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0837-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,12]]}}}