{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:40Z","timestamp":1787340940840,"version":"build-2736575974"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherent drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop a truly efficient thresholding method is a fundamental question in this field. The aim of this paper is to address this question by proposing a new thresholding technique based on the notion of optimal $k$-thresholding. The central idea for this new development is to connect the $k$-thresholding directly to the residual reduction during the course of algorithms. This leads to a natural design principle for the efficient thresholding methods. Under the restricted isometry property, we prove that the optimal thresholding based algorithms are globally convergent to the solution of sparse optimization problems. The numerical experiments demonstrate that when solving sparse optimization problems, the traditional hard thresholding methods have been significantly transcended by the proposed algorithms which can even outperform the classic $\\ell_1$-minimization method in many situations.<\/jats:p>","DOI":"10.1137\/18m1219187","type":"journal-article","created":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T15:02:53Z","timestamp":1577977373000},"page":"31-55","source":"Crossref","is-referenced-by-count":50,"title":["Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems"],"prefix":"10.1137","volume":"30","author":[{"given":"Yun-Bin","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,1,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Beck and Y. C. Eldar,\n                      Sparse signal recovery from nonlinear measurements\n                      , in Proceedings of the 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 5464-5468.","DOI":"10.1109\/ICASSP.2013.6638708"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120869778"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1388"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2014.2379665"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2011.09.017"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9035-z"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.04.002"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2010.2042411"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"J.U. Bouchot,\n                      A generalized class of hard thresholding algorithms for sparse signal recovery\n                      , in Approximation Theory XIV: San Antonio 2013, Springer Proceedings in Mathematics & Statistics, G. Fasshauer and L. Schumaker, eds., 83 (2014), pp. 45-63.","DOI":"10.1007\/978-3-319-06404-8_4"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2016.03.002"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/060657704"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2017.0789"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9045-x"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1117\/12.894386"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"W. A. Chaovalitwongse, I. P. Androulakis, and P. M. Pardalos,\n                      Quadratic integer programming: Complexity and equivalent forms\n                      , in Encyclopedia of Optimization, C. Floudas and P. Pardalos, eds., Springer, Boston, MA, 2008.","DOI":"10.1007\/978-0-387-74759-0_536"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016006"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20042"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/18.382009"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/81.3.425"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885522"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"M. Elad,\n                      Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing\n                      , Springer, New York, NY, 2010.","DOI":"10.1007\/978-1-4419-7011-4"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"Y. C. Eldar and G. Kutyniok,\n                      Compressed Sensing: Theory and Applications\n                      , Cambridge University Press, Cambridge, UK, 2012.","DOI":"10.1017\/CBO9780511794308"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2003.814255"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2007.10.005"},{"key":"atypb29","first-page":"65","author":"Foucart S.","year":"2012","journal-title":"NY"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/100806278"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.09.001"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"S. Foucart and H. Rauhut,\n                      A Mathematical Introduction to Compressive Sensing\n                      , Springer, New York, NY, 2013.","DOI":"10.1007\/978-0-8176-4948-7"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"R. Garg and R. Khandekar,\n                      Gradient descent with sparsification: An iterative algorithm for sparse recovery with restricted isometry property\n                      , in Proceedings of the International Conference on Machine Learning, 2009, Montreal, Canada, pp. 337-344.","DOI":"10.1145\/1553374.1553417"},{"key":"atypb34","unstructured":"M. Grant and S. Boyd,\n                      CVX: MATLAB Software for Disciplined Convex Programming\n                      , version 1.21, April 2017."},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"K. Herrity, A. Gilbert, and J. Tropp,\n                      Sparse approximation via iterative thresholding\n                      , in Proceedings of the 2006 IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 624-627.","DOI":"10.1109\/ICASSP.2006.1660731"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.2307\/2372313"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"K. Lange,\n                      MM Optimization Algorithms\n                      , SIAM, Philadelphia, PA, 2016.","DOI":"10.1137\/1.9781611974409"},{"key":"atypb38","unstructured":"R. Khanna and A. Kyrillidis,\n                      IHT Dies Hard: Provable Accelerated Iterative Hard Thresholding\n                      , preprint,arXiv:1712.09379[math.OC], 2017."},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"N. Kingsbury and T. Reeves,\n                      Redundant representation with complex wavelets: How to achieve sparsity\n                      , in Proceedings of the 2003 IEEE International Conference on Image Processing, Barcelona, pp. 45-48.","DOI":"10.1109\/ICIP.2003.1246894"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-013-0434-7"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"H. Liu, M.C. Yue, A.M.C. So, and W.K., Ma,\n                      A discrete first-order method for large-scale MIMO detection with provable guarantees\n                      , in Proceedings of the IEEE 18th Internal Workshop on Signal Processing Advances in Wireless Communications, 2017.","DOI":"10.1109\/SPAWC.2017.8227768"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"A. Maleki,\n                      Coherence Analysis of Iterative Thresholding Algorithms\n                      , in Proceedings of the Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, 2009, pp. 236-243.","DOI":"10.1109\/ALLERTON.2009.5394802"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/78.258082"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1117\/12.173207"},{"key":"atypb45","unstructured":"A. Miller,\n                      Subset Selection in Regression\n                      , CRC Press, Boca Raton, FL, 2002."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.07.002"},{"key":"atypb48","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Springer Science and Business Media, New York, NY, 2013."},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"T. H. Reeves and N. G. Kingsbury,\n                      Overcomplete image coding using iterative projection-based noise shaping\n                      , in Proceedings of the 2002 IEEE International Conference on Image Processing, Rochester, pp. 597-600.","DOI":"10.1109\/ICIP.2002.1039041"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-1684(03)00150-6"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2012.08.004"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909108"},{"key":"atypb53","unstructured":"Y.B. Zhao,\n                      Sparse Optimization Theory and Methods\n                      , CRC Press, Boca Raton, FL, 2018."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/140968240"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0791"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/110847445"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1219187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:58Z","timestamp":1787338618000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1219187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1219187"],"URL":"https:\/\/doi.org\/10.1137\/18m1219187","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}