0448595 20240103210839.420151022235959.9 000357406900015 84940396270 10.1137/140968240 25 s. P cav_un_epca*02550731052-6234252 (2015)1110-1134SIAM Society for Industrial and Applied Mathematics l(0)-minimization sparsest solution reweighted l(1)-method sparsity recovery cav_un_auth*0320844 Zhao Y.-B. GB cav_un_auth*0101131 Kočvara Michal Matematická teorie rozhodování Department of Decision Making Theory MTR MTR UTIA-B Department of Decision Making Theory 50 Ústav teorie informace a automatizace AV ČR, v. v. i. http://library.utia.cas.cz/separaty/2015/MTR/kocvara-0448595.pdf GAP201/12/0671 GA ČR CZ cav_un_auth*0289475 EP/K00946X/1 EPSRC GB cav_un_auth*0320649 The connection between the sparsest solution to an underdetermined system of linear equations and the weighted l(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 l(1)-minimization with all possible choices of nonnegative weights. Motivated by this fact, a new reweighted l(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 l(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. 2016 BA 2 RVO:67985556 http://hdl.handle.net/11104/0250574 S MATHEMATICS.APPLIED 3.463 0.276 999.9 0.01727 2.751 5274 3.235 Q1 2.216 105 Q1 99.125 97.4 Q1* Q1* 97.441 2015 84940396270 SCOPUS 000357406900015 WOS cav_un_epca*0255073 SIAM Journal on Optimization 1052-6234 1095-7189 Roč. 25 č. 2 2015 1110 1134 SIAM Society for Industrial and Applied Mathematics