{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T07:45:04Z","timestamp":1770536704328,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000},"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":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The optimization problems with a sparsity constraint is a class of important global optimization problems. A typical type of thresholding algorithms for solving such a problem adopts the traditional full steepest descent direction or Newton-like direction as a search direction to generate an iterate on which a certain thresholding is performed. Traditional hard thresholding discards a large part of a vector, and thus some important information contained in a dense vector has been lost in such a thresholding process. Recent study (Zhao in SIAM J Optim 30(1): 31\u201355, 2020) shows that the hard thresholding should be applied to a compressible vector instead of a dense vector to avoid a big loss of information. On the other hand, the optimal <jats:italic>k<\/jats:italic>-thresholding as a novel thresholding technique may overcome the intrinsic drawback of hard thresholding, and performs thresholding and objective function minimization simultaneously. This motivates us to propose the so-called partial gradient optimal thresholding (PGOT) method and its relaxed versions in this paper. The PGOT is an integration of the partial gradient and the optimal <jats:italic>k<\/jats:italic>-thresholding technique. The solution error bound and convergence for the proposed algorithms have been established in this paper under suitable conditions. Application of our results to the sparse optimization problems arising from signal recovery is also discussed. Experiment results from synthetic data indicate that the proposed algorithm is efficient and comparable to several existing algorithms.<\/jats:p>","DOI":"10.1007\/s10898-022-01143-1","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T09:04:35Z","timestamp":1645607075000},"page":"393-413","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Partial gradient optimal thresholding algorithms for a class of sparse optimization problems"],"prefix":"10.1007","volume":"84","author":[{"given":"Nan","family":"Meng","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"}]},{"given":"Michal","family":"Ko\u010dvara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhongfeng","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,23]]},"reference":[{"key":"1143_CR1","doi-asserted-by":"crossref","unstructured":"Andersen, E. D., Andersen, K. D.: The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High performance optimization. Springer, Boston, MA, 33, 197-232 (2000)","DOI":"10.1007\/978-1-4757-3216-0_8"},{"issue":"2","key":"1143_CR2","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1002\/nla.1948","volume":"22","author":"JD Blanchard","year":"2015","unstructured":"Blanchard, J.D., Tanner, J.: Performance comparisons of greedy algorithms in compressed sensing. Numer. Linear Algebra Appl. 22(2), 254\u2013282 (2015)","journal-title":"Numer. Linear Algebra Appl."},{"issue":"4","key":"1143_CR3","first-page":"289","volume":"4","author":"JD Blanchard","year":"2015","unstructured":"Blanchard, J.D., Tanner, J., Wei, K.: CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion. Inform. Inference J. IMA 4(4), 289\u2013327 (2015)","journal-title":"Inform. Inference J. IMA"},{"key":"1143_CR4","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1016\/j.sigpro.2011.09.017","volume":"92","author":"T Blumensath","year":"2012","unstructured":"Blumensath, T.: Accelerated iterative hard thresholding. Signal Process. 92, 752\u2013756 (2012)","journal-title":"Signal Process."},{"key":"1143_CR5","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/s00041-008-9035-z","volume":"14","author":"T Blumensath","year":"2008","unstructured":"Blumensath, T., Davies, M.: Iterative hard thresholding for sparse approximation. J. Fourier Anal. Appl. 14, 629\u2013654 (2008)","journal-title":"J. Fourier Anal. Appl."},{"key":"1143_CR6","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.acha.2009.04.002","volume":"27","author":"T Blumensath","year":"2009","unstructured":"Blumensath, T., Davies, M.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27, 265\u2013274 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1143_CR7","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1109\/JSTSP.2010.2042411","volume":"4","author":"T Blumensath","year":"2010","unstructured":"Blumensath, T., Davies, M.: Normalized iterative hard thresholding: guaranteed stability and performance. IEEE J. Sel. Top. Signal Process. 4, 298\u2013309 (2010)","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"1143_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-73074-5","volume-title":"Compressed Sensing and its Applications","author":"H Boche","year":"2019","unstructured":"Boche, H., Calderbank, R., Kutyniok, G., Vybiral, J.: Compressed Sensing and its Applications. Springer, New York (2019)"},{"key":"1143_CR9","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/j.acha.2016.03.002","volume":"41","author":"J Bouchot","year":"2016","unstructured":"Bouchot, J., Foucart, S., Hitczenki, P.: Hard thresholding pursuit algorithms: number of iterations. Appl. Comput. Harmon. Anal. 41, 412\u2013435 (2016)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"7","key":"1143_CR10","doi-asserted-by":"publisher","first-page":"4680","DOI":"10.1109\/TIT.2011.2146090","volume":"57","author":"T Cai","year":"2011","unstructured":"Cai, T., Wang, L.: Orthogonal matching pursuit for sparse signal recovery with noise. IEEE Trans. Inform. Theory 57(7), 4680\u20134688 (2011)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"12","key":"1143_CR11","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"1143_CR12","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52(2), 489\u2013509 (2006)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"1143_CR13","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s00041-008-9045-x","volume":"14","author":"E Cand\u00e8s","year":"2008","unstructured":"Cand\u00e8s, E., Wakin, M., Boyd, S.: Enhancing sparsity by reweighted $$\\ell _1$$-minimization. J. Fourier Anal. Appl. 14, 877\u2013905 (2008)","journal-title":"J. Fourier Anal. Appl."},{"issue":"1","key":"1143_CR14","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1137\/S003614450037906X","volume":"43","author":"S Chen","year":"2001","unstructured":"Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM Rev. 43(1), 129\u2013159 (2001)","journal-title":"SIAM Rev."},{"issue":"3","key":"1143_CR15","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1109\/COMST.2017.2664421","volume":"19","author":"J Choi","year":"2017","unstructured":"Choi, J., Shim, B., Ding, Y., Rao, B., Kim, D.: Compressed sensing for wireless communications: useful tips and tricks. IEEE Commun. Surv. Tutor. 19(3), 1527\u20131549 (2017)","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"1143_CR16","unstructured":"Dai, W., Milenkovic, O.: Subspace pursuit for compressive sensing: Closing the gap between performance and complexity. ILLINOIS UNIV AT URBANA-CHAMAPAIGN (2008)"},{"key":"1143_CR17","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. Inform. Theory 55, 2230\u20132249 (2009)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"1143_CR18","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1109\/18.382009","volume":"41","author":"D Donoho","year":"1995","unstructured":"Donoho, D.: De-noising by soft-thresholding. IEEE Trans. Inform. Theory 41, 613\u2013627 (1995)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1906","key":"1143_CR19","doi-asserted-by":"publisher","first-page":"4273","DOI":"10.1098\/rsta.2009.0152","volume":"367","author":"D Donoho","year":"2009","unstructured":"Donoho, D., Tanner, J.: Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philos. Trans. R. Soc. A Math. Phys. Eng. Sci. 367(1906), 4273\u20134293 (2009)","journal-title":"Philos. Trans. R. Soc. A Math. Phys. Eng. Sci."},{"key":"1143_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511794308","volume-title":"Compressed Sensing: Theory and Applications","author":"Y Eldar","year":"2012","unstructured":"Eldar, Y., Kutyniok, G.: Compressed Sensing: Theory and Applications. Cambridge University Press, Cambridge (2012)"},{"issue":"2","key":"1143_CR21","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.acha.2007.10.005","volume":"25","author":"M Fornasier","year":"2008","unstructured":"Fornasier, M., Rauhut, H.: Iterative thresholding algorithms. Appl. Comput. Harmon. Anal. 25(2), 187\u2013208 (2008)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1143_CR22","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":"6","key":"1143_CR23","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1137\/100806278","volume":"49","author":"S Foucart","year":"2011","unstructured":"Foucart, S.: Hard thresholding pursuit: an algorithm for compressive sensing. SIAM J. Numer. Anal. 49(6), 2543\u20132563 (2011)","journal-title":"SIAM J. Numer. Anal."},{"key":"1143_CR24","doi-asserted-by":"crossref","unstructured":"Garg, R., Khandekar, R.: Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property. In: Proceedings of the 26th annual international conference on machine learning (2009)","DOI":"10.1145\/1553374.1553417"},{"key":"1143_CR25","unstructured":"Grant, M., Boyd, S.: CVX: matlab software for disciplined convex programming. Version 1.21, (2017)"},{"key":"1143_CR26","doi-asserted-by":"crossref","unstructured":"Huang, G., Wang, L.: Soft-thresholding orthogonal matching pursuit for efficient signal reconstruction. In: Proceedings of the 2013 IEEE international conference on acoustics, speech and signal processing. 2543\u20132547 (2013)","DOI":"10.1109\/ICASSP.2013.6638114"},{"key":"1143_CR27","unstructured":"Khanna, R., Kyrillidis, A.: IHT dies hard: Provable accelerated iterative hard thresholding. Int. Conf. Artif. Intell. Stat. 188\u2013198 (2018)"},{"issue":"9","key":"1143_CR28","doi-asserted-by":"publisher","first-page":"2130","DOI":"10.1109\/TMI.2016.2550080","volume":"35","author":"Y Liu","year":"2016","unstructured":"Liu, Y., Zhan, Z., Cai, J.F., et al.: Projected iterative soft-thresholding algorithm for tight frames in compressed sensing magnetic resonance imaging. IEEE Trans. Med. Imag. 35(9), 2130\u20132140 (2016)","journal-title":"IEEE Trans. Med. Imag."},{"key":"1143_CR29","unstructured":"Meng, N., Zhao, Y.-B.: Newton-type optimal thresholding algorithms for sparse optimization problems. arXiv preprint arXiv:2104.02371 (2021)"},{"key":"1143_CR30","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."},{"key":"1143_CR31","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.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26, 301\u2013321 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"2","key":"1143_CR32","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1109\/JSTSP.2010.2042412","volume":"4","author":"D Needell","year":"2010","unstructured":"Needell, D., Vershynin, R.: Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE J. Sel. Top. Signal Process. 4(2), 310\u2013316 (2010)","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"1143_CR33","doi-asserted-by":"crossref","unstructured":"Patel, V., Chellappa, R.: Sparse representations, compressive sensing and dictionaries for pattern recognition. The First Asian Conference on Pattern Recognition, IEEE. 325\u2013329 (2011)","DOI":"10.1109\/ACPR.2011.6166711"},{"issue":"12","key":"1143_CR34","doi-asserted-by":"publisher","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","volume":"53","author":"J Tropp","year":"2007","unstructured":"Tropp, J., Gilbert, A.: Signal recovery from random measurements via orthogonal mathcing pursuit. IEEE Trans. Inform. Theory 53(12), 4655\u20134666 (2007)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"1143_CR35","doi-asserted-by":"crossref","unstructured":"Yuan, X.-T., Liu, Q.: Newton greedy pursuit: A quadratic approximation method for sparsity-constrained optimization. In: Proceedings of the IEEE conference on computer vision and pattern recognition. 4122\u20134129 (2014)","DOI":"10.1109\/CVPR.2014.525"},{"key":"1143_CR36","unstructured":"Zhao, Y.-B., Luo, Z.-Q.: Improved Rip-based bounds for guaranteed performance of two compressed sensing algorithms. arXiv:2007.01451v3 (2020)"},{"key":"1143_CR37","doi-asserted-by":"publisher","DOI":"10.1201\/9781315113142","volume-title":"Sparse Optimization Theory and Methods","author":"Y-B Zhao","year":"2018","unstructured":"Zhao, Y.-B.: Sparse Optimization Theory and Methods. CRC Press, Boca Raton, FL (2018)"},{"issue":"1","key":"1143_CR38","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/18M1219187","volume":"30","author":"Y-B 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":"1143_CR39","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/140968240","volume":"25","author":"Y-B 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":"1143_CR40","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1137\/110847445","volume":"22","author":"Y-B 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."},{"key":"1143_CR41","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1287\/moor.2016.0791","volume":"42","author":"Y-B Zhao","year":"2017","unstructured":"Zhao, Y.-B., Luo, Z.-Q.: Constructing new reweighted $$\\ell _1$$-algorithms for sparsest points of polyhedral sets. Math. Oper. Res. 42, 57\u201376 (2017)","journal-title":"Math. Oper. Res."},{"key":"1143_CR42","doi-asserted-by":"publisher","first-page":"108148","DOI":"10.1016\/j.sigpro.2021.108148","volume":"187","author":"Y-B Zhao","year":"2021","unstructured":"Zhao, Y.-B., Luo, Z.-Q.: Analysis of optimal thresholding algorithms for compressed sensing. Signal Process. 187, 108148 (2021)","journal-title":"Signal Process."},{"key":"1143_CR43","doi-asserted-by":"crossref","unstructured":"Zhou, S., Pan, L., Xiu, N.: Subspace Newton method for the $$\\ell _0 $$-regularized optimization. arXiv:2004.05132 (2020)","DOI":"10.1007\/s11075-021-01085-x"},{"issue":"12","key":"1143_CR44","first-page":"1","volume":"22","author":"S Zhou","year":"2021","unstructured":"Zhou, S., Xiu, N., Qi, H.: Global and quadratic convergence of Newton hard-thresholding pursuit. J. Mach. Learn. Res. 22(12), 1\u201345 (2021)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01143-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-022-01143-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01143-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T10:09:51Z","timestamp":1663754991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-022-01143-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,23]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["1143"],"URL":"https:\/\/doi.org\/10.1007\/s10898-022-01143-1","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,23]]},"assertion":[{"value":"15 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}