{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:36Z","timestamp":1787340216073,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE-2019-T3-1-010"],"award-info":[{"award-number":["MOE-2019-T3-1-010"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Semidefinite programming (SDP) problems are challenging to solve because of their high dimensionality. However, solving sparse SDP problems with small tree width is known to be relatively easier because (1) they can be decomposed into smaller multiblock SDP problems through chordal conversion and\u00a0(2) they have low-rank optimal solutions. In this paper, we study more general SDP problems whose coefficient matrices have sparse plus low-rank (SPLR) structure. We develop a unified framework to convert such problems into sparse SDP problems with bounded tree width. Based on this, we derive rank bounds for SDP problems with SPLR structure, which are tight in the worst case.<\/jats:p>","DOI":"10.1137\/24m1694112","type":"journal-article","created":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T08:12:07Z","timestamp":1770192727000},"page":"90-119","source":"Crossref","is-referenced-by-count":0,"title":["Exploring Chordal Sparsity in Semidefinite Programming with Sparse plus Low-Rank Data Matrices"],"prefix":"10.1137","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6619-0474","authenticated-orcid":true,"given":"Tianyun","family":"Tang","sequence":"first","affiliation":[{"name":"Department of Mathematics, National University of Singapore, Singapore 119076."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7204-8933","authenticated-orcid":true,"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Institute of Operations Research and Analytics, National University of Singapore, Singapore 119076."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,2,4]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(88)90240-6"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0016-2"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574037"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/1356052.1356057"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"ref6","first-page":"2765","volume-title":"in Advances in Neural Information Processing Systems 29 (NIPS 2016)","author":"Boumal N."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0223-z"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-021-01705-4"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(92)90304-S"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"R. Diestel, Graph Theory, 3rd ed. Graduate Texts in Mathematics, Springer-Verlag, Berlin,\u00a02005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.23081"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2562062"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90207-6"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009898604624"},{"key":"ref17","volume-title":"Minimum Rank Positive Semidefinite Matrix Completion with Chordal Sparsity Pattern","author":"Jiang X.","year":"2017"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-021-00339-7"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"S. Kang, X. Xu, J. Sarva, L. Liang, and H. Yang, Fast and Certifiable Trajectory Optimization, preprint, arXiv:2406.05846, 2024.","DOI":"10.1007\/978-3-032-09967-9_3"},{"key":"ref20","first-page":"1","volume":"25","author":"Lee C.-p.","year":"2024","journal-title":"J. Mach. Learn. Res."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"ref22","first-page":"1","volume":"21","author":"Madani R.","year":"2014","journal-title":"Constraints"},{"key":"ref23","unstructured":"R. D. Monteiro, A. Sujanani, and D. Cifuentes, A Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming Based on a Hybrid Convex-Nonconvex Approach, preprint, arXiv:2401.12490, 2024."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0351-9"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.2.339"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(98)00097-X"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805766"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/23M1561464"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1345"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01952-6"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1561\/2400000006"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-005-4939-z"},{"key":"ref35","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","volume":"27","author":"Wolkowicz H.","year":"2012"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0082-6"},{"key":"ref37","unstructured":"R. Y. Zhang, Parameterized Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth, preprint, arXiv:2306.15288, 2023."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01516-y"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01366-3"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1694112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:18Z","timestamp":1787336718000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1694112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,4]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/24M1694112"],"URL":"https:\/\/doi.org\/10.1137\/24m1694112","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,4]]}}}