{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T04:58:25Z","timestamp":1781153905957,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T00:00:00Z","timestamp":1777075200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T00:00:00Z","timestamp":1777075200000},"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":["J Optim Theory Appl"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1007\/s10957-026-02997-1","type":"journal-article","created":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:10:27Z","timestamp":1777090227000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Hardness of the $$L_{1}-L_{2}$$ Regularization Problem"],"prefix":"10.1007","volume":"209","author":[{"given":"Yuyuan","family":"Ouyang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6576-5322","authenticated-orcid":false,"given":"Kyle","family":"Yates","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,25]]},"reference":[{"issue":"6","key":"2997_CR1","doi-asserted-by":"publisher","first-page":"3448","DOI":"10.1109\/TIT.2013.2248414","volume":"59","author":"AS Bandeira","year":"2013","unstructured":"Bandeira, A.S., Dobriban, E., Mixon, D.G., Sawin, W.F.: Certifying the restricted isometry property is hard. IEEE Trans. Inf. Theory 59(6), 3448\u20133450 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2997_CR2","unstructured":"Bertrand, Q., Klopfenstein, Q., Bannier, P.A., Gidel, G., Massias, M.: Beyond L1: faster and better sparse models with skglm. In: 36th Conference on Neural Information Processing Systems (NeurIPS 2022). New Orleans, United States (2022)"},{"key":"2997_CR3","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.acha.2021.09.003","volume":"56","author":"N Bi","year":"2022","unstructured":"Bi, N., Tang, W.S.: A necessary and sufficient condition for sparse vector recovery via $$\\ell _1 - \\ell _2$$ minimization. Appl. Comput. Harmon. Anal. 56, 337\u2013350 (2022)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"1","key":"2997_CR4","doi-asserted-by":"publisher","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. Foundations and Trends in Machine Learning 3(1), 1\u2013122 (2011)","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"3","key":"2997_CR5","doi-asserted-by":"publisher","first-page":"1078","DOI":"10.1137\/20M1337041","volume":"14","author":"K Bui","year":"2021","unstructured":"Bui, K., Park, F., Lou, Y., Xin, J.: A weighted difference of anisotropic and isotropic total variation for relaxed mumford-shah color and multiphase image segmentation. SIAM J. Imag. Sci. 14(3), 1078\u20131113 (2021)","journal-title":"SIAM J. Imag. Sci."},{"issue":"8","key":"2997_CR6","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"1","key":"2997_CR7","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10107-012-0613-0","volume":"143","author":"X Chen","year":"2014","unstructured":"Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained $${L}_2-{L}_p$$ minimization. Math. Program. 143(1), 371\u2013383 (2014)","journal-title":"Math. Program."},{"issue":"38","key":"2997_CR8","first-page":"1","volume":"20","author":"Y Chen","year":"2019","unstructured":"Chen, Y., Ye, Y., Wang, M.: Approximation hardness for a class of sparse optimization problems. J. Mach. Learn. Res. 20(38), 1\u201327 (2019)","journal-title":"J. Mach. Learn. Res."},{"issue":"5","key":"2997_CR9","doi-asserted-by":"publisher","first-page":"2197","DOI":"10.1073\/pnas.0437847100","volume":"100","author":"DL Donoho","year":"2003","unstructured":"Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via $$\\ell ^1$$ minimization. Proc. Natl. Acad. Sci. 100(5), 2197\u20132202 (2003)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"4","key":"2997_CR10","doi-asserted-by":"publisher","first-page":"2010","DOI":"10.1137\/13090540X","volume":"6","author":"E Esser","year":"2013","unstructured":"Esser, E., Lou, Y., Xin, J.: A method for finding structured sparse solutions to nonnegative least squares problems with applications. SIAM J. Imag. Sci. 6(4), 2010\u20132046 (2013)","journal-title":"SIAM J. Imag. Sci."},{"issue":"456","key":"2997_CR11","doi-asserted-by":"publisher","first-page":"1348","DOI":"10.1198\/016214501753382273","volume":"96","author":"J Fan","year":"2001","unstructured":"Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348\u20131360 (2001)","journal-title":"J. Am. Stat. Assoc."},{"key":"2997_CR12","doi-asserted-by":"crossref","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkh\u00e4user Basel (2013)","DOI":"10.1007\/978-0-8176-4948-7"},{"issue":"2","key":"2997_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1080\/00401706.1993.10485033","volume":"35","author":"LE Frank","year":"1993","unstructured":"Frank, L.E., Friedman, J.H.: A statistical view of some chemometrics regression tools. Technometrics 35(2), 109\u2013135 (1993)","journal-title":"Technometrics"},{"key":"2997_CR14","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)"},{"issue":"2","key":"2997_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10107-011-0470-2","volume":"129","author":"D Ge","year":"2011","unstructured":"Ge, D., Jiang, X., Ye, Y.: A note on the complexity of $${L}_p$$ minimization. Math. Program. 129(2), 285\u2013299 (2011)","journal-title":"Math. Program."},{"key":"2997_CR16","doi-asserted-by":"crossref","unstructured":"G\u00fcler, O.: Foundations of Optimization. Springer Science & Business Media (2010)","DOI":"10.1007\/978-0-387-68407-9"},{"issue":"7","key":"2997_CR17","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1080\/00949650902773544","volume":"80","author":"X Huo","year":"2010","unstructured":"Huo, X., Chen, J.: Complexity of penalized likelihood estimation. J. Stat. Comput. Simul. 80(7), 747\u2013759 (2010)","journal-title":"J. Stat. Comput. Simul."},{"key":"2997_CR18","doi-asserted-by":"crossref","unstructured":"Jiang, Z., Hu, Q.: The complexity results of the sparse optimization problems and reverse convex optimization problems. Optimization Letters 14 (2020)","DOI":"10.1007\/s11590-020-01541-y"},{"key":"2997_CR19","doi-asserted-by":"crossref","unstructured":"Li, P., Chen, W., Ge, H., Ng, M.K.P.: $$\\ell _1 - \\alpha \\ell _2$$ minimization methods for signal and image reconstruction with impulsive noise removal. Inverse Problems 36 (2020)","DOI":"10.1088\/1361-6420\/ab750c"},{"key":"2997_CR20","doi-asserted-by":"crossref","unstructured":"Lou, Y., Osher, S., Xin, J.: Computational aspects of constrained $${L}_1$$-$${L}_2$$ minimization for compressive sensing. In: Modelling. Computation and Optimization in Information Systems and Management Sciences, pp. 169\u2013180. Springer International Publishing, Cham (2015)","DOI":"10.1007\/978-3-319-18161-5_15"},{"issue":"2","key":"2997_CR21","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1007\/s10915-017-0463-2","volume":"74","author":"Y Lou","year":"2018","unstructured":"Lou, Y., Yan, M.: Fast L1\u2013L2 minimization via a proximal operator. J. Sci. Comput. 74(2), 767\u2013785 (2018)","journal-title":"J. Sci. Comput."},{"issue":"1","key":"2997_CR22","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/s10915-014-9930-1","volume":"64","author":"Y Lou","year":"2015","unstructured":"Lou, Y., Yin, P., He, Q., Xin, J.: Computing sparse representation in a highly coherent dictionary based on difference of $${L}_1$$ and $${L}_2$$. J. Sci. Comput. 64(1), 178\u2013196 (2015)","journal-title":"J. Sci. Comput."},{"issue":"2","key":"2997_CR23","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539792240406","volume":"24","author":"BK Natarajan","year":"1995","unstructured":"Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2), 227\u2013234 (1995)","journal-title":"SIAM J. Comput."},{"key":"2997_CR24","doi-asserted-by":"crossref","unstructured":"Nguyen, T.T., Soussen, C., Idier, J., Djermoune, E.H.: NP-hardness of $$\\ell _0$$ minimization problems: revision and extension to the non-negative setting. 2019 13th International conference on Sampling Theory and Applications (SampTA) pp. 1\u20134 (2019)","DOI":"10.1109\/SampTA45681.2019.9030937"},{"issue":"3","key":"2997_CR25","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1214\/11-AOS878","volume":"39","author":"RJ Tibshirani","year":"2011","unstructured":"Tibshirani, R.J., Taylor, J.: The solution path of the generalized lasso. Ann. Stat. 39(3), 1335\u20131371 (2011)","journal-title":"Ann. Stat."},{"issue":"2","key":"2997_CR26","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1109\/TIT.2013.2290112","volume":"60","author":"AM Tillmann","year":"2013","unstructured":"Tillmann, A.M., Pfetsch, M.E.: The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans. Inf. Theory 60(2), 1248\u20131259 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"2997_CR27","doi-asserted-by":"publisher","first-page":"A536","DOI":"10.1137\/140952363","volume":"37","author":"P Yin","year":"2015","unstructured":"Yin, P., Lou, Y., He, Q., Xin, J.: Minimization of $$\\ell _{1-2}$$ for compressed sensing. SIAM J. Sci. Comput. 37(1), A536\u2013A563 (2015)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"2997_CR28","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1214\/09-AOS729","volume":"38","author":"CH Zhang","year":"2010","unstructured":"Zhang, C.H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894 (2010)","journal-title":"Ann. Stat."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-02997-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-026-02997-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-02997-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T04:13:28Z","timestamp":1781151208000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-026-02997-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,25]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["2997"],"URL":"https:\/\/doi.org\/10.1007\/s10957-026-02997-1","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,25]]},"assertion":[{"value":"4 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"45"}}