Number of the records: 1
A New Computational Method for the Sparsest Solutions to Systems of Linear Equations
- 1.
SYSNO ASEP 0448595 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title A New Computational Method for the Sparsest Solutions to Systems of Linear Equations Author(s) Zhao, Y.-B. (GB)
Kočvara, Michal (UTIA-B) RID, ORCIDNumber of authors 2 Source Title SIAM Journal on Optimization. - : SIAM Society for Industrial and Applied Mathematics - ISSN 1052-6234
Roč. 25, č. 2 (2015), s. 1110-1134Number of pages 25 s. Publication form Print - P Language eng - English Country US - United States Keywords l(0)-minimization ; sparsest solution ; reweighted l(1)-method ; sparsity recovery Subject RIV BA - General Mathematics R&D Projects GAP201/12/0671 GA ČR - Czech Science Foundation (CSF) Institutional support UTIA-B - RVO:67985556 UT WOS 000357406900015 EID SCOPUS 84940396270 DOI https://doi.org/10.1137/140968240 Annotation 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. Workplace Institute of Information Theory and Automation Contact Markéta Votavová, votavova@utia.cas.cz, Tel.: 266 052 201. Year of Publishing 2016
Number of the records: 1