{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T05:58:12Z","timestamp":1765951092677,"version":"3.48.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T00:00:00Z","timestamp":1763510400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T00:00:00Z","timestamp":1763510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005722","name":"Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005722","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2025,12]]},"abstract":"Abstract<\/jats:title>\n \n In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has the planted Maximum Clique Problem (MCP) as a special case. The maximum clique problem is NP-hard. A Quasi-clique or\n \n \n $$\\gamma $$<\/jats:tex-math>\n \n \u03b3<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -clique is a dense graph with the edge density of at least\n \n \n $$\\gamma $$<\/jats:tex-math>\n \n \u03b3<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$\\gamma \\in (0, 1]$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The maximum quasi-clique problem seeks to find such a subgraph with the largest cardinality in a given graph. Our method of choice is the low-rank plus sparse matrix splitting technique. We present a theoretical basis for when our convex relaxation problem recovers the planted maximum quasi-clique. We have derived a new bound on the norm of the dual matrix that certifies the recovery using\n \n \n $$l_{\\infty , 2}$$<\/jats:tex-math>\n \n \n l<\/mml:mi>\n \n \u221e<\/mml:mi>\n ,<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n norm. We have showed that when certain conditions are met, our convex formulation recovers the planted quasi-clique exactly. The numerical experiments we have performed corroborate our theoretical findings.\n <\/jats:p>","DOI":"10.1007\/s10898-025-01562-w","type":"journal-article","created":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T04:15:48Z","timestamp":1763525748000},"page":"1121-1144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Rank-sparsity decomposition for planted quasi clique recovery"],"prefix":"10.1007","volume":"93","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6900-2771","authenticated-orcid":false,"given":"Sakirudeen A.","family":"Abdulsalaam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Montaz","family":"Ali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,19]]},"reference":[{"key":"1562_CR1","unstructured":"Abdulsalaam, S.A.: Convex Optimization for Rank-Sparsity Decomposition, With Application to the Planted Quasi-Clique Problem. University of the Witwatersrand, Johannesburg (South Africa), (2020)"},{"key":"1562_CR2","first-page":"119","volume":"50","author":"J Abello","year":"1999","unstructured":"Abello, J., Pardalos, P.M., Resende, M.G.C.: On maximum clique problems in very large graphs. DIMACS Ser. 50, 119\u2013130 (1999)","journal-title":"DIMACS Ser."},{"key":"1562_CR3","doi-asserted-by":"crossref","unstructured":"Abello, J., Resende, M.G.C., Sudarsky, S.: Massive quasi-clique detection. In Latin American Symposium on Theoretical Informatics, pages 598\u2013612. Springer, (2002)","DOI":"10.1007\/3-540-45995-2_51"},{"issue":"1","key":"1562_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1080\/0022250X.1973.9989826","volume":"3","author":"RD Alba","year":"1973","unstructured":"Alba, R.D.: A graph-theoretic definition of a sociometric clique. J. Math. Soc. 3(1), 113\u2013126 (1973)","journal-title":"J. Math. Soc."},{"key":"1562_CR5","unstructured":"Ames, B.: Convex relaxation for the planted clique, biclique, and clustering problems. (2011)"},{"issue":"1","key":"1562_CR6","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10107-011-0459-x","volume":"129","author":"BPW Ames","year":"2011","unstructured":"Ames, B.P.W., Vavasis, S.A.: Nuclear norm minimization for the planted clique and biclique problems. Math. Program. 129(1), 69\u201389 (2011)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1562_CR7","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10107-013-0733-1","volume":"143","author":"BPW Ames","year":"2014","unstructured":"Ames, B.P.W., Vavasis, S.A.: Convex optimization for the planted k-disjoint-clique problem. Math. Program. 143(1\u20132), 299\u2013337 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"1562_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.laa.2006.02.019","volume":"417","author":"OM Baksalary","year":"2006","unstructured":"Baksalary, O.M., Kik, P.: On commutativity of projectors. Linear Algebra Appl. 417(1), 31\u201341 (2006)","journal-title":"Linear Algebra Appl."},{"key":"1562_CR9","unstructured":"Balabhaskar, B.: Graph theoretic generalization of clique: Optimization and extensions. PhD thesis, PhD thesis, Texas A & M University, (2007)"},{"issue":"1","key":"1562_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum $$k$$-plex problem. Op. Res. 59(1), 133\u2013142 (2011)","journal-title":"Op. Res."},{"key":"1562_CR11","doi-asserted-by":"crossref","unstructured":"Beck, C., D\u2019Andrea, R.: Computational study and comparisons of lft reducibility methods. In Proceedings of the 1998 American Control Conference. ACC (IEEE Cat. No. 98CH36207), 2, 1013\u20131017. IEEE, (1998)","DOI":"10.1109\/ACC.1998.703562"},{"key":"1562_CR12","doi-asserted-by":"crossref","unstructured":"Brunato, M., Hoos, H.H., Battiti, R.: On effectively finding maximal quasi-cliques in graphs. In International Conference on Learning and Intelligent Optimization, pages 41\u201355. Springer, (2007)","DOI":"10.1007\/978-3-540-92695-5_4"},{"issue":"6","key":"1562_CR13","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","volume":"98","author":"EJ Candes","year":"2010","unstructured":"Candes, E.J., Plan, Y.: Matrix completion with noise. Proc. IEEE 98(6), 925\u2013936 (2010)","journal-title":"Proc. IEEE"},{"issue":"6","key":"1562_CR14","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e9s","year":"2009","unstructured":"Cand\u00e9s, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717\u2013772 (2009)","journal-title":"Found. Comput. Math."},{"issue":"5","key":"1562_CR15","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"EJ Cand\u00e8s","year":"2010","unstructured":"Cand\u00e8s, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053\u20132080 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"1562_CR16","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1970392.1970395","volume":"58","author":"EJ Cand\u00e8s","year":"2011","unstructured":"Cand\u00e8s, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM (JACM) 58(3), 11:1-11:37 (2011)","journal-title":"J. ACM (JACM)"},{"key":"1562_CR17","unstructured":"Cape, J., Tang, M., Priebe, C.E.: The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. arXiv preprint arXiv:1705.10735, (2017)"},{"issue":"2","key":"1562_CR18","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/090761793","volume":"21","author":"V Chandrasekaran","year":"2011","unstructured":"Chandrasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21(2), 572\u2013596 (2011)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"1562_CR19","doi-asserted-by":"publisher","first-page":"2909","DOI":"10.1109\/TIT.2015.2415195","volume":"61","author":"Y Chen","year":"2015","unstructured":"Chen, Y.: Incoherence-optimal matrix completion. IEEE Trans. Inf. Theory 61(5), 2909\u20132923 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"7","key":"1562_CR20","doi-asserted-by":"publisher","first-page":"4324","DOI":"10.1109\/TIT.2013.2249572","volume":"59","author":"Y Chen","year":"2013","unstructured":"Chen, Y., Jalali, A., Sanghavi, S., Caramanis, C.: Low-rank matrix recovery from errors and erasures. IEEE Trans. Inf. Theory 59(7), 4324\u20134337 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"83","key":"1562_CR21","first-page":"1","volume":"17","author":"S Diamond","year":"2016","unstructured":"Diamond, S., Boyd, S.: CVXPY: a Python-embedded modeling language for convex optimization. J. Mach. Learn. Res. 17(83), 1\u20135 (2016)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"1562_CR22","doi-asserted-by":"publisher","first-page":"1548","DOI":"10.1109\/TIT.2011.2104999","volume":"57","author":"D Gross","year":"2011","unstructured":"Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57(3), 1548\u20131566 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1562_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00365-012-9176-9","volume":"37","author":"X Li","year":"2013","unstructured":"Li, X.: Compressed sensing and matrix completion with constant proportion of corruptions. Constr. Approx. 37(1), 73\u201399 (2013)","journal-title":"Constr. Approx."},{"issue":"2","key":"1562_CR24","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02289199","volume":"15","author":"RD Luce","year":"1950","unstructured":"Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2), 169\u2013190 (1950)","journal-title":"Psychometrika"},{"issue":"2","key":"1562_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1109\/9.554402","volume":"42","author":"M Mesbahi","year":"1997","unstructured":"Mesbahi, M., Papavassilopoulos, G.P.: On the rank minimization problem over a positive semidefinite linear matrix inequality. IEEE Trans. Autom. Control 42(2), 239\u2013243 (1997)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"2","key":"1562_CR26","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"RJ Mokken","year":"1979","unstructured":"Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13(2), 161\u2013173 (1979)","journal-title":"Qual. Quant."},{"issue":"4","key":"1562_CR27","doi-asserted-by":"publisher","first-page":"2017","DOI":"10.1109\/TIT.2013.2240435","volume":"59","author":"NH Nguyen","year":"2013","unstructured":"Nguyen, N.H., Tran, T.D.: Exact recoverability from dense corrupted observations via $$\\ell _{1}$$-minimization. IEEE Trans. Inf. Theory 59(4), 2017\u20132035 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1562_CR28","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"PRJ \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P.R.J.: A fast algorithm for the maximum clique problem. Discret. Appl. Math. 120(1), 197\u2013207 (2002)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1562_CR29","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.dam.2012.07.019","volume":"161","author":"J Pattillo","year":"2013","unstructured":"Pattillo, J., Veremyev, A., Butenko, S., Boginski, V.: On the maximum quasi-clique problem. Discret. Appl. Math. 161(1), 244\u2013257 (2013)","journal-title":"Discret. Appl. Math."},{"key":"1562_CR30","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.aim.2017.11.001","volume":"324","author":"E Rebrova","year":"2018","unstructured":"Rebrova, E., Vershynin, R.: Norms of random matrices: local and global problems. Adv. Math. 324, 40\u201383 (2018)","journal-title":"Adv. Math."},{"issue":"Dec","key":"1562_CR31","first-page":"3413","volume":"12","author":"B Recht","year":"2011","unstructured":"Recht, B.: A simpler approach to matrix completion. J. Machine Learn. Res. 12(Dec), 3413\u20133430 (2011)","journal-title":"J. Machine Learn. Res."},{"key":"1562_CR32","doi-asserted-by":"crossref","unstructured":"Recht, B., Xu, W., Hassibi, B.: Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization. In Decision and Control, 2008. CDC 2008. 47th IEEE Conference on, 3065\u20133070. IEEE, (2008)","DOI":"10.1109\/CDC.2008.4739332"},{"issue":"3","key":"1562_CR33","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471\u2013501 (2010)","journal-title":"SIAM Rev."},{"issue":"1","key":"1562_CR34","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"SB Seidman","year":"1978","unstructured":"Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept*. J. Math. Soc. 6(1), 139\u2013154 (1978)","journal-title":"J. Math. Soc."},{"key":"1562_CR35","unstructured":"Tao, T.: Topics in random matrix theory"},{"issue":"1","key":"1562_CR36","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10589-015-9804-y","volume":"64","author":"A Veremyev","year":"2016","unstructured":"Veremyev, A., Prokopyev, O.A., Butenko, S., Pasiliao, E.L.: Exact mip-based approaches for finding maximum quasi-cliques and dense subgraphs. Comput. Optim. Appl. 64(1), 177\u2013214 (2016)","journal-title":"Comput. Optim. Appl."},{"key":"1562_CR37","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, (2010)"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01562-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-025-01562-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01562-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T05:53:10Z","timestamp":1765950790000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-025-01562-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,19]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1562"],"URL":"https:\/\/doi.org\/10.1007\/s10898-025-01562-w","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2025,11,19]]},"assertion":[{"value":"6 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}