{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T08:05:45Z","timestamp":1772525145131,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,8,19]],"date-time":"2015-08-19T00:00:00Z","timestamp":1439942400000},"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":[[2016,7]]},"DOI":"10.1007\/s10107-015-0937-7","type":"journal-article","created":{"date-parts":[[2015,8,18]],"date-time":"2015-08-18T08:14:59Z","timestamp":1439885699000},"page":"417-465","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank"],"prefix":"10.1007","volume":"158","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":[[2015,8,19]]},"reference":[{"key":"937_CR1","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.laa.2013.10.046","volume":"473","author":"ES Allman","year":"2013","unstructured":"Allman, E.S., Rhodes, J.A., Sturmfels, B., Zwiernik, P.: Tensors of nonnegative rank two. Linear Algebra Appl. 473, 37\u201353 (2013)","journal-title":"Linear Algebra Appl."},{"key":"937_CR2","doi-asserted-by":"crossref","unstructured":"Bachoc, C., Gijswijt, D.C., Schrijver, A., Vallentin, F.: Invariant semidefinite programs. In: Handbook on Semidefinite, Conic and Polynomial Optimization. Springer, pp. 219\u2013269 (2012)","DOI":"10.1007\/978-1-4614-0769-0_9"},{"key":"937_CR3","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, Singapore (2003)"},{"key":"937_CR4","doi-asserted-by":"crossref","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.): Semidefinite optimization and convex algebraic geometry. MOS-SIAM Series on Optimization, vol. 13. SIAM (2013)","DOI":"10.1145\/2465506.2466575"},{"issue":"3\u20134","key":"937_CR5","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1007\/s00208-014-1150-3","volume":"362","author":"G Blekherman","year":"2015","unstructured":"Blekherman, G., Teitler, Z.: On maximum, typical and generic ranks. Math. Ann. 362(3\u20134), 1021\u20131031 (2015)","journal-title":"Math. Ann."},{"issue":"4","key":"937_CR6","doi-asserted-by":"crossref","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."},{"issue":"2","key":"937_CR7","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","volume":"83","author":"J Borwein","year":"1981","unstructured":"Borwein, J., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495\u2013530 (1981)","journal-title":"J. Math. Anal. Appl."},{"key":"937_CR8","doi-asserted-by":"crossref","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 480\u2013489 (2012)","DOI":"10.1109\/FOCS.2012.10"},{"key":"937_CR9","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: Common information and unique disjointness. In: IEEE 54th Annual Symposium on Foundations of Computer Science (2013)","DOI":"10.1109\/FOCS.2013.79"},{"key":"937_CR10","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing. ACM, pp. 161\u2013170 (2013)","DOI":"10.1145\/2488608.2488629"},{"issue":"6","key":"937_CR11","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1007\/s10208-012-9135-7","volume":"12","author":"V Chandrasekaran","year":"2012","unstructured":"Chandrasekaran, V., Recht, B., Parrilo, P.A., Willsky, A.S.: The convex geometry of linear inverse problems. Found. Comput. Math. 12(6), 805\u2013849 (2012)","journal-title":"Found. Comput. Math."},{"issue":"3","key":"937_CR12","doi-asserted-by":"crossref","first-page":"1254","DOI":"10.1137\/060661569","volume":"30","author":"P Comon","year":"2008","unstructured":"Comon, P., Golub, G., Lim, L.H., Mourrain, B.: Symmetric tensors and symmetric tensor rank. SIAM J. Matrix Anal. Appl. 30(3), 1254\u20131279 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"937_CR13","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2012","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (2012)"},{"key":"937_CR14","unstructured":"Dickinson, P.J.C.: The Copositive Cone, the Completely Positive Cone and Their Generalisations. Ph.D. thesis, University of Groningen (2013)"},{"key":"937_CR15","doi-asserted-by":"publisher","unstructured":"Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57, 403\u2013415 (2014). doi: 10.1007\/s10589-013-9594-z","DOI":"10.1007\/s10589-013-9594-z"},{"issue":"4","key":"937_CR16","doi-asserted-by":"publisher","first-page":"2502","DOI":"10.1137\/100814251","volume":"23","author":"XV Doan","year":"2013","unstructured":"Doan, X.V., 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). doi: 10.1137\/100814251","journal-title":"SIAM J. Optim."},{"key":"937_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-7643-8905-5","volume-title":"Lectures on Algebraic Statistics","author":"M Drton","year":"2009","unstructured":"Drton, M., Sturmfels, B., Sullivant, S.: Lectures on Algebraic Statistics. Springer, New York (2009)"},{"issue":"2\u20133","key":"937_CR18","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10107-006-0026-z","volume":"109","author":"I Dukanovic","year":"2007","unstructured":"Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Program. 109(2\u20133), 345\u2013365 (2007)","journal-title":"Math. Program."},{"key":"937_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0922-1","author":"H Fawzi","year":"2015","unstructured":"Fawzi, H., Gouveia, J., Parrilo, P.A., Robinson, R.Z., Thomas, R.R.: Positive semidefinite rank. Math. Program. Ser. B (2015). doi: 10.1007\/s10107-015-0922-1","journal-title":"Math. Program. Ser. B"},{"key":"937_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0837-2","author":"H Fawzi","year":"2014","unstructured":"Fawzi, H., Parrilo, P.A.: Lower bounds on nonnegative rank via nonnegative nuclear norms. Math. Program. Ser. B (2014). doi: 10.1007\/s10107-014-0837-2","journal-title":"Math. Program. Ser. B"},{"issue":"1","key":"937_CR21","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. Discrete Math. 313(1), 67\u201383 (2013)","journal-title":"Discrete Math."},{"issue":"1","key":"937_CR22","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"},{"issue":"11","key":"937_CR23","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."},{"issue":"2","key":"937_CR24","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."},{"key":"937_CR25","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1090\/S0002-9939-1977-0472853-X","volume":"64","author":"R Grone","year":"1977","unstructured":"Grone, R.: Decomposable tensors as a quadratic variety. Proc. Am. Math. Soc. 64, 227\u2013230 (1977)","journal-title":"Proc. Am. Math. Soc."},{"key":"937_CR26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R Grone","year":"1984","unstructured":"Grone, R., Johnson, C.R., S\u00e1, E.M., Wolkowicz, H.: Positive definite completions of partial hermitian matrices. Linear Algebra Appl. 58, 109\u2013124 (1984)","journal-title":"Linear Algebra Appl."},{"key":"937_CR27","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Kushilevitz, E., Nisan, N.: Fractional covers and communication complexity. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference. IEEE, pp. 262\u2013274 (1992)","DOI":"10.1109\/SCT.1992.215401"},{"key":"937_CR28","first-page":"201","volume":"107","author":"H K\u00f6nig","year":"1999","unstructured":"K\u00f6nig, H.: Cubature formulas on spheres. Math. Res. 107, 201\u2013212 (1999)","journal-title":"Math. Res."},{"issue":"1","key":"937_CR29","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1214\/14-AOS1282","volume":"43","author":"K Kubjas","year":"2015","unstructured":"Kubjas, K., Robeva, E., Sturmfels, B., et al.: Fixed points EM algorithm and nonnegative rank boundaries. Ann. Stat. 43(1), 422\u2013461 (2015)","journal-title":"Ann. Stat."},{"key":"937_CR30","doi-asserted-by":"crossref","unstructured":"Landsberg, J.M.: Tensors: Geometry and Applications, vol. 128. AMS Bookstore (2012)","DOI":"10.1090\/gsm\/128"},{"issue":"4","key":"937_CR31","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower bounds in communication complexity. Found. Trendsin Theor. Comput. Sci. 3(4), 263\u2013399 (2009)","journal-title":"Found. Trendsin Theor. Comput. Sci."},{"issue":"7\u20138","key":"937_CR32","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1002\/cem.1244","volume":"23","author":"LH Lim","year":"2009","unstructured":"Lim, L.H., Comon, P.: Nonnegative approximations of nonnegative tensors. J. Chemom. 23(7\u20138), 432\u2013441 (2009)","journal-title":"J. Chemom."},{"key":"937_CR33","unstructured":"L\u00f6fberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004). http:\/\/users.isy.liu.se\/johanl\/yalmip"},{"issue":"4","key":"937_CR34","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"937_CR35","first-page":"235","volume-title":"Paths, Flows, and VLSI-Layout","author":"L Lov\u00e1sz","year":"1990","unstructured":"Lov\u00e1sz, L.: Communication complexity: a survey. In: Korte, B., Promel, H., Graham, R.L. (eds.) Paths, Flows, and VLSI-Layout, pp. 235\u2013265. Springer-Verlag New York, Secaucus (1990)"},{"issue":"5","key":"937_CR36","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"issue":"3","key":"937_CR37","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s101070100246","volume":"102","author":"P Meurdesoif","year":"2005","unstructured":"Meurdesoif, P.: Strengthening the Lov\u00e1sz bound for graph coloring. Math. Program. 102(3), 577\u2013588 (2005)","journal-title":"Math. Program."},{"issue":"2039","key":"937_CR38","first-page":"2821","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. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 459(2039), 2821\u20132845 (2003)","journal-title":"Eng. Sci."},{"issue":"1","key":"937_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.22.1.1","volume":"22","author":"Y Nesterov","year":"1997","unstructured":"Nesterov, Y., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1\u201342 (1997)","journal-title":"Math. Oper. Res."},{"key":"937_CR40","unstructured":"Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent sdps via approximations of the psd cone. arXiv preprint arXiv:1408.4685 (2014)"},{"key":"937_CR41","doi-asserted-by":"crossref","unstructured":"Reznick, B.: Sums of even powers of real linear forms. Mem. Am. Math. Soc. 96(463), viii+155 (1992)","DOI":"10.1090\/memo\/0463"},{"key":"937_CR42","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1997","unstructured":"Rockafellar, R.T.: Convex Analysis, vol. 28. Princeton University Press, Princeton (1997)"},{"key":"937_CR43","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. ACM, pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"},{"issue":"3","key":"937_CR44","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/s003730050068","volume":"15","author":"ER Scheinerman","year":"1999","unstructured":"Scheinerman, E.R., Trenk, A.N.: On the fractional intersection number of a graph. Graphs Comb. 15(3), 341\u2013351 (1999)","journal-title":"Graphs Comb."},{"issue":"2","key":"937_CR45","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1137\/120885759","volume":"34","author":"N Shaked-Monderer","year":"2013","unstructured":"Shaked-Monderer, N., Bomze, I.M., Jarre, F., Schachinger, W.: On the cp-rank and minimal cp factorizations of a completely positive matrix. SIAM J. Matrix Anal. Appl. 34(2), 355\u2013368 (2013)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"937_CR46","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354\u2013356 (1969)","journal-title":"Numer. Math."},{"key":"937_CR47","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: A note on the $$\\vartheta $$ \u03d1 number of Lov\u00e1sz and the generalized Delsarte bound. In: IEEE 35th Annual Symposium on Foundations of Computer Science, pp. 36\u201339 (1994)","DOI":"10.1109\/SFCS.1994.365707"},{"issue":"1","key":"937_CR48","doi-asserted-by":"crossref","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":"937_CR49","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":"4","key":"937_CR50","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0024-3795(71)90009-7","volume":"4","author":"S Winograd","year":"1971","unstructured":"Winograd, S.: On multiplication of 2 $$\\times $$ \u00d7 2 matrices. Linear Algebra Appl. 4(4), 381\u2013388 (1971)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"937_CR51","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1109\/TIT.1975.1055346","volume":"21","author":"A Wyner","year":"1975","unstructured":"Wyner, A.: The common information of two dependent random variables. IEEE Trans. Inf. Theory 21(2), 163\u2013179 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"937_CR52","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."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0937-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0937-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0937-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T01:19:31Z","timestamp":1748567971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0937-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,19]]},"references-count":52,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["937"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0937-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,19]]}}}