{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:42Z","timestamp":1740120222289,"version":"3.37.3"},"reference-count":54,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","funder":[{"DOI":"10.13039\/501100012166","name":"National key R & D program of China","doi-asserted-by":"crossref","award":["2021YFA1000900"],"award-info":[{"award-number":["2021YFA1000900"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>Robust optimization problems have attracted considerable attention in recent years. In this paper, we focus on two fundamental robust optimization problems: SVM with outliers and [Formula: see text]-center clustering with outliers. The key obstacle is that the outliers can be located arbitrarily in the space (e.g., by an attacker), and thus they are actually quite challenging combinatorial optimization problems. Their computational complexities can be very high especially in high dimensional spaces. The Johnson\u2013Lindenstrauss [Formula: see text]JL\u200a[Formula: see text] Transform is a popular random projection method for dimension reduction. Though the JL transform has been widely studied in the past decades, its effectiveness for dealing with high-dimensional optimizations with outliers has never been investigated before (to the best of our knowledge). Based on some novel insights from the geometry, we prove that the complexities of these two problems can be significantly reduced through the JL transform. Moreover, we prove that the solution in the dimensionality-reduced space can be efficiently recovered in the original [Formula: see text] space while the quality is still preserved. To study its performance in practice, we compare different JL transform methods with several other well known dimension reduction methods in our experiments.<\/jats:p>","DOI":"10.1142\/s0218195922500078","type":"journal-article","created":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T10:54:52Z","timestamp":1671447292000},"page":"201-225","source":"Crossref","is-referenced-by-count":0,"title":["Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers"],"prefix":"10.1142","volume":"32","author":[{"given":"Jiawei","family":"Huang","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruizhe","family":"Qin","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fan","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1307-6077","authenticated-orcid":false,"given":"Hu","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,12,19]]},"reference":[{"volume-title":"ECML PKDD 2012 Tutorial","year":"2012","author":"Durrant R. J.","key":"S0218195922500078BIB001"},{"key":"S0218195922500078BIB002","first-page":"143","volume-title":"FOCS","author":"Sarlos T.","year":"2006"},{"key":"S0218195922500078BIB004","first-page":"410","volume-title":"FOCS","author":"Blocki J.","year":"2012"},{"issue":"189","key":"S0218195922500078BIB005","first-page":"1","volume":"26","author":"Johnson W. B.","year":"1984","journal-title":"Contemporary Math."},{"issue":"1","key":"S0218195922500078BIB006","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"Dasgupta S.","year":"2003","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"S0218195922500078BIB007","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"Achlioptas D.","year":"2003","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"S0218195922500078BIB008","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"Ailon N.","year":"2009","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S0218195922500078BIB009","first-page":"4:1","volume":"61","author":"Kane D. M.","year":"2014","journal-title":"J. ACM"},{"key":"S0218195922500078BIB010","first-page":"341","volume-title":"STOC","author":"Dasgupta A.","year":"2010"},{"issue":"1","key":"S0218195922500078BIB011","first-page":"2859","volume":"16","author":"Cunningham J. P.","year":"2015","journal-title":"The J. Mach. Learn. Res."},{"issue":"5","key":"S0218195922500078BIB012","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/sam.11161","volume":"5","author":"Zimek A.","year":"2012","journal-title":"Statistical Analysis and Data Mining: The ASA Data Science Journal"},{"key":"S0218195922500078BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2018.07.023"},{"volume-title":"Introduction to Data Mining","year":"2006","author":"Tan P.-N.","key":"S0218195922500078BIB014"},{"issue":"2","key":"S0218195922500078BIB016","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1109\/TIT.2014.2375327","volume":"61","author":"Boutsidis C.","year":"2014","journal-title":"IEEE Trans. Inform. Th."},{"key":"S0218195922500078BIB017","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/2746539.2746569","volume-title":"Proc. Forty-Seventh Annual ACM Symposium on Theory of Computing","author":"Cohen M. B.","year":"2015"},{"key":"S0218195922500078BIB018","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1145\/3313276.3316350","volume-title":"Proc. 51st Annual ACM SIGACT Symposium on Theory of Computing","author":"Makarychev K.","year":"2019"},{"issue":"2","key":"S0218195922500078BIB019","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s10994-006-6265-7","volume":"63","author":"Arriaga R. I.","year":"2006","journal-title":"Machine Learning"},{"issue":"1","key":"S0218195922500078BIB020","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10994-006-7550-1","volume":"65","author":"Balcan M.-F.","year":"2006","journal-title":"Machine Learning"},{"key":"S0218195922500078BIB021","first-page":"793","volume-title":"Advances in Neural Information Processing Systems","author":"Kumar K.","year":"2008"},{"volume-title":"Proc. 29th Int. Conf. Machine Learning, ICML","year":"2012","author":"Shi Q.","key":"S0218195922500078BIB022"},{"issue":"4","key":"S0218195922500078BIB023","doi-asserted-by":"crossref","first-page":"22:1","DOI":"10.1145\/2641760","volume":"8","author":"Paul S.","year":"2014","journal-title":"TKDD"},{"key":"S0218195922500078BIB024","first-page":"135","volume-title":"Conference on Learning Theory","author":"Zhang L.","year":"2013"},{"issue":"3","key":"S0218195922500078BIB025","volume":"2","author":"Chang C.-C.","year":"2011","journal-title":"ACM TIST"},{"key":"S0218195922500078BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/BF00994018"},{"key":"S0218195922500078BIB027","first-page":"185","volume-title":"Advances in Kernel Methods \u2014 Support Vector Learning","author":"Platt J.","year":"1999"},{"volume-title":"NIPS","year":"1999","author":"Crisp D. J.","key":"S0218195922500078BIB028"},{"key":"S0218195922500078BIB029","doi-asserted-by":"publisher","DOI":"10.1162\/089976600300015565"},{"key":"S0218195922500078BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2016.03.028"},{"key":"S0218195922500078BIB031","first-page":"582","volume-title":"Advances in Neural Information Processing Systems","author":"Sch\u00f6lkopf B.","year":"1999"},{"key":"S0218195922500078BIB033","first-page":"2532","volume-title":"Advances in Neural Information Processing Systems","author":"Yang M.","year":"2010"},{"key":"S0218195922500078BIB034","first-page":"1098","volume-title":"ICML, JMLR Workshop and Conference Proceedings","author":"Suzumura S.","year":"2014"},{"key":"S0218195922500078BIB035","first-page":"2561","volume-title":"AAAI","author":"Ding H.","year":"2015"},{"key":"S0218195922500078BIB036","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.patcog.2016.09.045","volume":"63","author":"Xu G.","year":"2017","journal-title":"Pattern Recognition"},{"key":"S0218195922500078BIB037","first-page":"1177","volume-title":"Advances in Neural Information Processing Systems","author":"Rahimi A.","year":"2008"},{"key":"S0218195922500078BIB038","first-page":"735","volume-title":"Artificial Intelligence and Statistics","author":"Paul S.","year":"2015"},{"key":"S0218195922500078BIB039","first-page":"642","volume-title":"SODA","author":"Charikar M.","year":"2001"},{"key":"S0218195922500078BIB040","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-540-85363-3_14","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"McCutchen R. M.","year":"2008"},{"key":"S0218195922500078BIB041","first-page":"67:1","volume-title":"ICALP","author":"Chakrabarty D.","year":"2016"},{"key":"S0218195922500078BIB042","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1145\/509907.509947","volume-title":"STOC","author":"B\u0103doiu M.","year":"2002"},{"key":"S0218195922500078BIB043","first-page":"40:1","volume-title":"ESA","author":"Ding H.","year":"2019"},{"key":"S0218195922500078BIB044","first-page":"1063","volume-title":"Advances in Neural Information Processing Systems","author":"Malkomes G.","year":"2015"},{"issue":"7","key":"S0218195922500078BIB045","doi-asserted-by":"crossref","first-page":"766","DOI":"10.14778\/3317315.3317319","volume":"12","author":"Ceccarello M.","year":"2019","journal-title":"Proc. VLDB Endow."},{"key":"S0218195922500078BIB046","doi-asserted-by":"publisher","DOI":"10.1002\/0471725382"},{"issue":"1","key":"S0218195922500078BIB047","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/0304007","volume":"4","author":"Gilbert E. G.","year":"1966","journal-title":"SIAM J. Control"},{"key":"S0218195922500078BIB048","first-page":"33","volume-title":"SoCG","author":"G\u00e4rtner B.","year":"2009"},{"issue":"4","key":"S0218195922500078BIB049","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/1824777.1824783","volume":"6","author":"Clarkson K. L.","year":"2010","journal-title":"ACM Transactions on Algorithms"},{"key":"S0218195922500078BIB050","first-page":"801","volume-title":"SODA","author":"B\u0103doiu M.","year":"2003"},{"key":"S0218195922500078BIB051","first-page":"381","volume-title":"Proceedings of the 23rd ACM Symposium on Computational Geometry","author":"Agarwal P. K.","year":"2007"},{"key":"S0218195922500078BIB052","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1145\/2582112.2582126","volume-title":"SOCG","author":"Sheehy D. R.","year":"2014"},{"key":"S0218195922500078BIB053","first-page":"545","volume-title":"Advances in Neural Information Processing Systems","author":"Guyon I.","year":"2005"},{"issue":"11","key":"S0218195922500078BIB054","doi-asserted-by":"crossref","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Bengio Y.","year":"1998","journal-title":"Proc. IEEE"},{"key":"S0218195922500078BIB055","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"S0218195922500078BIB057","first-page":"1871","volume":"9","author":"Fan R.-E.","year":"2008","journal-title":"J. Machine Learning Research"},{"volume-title":"Learning Multiple Layers of Features from Tiny Images","year":"2009","author":"Krizhevsky A.","key":"S0218195922500078BIB058"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195922500078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,18]],"date-time":"2023-03-18T10:03:49Z","timestamp":1679133829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218195922500078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":54,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1142\/S0218195922500078"],"URL":"https:\/\/doi.org\/10.1142\/s0218195922500078","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2022,9]]}}}