{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T20:23:04Z","timestamp":1787343784102,"version":"build-2736575974"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The connection between the sparsest solution to an underdetermined system of linear equations and the weighted $\\ell_1$-minimization problem is established in this paper. We show that seeking the sparsest solution to a linear system can be transformed to searching for the densest slack variable of the dual problem of weighted $\\ell_1$-minimization with all possible choices of nonnegative weights. Motivated by this fact, a new reweighted $\\ell_1$-algorithm for the sparsest solutions of linear systems, going beyond the framework of existing sparsity-seeking methods, is proposed in this paper. Unlike existing reweighted $\\ell_1$-methods that are based on the weights defined directly in terms of iterates, the new algorithm computes a weight in dual space via certain convex optimization and uses such a weight to locate the sparsest solutions. It turns out that the new algorithm converges to the sparsest solutions of linear systems under some mild conditions that do not require the uniqueness of the sparsest solutions. Empirical results demonstrate that this new computational method remarkably outperforms $\\ell_1$-minimization and stands as one of the very efficient sparsity-seeking algorithms for the sparsest solutions of systems of linear equations.<\/jats:p>","DOI":"10.1137\/140968240","type":"journal-article","created":{"date-parts":[[2015,6,18]],"date-time":"2015-06-18T13:26:42Z","timestamp":1434634002000},"page":"1110-1134","source":"Crossref","is-referenced-by-count":15,"title":["A New Computational Method for the Sparsest Solutions to Systems of Linear Equations"],"prefix":"10.1137","volume":"25","author":[{"given":"Yun-Bin","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Ko\u010dvara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,6,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2279362"},{"key":"atypb2","unstructured":"M. S. Asif and J. Romberg,\n                      Sparse Recovery of Streaming Signals Using $\\ell_1$-Homotopy\n                      , arXiv:1306.3331, 2013."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"B. Babadi, D. Ba, P. Purdon, and E. Brown,\n                      Convergence and Stability of a Class of Iteratively Reweighted Least Squares Algorithms for Sparse Signal Recovery in the Presence of Noise\n                      , Technical report, MIT, Cambridge, MA, 2013.","DOI":"10.1109\/TSP.2013.2287685"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb5","unstructured":"A. Beurling,\n                      Sur les inte\u0301grales de Fourier absolument convergentes et leur application a\u0300 une transformation fonctionelle\n                      , in Proceedings of the Scandinavian Mathematical Congress, Helsinki, Finland, 1938."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.916124"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"T. Blumensath, M. Davies, and G. Rilling,\n                      Greedy algorithms for compressed sensing\n                      , in Compressed Sensing: Theory and Applications, Y. Eldar and G. Kutyniok, eds., Cambridge University Press, Cambridge, UK, 2012.","DOI":"10.1017\/CBO9780511794308.009"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/060657704"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9045-x"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01449883"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2007.898300"},{"key":"atypb15","first-page":"3869","author":"Chartrand R.","year":"2008","journal-title":"Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9553-8"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00610-3"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016006"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20042"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20303"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02124742"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/18.382009"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"atypb25","unstructured":"A. Donoho, I. Drori, Y. Tsaig, and J. Starck,\n                      Sparse Solution of Underdetermined Linear Equations by Stagewise Orthogonal Matching Pursuit\n                      , Technical report, Stanford University, Stanford, CA, 2006."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0437847100"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/18.959265"},{"key":"atypb28","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, 2010.","DOI":"10.1007\/978-1-4419-7011-4"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2007.909318"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.09.001"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.828141"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0013-4694(95)00107-A"},{"key":"atypb33","unstructured":"M. Grant and S. Boyd,\n                      CVX: MATLAB Software for Disciplined Convex Programming\n                      , Version 1.21, CVX Research, 2011."},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and J. Friedman,\n                      The Elements of Statistical Learning\n                      , Springer, New York, 2001.","DOI":"10.1007\/978-0-387-21606-5"},{"key":"atypb35","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1080\/03610927708827533","volume":"6","author":"Holland P.","year":"1997","journal-title":"Comm. Statist. Theory Methods"},{"key":"atypb36","unstructured":"X. Huang, Y. Liu, S. Shi, S. Van Huffel, and J. Suykens,\n                      Two-level $\\ell_1$ Minimization for Compressed Sensing\n                      , KU Leuven, Belgium, 2013."},{"key":"atypb37","unstructured":"M. Khajehnejad, W. Xu, A. Avestimehr, and B. Hassibi,\n                      Improved sparse recovery thresholds with two-step reweighted $\\ell_1$ mininimization\n                      , in Proceedings of ISIT, Austin, TX, 2010."},{"key":"atypb38","unstructured":"M. Khajehnejad, W. Xu, A. Avestimehr, and B. Hassibi,\n                      Weighted $\\ell_1$ Mininimization for Sparse Recovery with Prior Information\n                      , arXiv:0901.2912, 2009."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/090775397"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0722-4"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"S. Mallat,\n                      A Wavelet Tour of Signal Processing\n                      , Academic Press, San Diego, CA, 1999.","DOI":"10.1016\/B978-012466606-1\/50008-8"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/78.258082"},{"key":"atypb44","first-page":"175","author":"Mangasarian O. L.","year":"1996","journal-title":"Heidelberg"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/0317052"},{"key":"atypb46","first-page":"113","author":"Needell D.","year":"2009","journal-title":"Systems and Computers"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.07.002"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2010.2042412"},{"key":"atypb49","unstructured":"W. Pennebaker and J. Mitchell,\n                      JPEG Still Image Data Compression Standard\n                      , Van Nostrand Reinhold, New York, 1993."},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"O. Taheri and S. Vorobyov,\n                      Reweighted $\\ell_1$-Norm Penalized LMS for Sparse Channel Esitimation and Its Analysis\n                      , arXiv:1401.3566, 2014.","DOI":"10.1016\/j.sigpro.2014.03.048"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.834793"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864420"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2010.2044010"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"V. Vapnik,\n                      The Nature of Statistical Learning Theory\n                      , Springer-Verlag, New York, 1999.","DOI":"10.1007\/978-1-4757-3264-1"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2004.831016"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2010.2042413"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2281030"},{"key":"atypb59","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\/140968240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:25Z","timestamp":1787340205000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140968240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140968240"],"URL":"https:\/\/doi.org\/10.1137\/140968240","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}