{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T19:21:42Z","timestamp":1751743302933,"version":"3.37.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s10208-023-09637-4","type":"journal-article","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T16:02:18Z","timestamp":1702051338000},"page":"223-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational Complexity of Decomposing a Symmetric Matrix as a Sum of Positive Semidefinite and Diagonal Matrices"],"prefix":"10.1007","volume":"25","author":[{"given":"Levent","family":"Tun\u00e7el","sequence":"first","affiliation":[]},{"given":"Stephen A.","family":"Vavasis","sequence":"additional","affiliation":[]},{"given":"Jingye","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,8]]},"reference":[{"key":"9637_CR1","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1073\/pnas.30.4.90","volume":"30","author":"AA Albert","year":"1944","unstructured":"A.\u00a0A. Albert. The matrices of factor analysis. Proc. Nat. Acad. Sci. U.S.A., 30:90\u201395, 1944.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"issue":"3","key":"9637_CR2","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00454-011-9391-3","volume":"47","author":"Sal Barone","year":"2012","unstructured":"Sal Barone and Saugata Basu. Refined bounds on the number of connected components of sign conditions on a variety. Discrete & Computational Geometry, 47(3):577\u2013597, 2012.","journal-title":"Discrete & Computational Geometry"},{"key":"9637_CR3","doi-asserted-by":"crossref","unstructured":"Saugata Basu, Richard Pollack, and Marie-Fran\u00e7oise Roy. Algorithms in real algebraic geometry, volume\u00a010 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, second edition, 2006.","DOI":"10.1007\/3-540-33099-2"},{"key":"9637_CR4","unstructured":"Dimitris Bertsimas, Martin\u00a0S. Copenhaver, and Rahul Mazumder. Certifiably optimal low rank factor analysis. The Journal of Machine Learning Research, 18(1):907\u2013959, 2017."},{"issue":"6","key":"9637_CR5","doi-asserted-by":"publisher","first-page":"3321","DOI":"10.1287\/opre.2021.2182","volume":"70","author":"Dimitris Bertsimas","year":"2022","unstructured":"Dimitris Bertsimas, Ryan Cory-Wright, and Jean Pauphilet. Mixed-projection conic optimization: a new paradigm for modeling rank constraints. Oper. Res., 70(6):3321\u20133344, 2022.","journal-title":"Oper. Res."},{"key":"9637_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"L.\u00a0Blum, M.\u00a0Shub, and S.\u00a0Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21:1\u201346, 1989.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"9637_CR7","unstructured":"Christopher\u00a0W. Brown and James\u00a0H. Davenport. The complexity of quantifier elimination and cylindrical algebraic decomposition. In Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201907, page 54-60, New York, NY, USA, 2007. Association for Computing Machinery."},{"key":"9637_CR8","doi-asserted-by":"crossref","unstructured":"John Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC \u201988, page 460-467, New York, NY, USA, 1988. Association for Computing Machinery.","DOI":"10.1145\/62212.62257"},{"key":"9637_CR9","doi-asserted-by":"crossref","unstructured":"George\u00a0E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In H.\u00a0Brakhage, editor, Automata Theory and Formal Languages, pages 134\u2013183, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.","DOI":"10.1007\/3-540-07407-4_17"},{"key":"9637_CR10","doi-asserted-by":"crossref","unstructured":"Giacomo Della\u00a0Riccia and Alexander Shapiro. Minimum rank and minimum trace of covariance matrices. Psychometrika, 47(4):443\u2013448, 1982.","DOI":"10.1007\/BF02293708"},{"key":"9637_CR11","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00440-006-0033-2","volume":"138","author":"Mathias Drton","year":"2007","unstructured":"Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Algebraic factor analysis: tetrads, pentads and beyond. Probability Theory and Related Fields, 138:463\u2013493, 2007.","journal-title":"Probability Theory and Related Fields"},{"key":"9637_CR12","doi-asserted-by":"crossref","unstructured":"M.\u00a0Fazel, H.\u00a0Hindi, and S.P. Boyd. A rank minimization heuristic with application to minimum order system approximation. In Proceedings of the 2001 American Control Conference. (Cat. No.01CH37148), volume\u00a06, pages 4734\u20134739 vol.6, 2001.","DOI":"10.1109\/ACC.2001.945730"},{"key":"9637_CR13","doi-asserted-by":"crossref","unstructured":"Bin Gao and P.-A. Absil. A Riemannian rank-adaptive method for low-rank matrix completion. Computational Optimization and Applications, 81:1\u201324, 2022.","DOI":"10.1007\/s10589-021-00328-w"},{"key":"9637_CR14","unstructured":"Gene\u00a0H. Golub and Charles\u00a0F. Van\u00a0Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition, 2013."},{"key":"9637_CR15","doi-asserted-by":"crossref","unstructured":"Monique Laurent. Cuts, matrix completions and graph rigidity. Math. Programming, 79(1-3, Ser. B):255\u2013283, 1997.","DOI":"10.1007\/BF02614320"},{"key":"9637_CR16","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. Graphs and geometry, volume\u00a065 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2019."},{"key":"9637_CR17","doi-asserted-by":"crossref","unstructured":"Nikolai\u00a0E Mn\u00ebv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Topology and geometry-Rohlin seminar, pages 527\u2013543. Springer, 1988.","DOI":"10.1007\/BFb0082792"},{"issue":"2","key":"9637_CR18","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01211741","volume":"6","author":"A Nemirovskii","year":"1993","unstructured":"A.\u00a0Nemirovskii. Several NP-hard problems arising in robust stability analysis. Math. Control Signals Systems, 6(2):99\u2013105, 1993.","journal-title":"Math. Control Signals Systems"},{"issue":"3","key":"9637_CR19","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/BF01261326","volume":"16","author":"Ren\u00e9 Peeters","year":"1996","unstructured":"Ren\u00e9 Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417\u2013431, 1996.","journal-title":"Combinatorica"},{"issue":"1","key":"9637_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01213466","volume":"6","author":"Svatopluk Poljak","year":"1993","unstructured":"Svatopluk Poljak and Ji\u0159\u00ed Rohn. Checking robust nonsingularity is NP-hard. Math. Control Signals Systems, 6(1):1\u20139, 1993.","journal-title":"Math. Control Signals Systems"},{"key":"9637_CR21","unstructured":"C\u00a0Ramya. Recent progress on matrix rigidity\u2013a survey. arXiv preprint arXiv:2009.09460, 2020."},{"issue":"3","key":"9637_CR22","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"Benjamin Recht","year":"2010","unstructured":"Benjamin Recht, Maryam Fazel, and Pablo\u00a0A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471\u2013501, 2010.","journal-title":"SIAM Review"},{"issue":"2","key":"9637_CR23","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s12532-013-0053-8","volume":"5","author":"Benjamin Recht","year":"2013","unstructured":"Benjamin Recht and Christopher R\u00e9. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 5(2):201\u2013226, 2013.","journal-title":"Mathematical Programming Computation"},{"issue":"4","key":"9637_CR24","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1006\/jcom.2000.0563","volume":"16","author":"F Rouillier","year":"2000","unstructured":"F.\u00a0Rouillier, M.-F. Roy, and M.\u00a0Safey El Din. Finding at least one point in each connected component of a real algebraic set defined by a single equation. Journal of Complexity, 16(4):716\u2013750, 2000.","journal-title":"Journal of Complexity"},{"issue":"4","key":"9637_CR25","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1137\/120872516","volume":"33","author":"J Saunderson","year":"2012","unstructured":"J.\u00a0Saunderson, V.\u00a0Chandrasekaran, P.\u00a0A. Parrilo, and A.\u00a0S. Willsky. Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting. SIAM Journal on Matrix Analysis and Applications, 33(4):1395-1416, 2012.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9637_CR26","unstructured":"J.\u00a0B. Saxe. Two papers on graph embedding problems. Technical Report CMU-CS80-102, Department of Computer Science, Carnegie-Mellon University, 1980."},{"key":"9637_CR27","doi-asserted-by":"crossref","unstructured":"Alexander Shapiro. Statistical inference of semidefinite programming. Math. Program., 174(1-2, Ser. B):77\u201397, 2019.","DOI":"10.1007\/s10107-018-1250-z"},{"key":"9637_CR28","unstructured":"Yaroslav Shitov. How hard is the tensor rank? arXiv preprint arXiv:1611.01559, 2016."},{"issue":"2","key":"9637_CR29","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1002\/cjs.11532","volume":"48","author":"Wu Yilei","year":"2020","unstructured":"Yilei Wu, Yingli Qin, and Mu\u00a0Zhu. High-dimensional covariance matrix estimation using a low-rank and diagonal decomposition. Canadian Journal of Statistics, 48(2):308\u2013337, 2020.","journal-title":"Canadian Journal of Statistics"},{"key":"9637_CR30","unstructured":"Fuzhen Zhang, editor. The Schur complement and its applications, volume\u00a04. Springer Science & Business Media, 2006."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-023-09637-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-023-09637-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-023-09637-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T18:53:06Z","timestamp":1739472786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-023-09637-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["9637"],"URL":"https:\/\/doi.org\/10.1007\/s10208-023-09637-4","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"type":"print","value":"1615-3375"},{"type":"electronic","value":"1615-3383"}],"subject":[],"published":{"date-parts":[[2023,12,8]]},"assertion":[{"value":"14 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}