{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T09:03:35Z","timestamp":1761987815116,"version":"build-2065373602"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,7,7]],"date-time":"2015-07-07T00:00:00Z","timestamp":1436227200000},"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":["J Optim Theory Appl"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s10957-015-0777-x","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T15:52:34Z","timestamp":1436197954000},"page":"653-675","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation"],"prefix":"10.1007","volume":"167","author":[{"given":"Brendan P. W.","family":"Ames","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,7]]},"reference":[{"issue":"3","key":"777_CR1","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"777_CR2","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 534\u2013543. ACM (2002)","DOI":"10.1145\/509907.509985"},{"issue":"4","key":"777_CR3","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. SIAM J. Comput. 36(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"777_CR4","unstructured":"Alon, N., Arora, S., Manokaran, R., Moshkovitz, D., Weinstein, O.: Inapproximability of densest $$\\kappa $$ \u03ba -subgraph from average-case hardness (2011)"},{"issue":"1","key":"777_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-011-0460-4","volume":"129","author":"B Ames","year":"2011","unstructured":"Ames, B., Vavasis, S.: Nuclear norm minimization for the planted clique and biclique problems. Math. Program. 129(1), 1\u201321 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"777_CR6","doi-asserted-by":"crossref","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":"3","key":"777_CR7","doi-asserted-by":"crossref","first-page":"11","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 (2011)","journal-title":"J. ACM (JACM)"},{"issue":"7","key":"777_CR8","doi-asserted-by":"crossref","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"},{"key":"777_CR9","unstructured":"Oymak, S., Hassibi, B.: Finding dense clusters via \u201clow rank + sparse\u201d decomposition. Arxiv preprint arXiv:1104.5186 (2011)"},{"issue":"1","key":"777_CR10","first-page":"2213","volume":"15","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Jalali, A., Sanghavi, S., Xu, H.: Clustering partially observed graphs via convex optimization. J. Mach. Learn. Res. 15(1), 2213\u20132238 (2014)","journal-title":"J. Mach. Learn. Res."},{"key":"777_CR11","unstructured":"Chen, Y., Sanghavi, S., Xu, H.: Clustering sparse graphs. In: Advances in neural information processing systems, pp. 2204\u20132212 (2012)"},{"key":"777_CR12","unstructured":"Lawler, E.L.: Combinatorial optimization: networks and matroids. Courier Corporation (1976)"},{"issue":"4","key":"777_CR13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume":"40","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. Complex. Comput. Comput. 40(4), 85\u2013103 (1972)","journal-title":"Complex. Comput. Comput."},{"issue":"4","key":"777_CR14","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"777_CR15","doi-asserted-by":"crossref","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."},{"key":"777_CR16","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse fourier representations via sampling. In: STOC \u201902: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 152\u2013161. ACM, New York, NY, USA (2002). doi: 10.1145\/509907.509933","DOI":"10.1145\/509907.509933"},{"issue":"4","key":"777_CR17","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D Donoho","year":"2006","unstructured":"Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"777_CR18","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2) (2006)","DOI":"10.1109\/TIT.2005.862083"},{"key":"777_CR19","unstructured":"Ames, B.: Robust convex relaxation for the planted clique and densest $$k$$ k -subgraph problems: additional proofs (2013). Available from http:\/\/bpames.people.ua.edu\/uploads\/3\/9\/0\/0\/39000767\/dks_appendices.pdf"},{"issue":"2","key":"777_CR20","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L Ku\u010dera","year":"1995","unstructured":"Ku\u010dera, L.: Expected complexity of graph partitioning problems. Discret. Appl. Math. 57(2), 193\u2013212 (1995)","journal-title":"Discret. Appl. Math."},{"key":"777_CR21","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. In: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 594\u2013598. Society for Industrial and Applied Mathematics (1998)"},{"issue":"2","key":"777_CR22","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A","volume":"16","author":"U Feige","year":"2000","unstructured":"Feige, U., Krauthgamer, R.: Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms 16(2), 195\u2013208 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"777_CR23","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, pp. 529\u2013537. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959929"},{"key":"777_CR24","first-page":"189","volume":"01","author":"U Feige","year":"2010","unstructured":"Feige, U., Ron, D.: Finding hidden cliques in linear time. DMTCS Proc. 01, 189\u2013204 (2010)","journal-title":"DMTCS Proc."},{"issue":"01","key":"777_CR25","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1017\/S096354831300045X","volume":"23","author":"Y Dekel","year":"2014","unstructured":"Dekel, Y., Gurel-Gurevich, O., Peres, Y.: Finding hidden cliques in linear time with high probability. Comb. Probab. Comput. 23(01), 29\u201349 (2014)","journal-title":"Comb. Probab. Comput."},{"key":"777_CR26","unstructured":"Deshpande, Y., Montanari, A.: Finding hidden cliques of size $$\\sqrt{N\/e}$$ N \/ e in nearly linear time. Found. Comput. Math. pp. 1\u201360 (2013)"},{"issue":"3","key":"777_CR27","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1023\/A:1008374125234","volume":"20","author":"A Juels","year":"2000","unstructured":"Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Crypt. 20(3), 269\u2013280 (2000)","journal-title":"Des. Codes Crypt."},{"key":"777_CR28","doi-asserted-by":"crossref","unstructured":"Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., Xie, N.: Testing k-wise and almost k-wise independence. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 496\u2013505. ACM (2007)","DOI":"10.1145\/1250790.1250863"},{"issue":"1","key":"777_CR29","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1137\/090766991","volume":"40","author":"E Hazan","year":"2011","unstructured":"Hazan, E., Krauthgamer, R.: How hard is it to approximate the best nash equilibrium? SIAM J. Comput. 40(1), 79\u201391 (2011)","journal-title":"SIAM J. Comput."},{"key":"777_CR30","unstructured":"Berthet, Q., Rigollet, P.: Computational lower bounds for sparse PCA. arXiv preprint arXiv:1304.0828 (2013)"},{"issue":"4","key":"777_CR31","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M Jerrum","year":"1992","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. Random Struct. Algorithms 3(4), 347\u2013359 (1992)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"777_CR32","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/S009753970240118X","volume":"32","author":"U Feige","year":"2003","unstructured":"Feige, U., Krauthgamer, R.: The probable value of the lov\u00e1sz-schrijver relaxations for maximum independent set. SIAM J. Comput. 32(2), 345\u2013370 (2003)","journal-title":"SIAM J. Comput."},{"key":"777_CR33","doi-asserted-by":"crossref","unstructured":"Nadakuditi, R.: On hard limits of eigen-analysis based planted clique detection. In: Statistical Signal Processing Workshop (SSP), 2012 IEEE, pp. 129\u2013132. IEEE (2012)","DOI":"10.1109\/SSP.2012.6319639"},{"issue":"3","key":"777_CR34","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discret. Appl. Math. 131(3), 651\u2013654 (2003)","journal-title":"Discret. Appl. Math."},{"key":"777_CR35","unstructured":"Goerdt, A., Lanka, A.: An approximation hardness result for bipartite clique. In: Electronic Colloquium on Computational Complexity, Report, 48 (2004)"},{"key":"777_CR36","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press, Cambridge (2004)"},{"key":"777_CR37","volume-title":"Matrix computations","author":"G Golub","year":"1996","unstructured":"Golub, G., Van Loan, C.: Matrix computations. Johns Hopkins University Press, Baltimore (1996)"},{"key":"777_CR38","unstructured":"Lugosi, G.: Concentration-measure inequalities (2009). Available from http:\/\/www.econ.upf.edu\/~lugosi\/anu.pdf"},{"key":"777_CR39","doi-asserted-by":"crossref","unstructured":"Tropp, J.: User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics pp. 1\u201346 (2011)","DOI":"10.21236\/ADA555817"},{"issue":"1","key":"777_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends Mach. Learn."},{"key":"777_CR41","unstructured":"Goldfarb, D., Ma, S., Scheinberg, K.: Fast alternating linearization methods for minimizing the sum of two convex functions. Math. Program. pp. 1\u201334 (2010)"},{"key":"777_CR42","unstructured":"Hong, M., Luo, Z.: On the linear convergence of the alternating direction method of multipliers. arXiv preprint arXiv:1208.3922 (2012)"},{"key":"777_CR43","unstructured":"Rohe, K., Qin, T., Fan, H.: The highest dimensional stochastic blockmodel with a regularized estimator. arXiv preprint arXiv:1206.2380 (2012)"},{"issue":"1\u20132","key":"777_CR44","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s10107-013-0733-1","volume":"143","author":"B Ames","year":"2014","unstructured":"Ames, B., Vavasis, S.: Convex optimization for the planted k-disjoint-clique problem. Math. Program. 143(1\u20132), 299\u2013337 (2014)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"777_CR45","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s10107-013-0729-x","volume":"147","author":"B Ames","year":"2014","unstructured":"Ames, B.: Guaranteed clustering and biclustering via semidefinite programming. Math. Program. 147(1\u20132), 429\u2013465 (2014)","journal-title":"Math. Program."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-015-0777-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10957-015-0777-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-015-0777-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T21:21:47Z","timestamp":1566940907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10957-015-0777-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,7]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["777"],"URL":"https:\/\/doi.org\/10.1007\/s10957-015-0777-x","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2015,7,7]]}}}