{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:37:00Z","timestamp":1787330220982,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Numerical experiments have indicated that the reweighted $\\ell_1$-minimization performs exceptionally well in locating sparse solutions of underdetermined linear systems of equations. We show that reweighted $\\ell_1$-methods are intrinsically associated with the minimization of the so-called merit functions for sparsity, which are essentially concave approximations to the cardinality function. Based on this observation, we further show that a family of reweighted $\\ell_1$-algorithms can be systematically derived from the perspective of concave optimization through the linearization technique. In order to conduct a unified convergence analysis for this family of algorithms, we introduce the concept of the range space property (RSP) of a matrix and prove that if its adjoint has this property, the reweighted $\\ell_1$-algorithm can find a sparse solution to the underdetermined linear system provided that the merit function for sparsity is properly chosen. In particular, some convergence conditions for the Cand\u00e8s--Wakin--Boyd method and the recent $\\ell_p$-quasi-norm-based reweighted $\\ell_1$-method can be obtained as special cases of the general framework.<\/jats:p>","DOI":"10.1137\/110847445","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T20:54:16Z","timestamp":1347396856000},"page":"1065-1088","source":"Crossref","is-referenced-by-count":100,"title":["Reweighted $\\ell_1$-Minimization for Sparse Solutions to Underdetermined Linear Systems"],"prefix":"10.1137","volume":"22","author":[{"given":"Yun-Bin","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Duan","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,9,11]]},"reference":[{"key":"atyp_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/83.661180"},{"key":"atyp_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/060657704"},{"key":"atyp_ref3","doi-asserted-by":"crossref","unstructured":"3.\u2002E. Cand\u00e8s, <i>Compressive sampling<\/i> in International Congress of Mathematicians, Vol. III, 2006, pp. 1433-1452.","DOI":"10.4171\/022-3\/69"},{"key":"atyp_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atyp_ref5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"atyp_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"atyp_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"atyp_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"atyp_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9045-x"},{"key":"atyp_ref10","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2007.898300"},{"key":"atyp_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"atyp_ref12","unstructured":"12.\u2002X. Chen and W. Zhou, <i>Convergence of Reweighted $\\ell_1$ Minimization Algorithms and Unique Solution of Truncated $\\ell_p$ Minimization<\/i> Technical report, The Hong Kong Polytechnic University, Hong Kong, 2010."},{"key":"atyp_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00610-3"},{"key":"atyp_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20303"},{"key":"atyp_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016030"},{"key":"atyp_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"atyp_ref17","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0437847100"},{"key":"atyp_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/18.959265"},{"key":"atyp_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0149053"},{"key":"atyp_ref20","unstructured":"20.\u2002M. Fazel, <i>Matrix Rank Minimization with Applications<\/i> Ph.D. thesis, Stanford University, Stanford, CA, 2002."},{"key":"atyp_ref21","first-page":"3273","author":"Fazel M.","year":"2004","journal-title":"Washington, DC"},{"key":"atyp_ref22","unstructured":"22.\u2002M. Fazel, H. Hindi, and S. Boyd, <i>Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices<\/i> in Proceedings of the American Control Conference, IEEE, Washington, DC, 2003."},{"key":"atyp_ref23","first-page":"187","author":"Fornasier M.","year":"2011","journal-title":"New York"},{"key":"atyp_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.09.001"},{"key":"atyp_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/78.558475"},{"key":"atyp_ref26","unstructured":"26.\u2002M. Grant and S. Boyd, <i>CVX: Matlab Software for Disciplined Convex Programming, Version<\/i> 1.21, April 2011."},{"key":"atyp_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.820031"},{"key":"atyp_ref28","first-page":"1331","author":"Harikumar G.","year":"1996","journal-title":"GA"},{"key":"atyp_ref29","doi-asserted-by":"publisher","DOI":"10.1080\/03610927708827533"},{"key":"atyp_ref30","doi-asserted-by":"crossref","unstructured":"30.\u2002R. Horst, P. M. Pardalos, and N. V. Thoai, <i>Introduction to Global Optimization<\/i> 2nd ed., Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000.","DOI":"10.1007\/978-1-4615-0015-5"},{"key":"atyp_ref31","doi-asserted-by":"publisher","DOI":"10.1137\/090775397"},{"key":"atyp_ref32","unstructured":"32.\u2002C. Lawson, <i>Contributions to the Theory of Linear Least Maximum Approximation<\/i> Ph.D. thesis, University of California Los Angeles, Los Angeles, CA, 1961."},{"key":"atyp_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-0145-1"},{"key":"atyp_ref34","doi-asserted-by":"publisher","DOI":"10.1109\/78.258082"},{"key":"atyp_ref35","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"atyp_ref36","doi-asserted-by":"crossref","unstructured":"36.\u2002D. Needell, <i>Noisy signal recovery via iterative reweighted $\\ell_1$-minimization<\/i> in Proceedings of the 43rd Asilomar Conference on Signals, Systems and Computers, Asilomar'09, Pacific Grove, CA, 2009, pp. 113-117.","DOI":"10.1109\/ACSSC.2009.5470154"},{"key":"atyp_ref37","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"atyp_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0422-2"},{"key":"atyp_ref39","doi-asserted-by":"publisher","DOI":"10.1190\/1.1440921"},{"key":"atyp_ref40","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","year":"1996","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"atyp_ref41","first-page":"301","volume":"26","author":"Tropp J.","year":"2008","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"atyp_ref42","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2010.2042413"},{"key":"atyp_ref43","unstructured":"43.\u2002Y. Zhang, <i>Theory of Compressive Sensing via $\\ell_1$-Minimization: A Non-RIP Analysis and Extensions<\/i> Technical report, Rice University, Houston, TX, 2008."},{"key":"atyp_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.02.021"},{"key":"atyp_ref45","doi-asserted-by":"publisher","DOI":"10.1137\/040603838"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110847445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:53:12Z","timestamp":1787327592000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110847445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110847445"],"URL":"https:\/\/doi.org\/10.1137\/110847445","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}