{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:29Z","timestamp":1740122429313,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071307"],"award-info":[{"award-number":["12071307"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _{1}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-algorithms for a class of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _{0}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-minimization models which can be used to model a wide range of practical problems. This class of algorithms is based on certain convex relaxations of the reformulation of the underlying <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _{0}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-minimization model. Such a reformulation is a special bilevel optimization problem which, in theory, is equivalent to the underlying <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _{0}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-minimization problem under the assumption of strict complementarity. Some basic properties of these algorithms are discussed, and numerical experiments have been carried out to demonstrate the efficiency of the proposed algorithms. Comparison of numerical performances of the proposed methods and the classic reweighted <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-algorithms has also been made in this paper.\n<\/jats:p>","DOI":"10.1007\/s10898-021-01013-2","type":"journal-article","created":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T20:03:50Z","timestamp":1618862630000},"page":"749-772","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dual-density-based reweighted $$\\ell _{1}$$-algorithms for a class of $$\\ell _{0}$$-minimization problems"],"prefix":"10.1007","volume":"81","author":[{"given":"Jialiang","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2388-9047","authenticated-orcid":false,"given":"Yun-Bin","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,19]]},"reference":[{"issue":"23","key":"1013_CR1","doi-asserted-by":"publisher","first-page":"5905","DOI":"10.1109\/TSP.2013.2279362","volume":"61","author":"MS Asif","year":"2013","unstructured":"Asif, M.S., Romberg, J.: Fast and accurate algorithms for re-weighted $$\\ell _{1}$$-norm minimization. IEEE Trans. Signal Process. 61(23), 5905\u20135916 (2013)","journal-title":"IEEE Trans. Signal Process."},{"issue":"16","key":"1013_CR2","doi-asserted-by":"publisher","first-page":"4209","DOI":"10.1109\/TSP.2014.2328981","volume":"62","author":"MS Asif","year":"2014","unstructured":"Asif, M.S., Romberg, J.: Sparse recovery of streaming signals using $$\\ell _{1}$$-homotopy. IEEE Trans. Signal Process. 62(16), 4209\u20134223 (2014)","journal-title":"IEEE Trans. Signal Process."},{"key":"1013_CR3","doi-asserted-by":"crossref","unstructured":"Blumensath, T., Davies, M., Rilling, G.: Greedy algorithms for compressed sensing. In: Compressed Sensing: Theory and Applications, Cambridge University Press, 348\u2013393 (2012)","DOI":"10.1017\/CBO9780511794308.009"},{"key":"1013_CR4","doi-asserted-by":"publisher","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":"1013_CR5","first-page":"1433","volume":"3","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J.: Compressive sampling. Proc. Int. Congr. Math. 3, 1433\u20131452 (2006)","journal-title":"Proc. Int. Congr. Math."},{"issue":"8","key":"1013_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.K., 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":"12","key":"1013_CR7","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5\u20136","key":"1013_CR8","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s00041-008-9045-x","volume":"14","author":"EJ Cand\u00e8s","year":"2008","unstructured":"Cand\u00e8s, E.J., Wakin, M.B., Boyd, S.P.: Enhancing sparsity by reweighted $$\\ell _{1}$$ minimization. J. Fourier Anal. Appl. 14(5\u20136), 877\u2013905 (2008)","journal-title":"J. Fourier Anal. Appl."},{"key":"1013_CR9","unstructured":"Chen, X., Zhou, W.: Convergence of reweighted $$\\ell _{1}$$ minimization algorithms and unique solution of truncated $$\\ell _{p}$$ minimization. Department of Applied Mathematics, The Hong Kong Polytechnic University (2010)"},{"issue":"5","key":"1013_CR10","doi-asserted-by":"publisher","first-page":"2230","DOI":"10.1109\/TIT.2009.2016006","volume":"55","author":"W Dai","year":"2009","unstructured":"Dai, W., Milenkovic, O.: Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Inf. Theory 55(5), 2230\u20132249 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"11","key":"1013_CR11","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1002\/cpa.20042","volume":"57","author":"I Daubechies","year":"2004","unstructured":"Daubechies, I., Defrise, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57(11), 1413\u20131457 (2004)","journal-title":"Commun. Pure Appl. Math."},{"issue":"4","key":"1013_CR12","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1013_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511794308","volume-title":"Compressed Sensing: Theory and Applications","author":"YC Eldar","year":"2012","unstructured":"Eldar, Y.C., Kutyniok, G.: Compressed Sensing: Theory and Applications. Cambridge University Press, Cambridge (2012)"},{"key":"1013_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7011-4","volume-title":"Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing","author":"M Elad","year":"2010","unstructured":"Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer, New York (2010)"},{"issue":"3","key":"1013_CR15","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.acha.2008.09.001","volume":"26","author":"S Foucart","year":"2009","unstructured":"Foucart, S., Lai, M.J.: Sparsest solutions of underdetermined linear systems via $$\\ell _{q}$$-minimization for $$0< q< 1$$. Appl. Comput. Harmon. Anal. 26(3), 395\u2013407 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1013_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7","volume-title":"A Mathematical Introduction to Compressive Sensing","author":"S Foucart","year":"2013","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Springer, New York (2013)"},{"issue":"4","key":"1013_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0013-4694(95)00107-A","volume":"95","author":"IF Gorodnitsky","year":"1995","unstructured":"Gorodnitsky, I.F., George, J.S., Rao, B.D.: Neuromagnetic source imaging with FOCUSS: a recursive weighted minimum norm algorithm. Electroen. Clin. Neuro. 95(4), 231\u2013251 (1995)","journal-title":"Electroen. Clin. Neuro."},{"key":"1013_CR18","unstructured":"Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, Version 2.1, 2014"},{"key":"1013_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nowak, R., Recht, B.: Sample complexity for 1-bit compressed sensing and sparse classification. In: IEEE International Symposium on Information Theory, 1553\u20131557 (2010)","DOI":"10.1109\/ISIT.2010.5513510"},{"key":"1013_CR20","unstructured":"Harikumar, G., Bresler, Y.: A new algorithm for computing sparse solutions to linear inverse problems. In: Proceedings of International Conference on Acoustics, Speech, Signal Processing (ICASSP) (1996)"},{"issue":"4","key":"1013_CR21","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1198\/jcgs.2010.09208","volume":"19","author":"H Hoefling","year":"2010","unstructured":"Hoefling, H.: A path algorithm for the fused lasso signal approximator. J. Comput. Graph. Stat. 19(4), 984\u20131006 (2010)","journal-title":"J. Comput. Graph. Stat."},{"issue":"1","key":"1013_CR22","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1137\/090775397","volume":"21","author":"MJ Lai","year":"2011","unstructured":"Lai, M.J., Wang, J.: An unconstrained $$\\ell _{q}$$ minimization with $$0<q\\le 1$$ for sparse solution of underdetermined linear systems. SIAM J. Optim. 21(1), 82\u2013101 (2011)","journal-title":"SIAM J. Optim."},{"issue":"11","key":"1013_CR23","doi-asserted-by":"publisher","first-page":"5289","DOI":"10.1109\/TSP.2011.2162324","volume":"59","author":"JN Laska","year":"2011","unstructured":"Laska, J.N., Wen, Z., Yin, W., Baraniuk, R.G.: Trust, but verify: fast and accurate signal recovery from 1-bit compressive measurements. IEEE Trans. Signal Process. 59(11), 5289\u20135301 (2011)","journal-title":"IEEE Trans. Signal Process."},{"key":"1013_CR24","doi-asserted-by":"crossref","unstructured":"Liu, J., Yuan, L., Ye, J.: An efficient algorithm for a class of fused lasso problems. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 323\u2013332 (2010)","DOI":"10.1145\/1835804.1835847"},{"issue":"12","key":"1013_CR25","doi-asserted-by":"publisher","first-page":"3397","DOI":"10.1109\/78.258082","volume":"41","author":"SG Mallat","year":"1993","unstructured":"Mallat, S.G., Zhang, Z.: Matching pursuit with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397\u20133415 (1993)","journal-title":"IEEE Trans. Signal Process."},{"key":"1013_CR26","doi-asserted-by":"publisher","first-page":"6594","DOI":"10.1109\/TSP.2020.3037996","volume":"68","author":"N Meng","year":"2020","unstructured":"Meng, N., Zhao, Y.B.: Newton-step-based hard thresholding algorithms for sparse signal recovery. IEEE Trans. Signal Process. 68, 6594\u20136606 (2020)","journal-title":"IEEE Trans. Signal Process."},{"issue":"3","key":"1013_CR27","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.acha.2008.07.002","volume":"26","author":"D Needell","year":"2009","unstructured":"Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26(3), 301\u2013321 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"6","key":"1013_CR28","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1080\/10556788.2010.511668","volume":"26","author":"F Rinaldi","year":"2011","unstructured":"Rinaldi, F.: Concave programming for finding sparse solutions to problems with convex constraints. Optim. Methods Softw. 26(6), 971\u2013992 (2011)","journal-title":"Optim. Methods Softw."},{"issue":"5B","key":"1013_CR29","doi-asserted-by":"publisher","first-page":"2922","DOI":"10.1214\/08-AOS665","volume":"37","author":"A Rinaldo","year":"2009","unstructured":"Rinaldo, A.: Properties and refinements of the fused lasso. Ann. Stat. 37(5B), 2922\u20132952 (2009)","journal-title":"Ann. Stat."},{"issue":"1","key":"1013_CR30","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s102080010029","volume":"3","author":"VN Temlyakov","year":"2003","unstructured":"Temlyakov, V.N.: Nonlinear methods of approximation. Found. Comut. Math. 3(1), 33\u2013107 (2003)","journal-title":"Found. Comut. Math."},{"issue":"1","key":"1013_CR31","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1093\/biostatistics\/kxm013","volume":"9","author":"R Tibshirani","year":"2008","unstructured":"Tibshirani, R., Wang, P.: Spatial smoothing and hot spot detection for CGH data using the fused lasso. Biostatistics 9(1), 18\u201329 (2008)","journal-title":"Biostatistics"},{"key":"1013_CR32","volume-title":"Statistical Learning with Sparsity: The Lasso and Generalizations","author":"R Tibshirani","year":"2015","unstructured":"Tibshirani, R., Wainwright, M., Hastie, T.: Statistical Learning with Sparsity: The Lasso and Generalizations. Chapman and Hall\/CRC, Boca Raton (2015)"},{"key":"1013_CR33","unstructured":"Xu, J.L.: Nonuniqueness of solutions of a class of $$\\ell _ {0}$$-minimization problems. To appear in J. Oper. Res. Soc. China"},{"issue":"4","key":"1013_CR34","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1080\/10556788.2020.1734003","volume":"35","author":"JL Xu","year":"2020","unstructured":"Xu, J.L., Zhao, Y.B.: Stability analysis of a class of sparse optimization problems. Optim. Methods Softw. 35(4), 836\u2013854 (2020)","journal-title":"Optim. Methods Softw."},{"key":"1013_CR35","doi-asserted-by":"publisher","DOI":"10.1201\/9781315113142","volume-title":"Sparse Optimization Theory and Methods","author":"YB Zhao","year":"2018","unstructured":"Zhao, Y.B.: Sparse Optimization Theory and Methods. CRC Press, Boca Raton (2018)"},{"issue":"1","key":"1013_CR36","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/18M1219187","volume":"30","author":"YB Zhao","year":"2020","unstructured":"Zhao, Y.B.: Optimal $$k$$-thresholding algorithms for sparse optimization problems. SIAM J. Optim. 30(1), 31\u201355 (2020)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1013_CR37","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/140968240","volume":"25","author":"YB Zhao","year":"2015","unstructured":"Zhao, Y.B., Ko\u010dvara, M.: A new computational method for the sparsest solutions to systems of linear equations. SIAM J. Optim. 25(2), 1110\u20131134 (2015)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1013_CR38","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1137\/110847445","volume":"22","author":"YB Zhao","year":"2012","unstructured":"Zhao, Y.B., Li, D.: Reweighted $$\\ell _{1}$$-minimization for sparse solutions to underdetermined linear systems. SIAM J. Optim. 22(3), 1065\u20131088 (2012)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1013_CR39","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1287\/moor.2016.0791","volume":"42","author":"YB Zhao","year":"2017","unstructured":"Zhao, Y.B., Luo, Z.Q.: Constructing new weighted $$\\ell _{1}$$-algorithms for the sparsest points of polyhedral sets. Math. Oper. Res. 42(1), 57\u201376 (2017)","journal-title":"Math. Oper. Res."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01013-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01013-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01013-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,18]],"date-time":"2021-10-18T04:31:19Z","timestamp":1634531479000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01013-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,19]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1013"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01013-2","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2021,4,19]]},"assertion":[{"value":"2 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}