A New Computational Method for the Sparsest Solutions to Systems of Linear Equations

0448595 - ÚTIA 2016 RIV US eng J - Journal Article
Zhao, Y.-B. - Kočvara, Michal
A New Computational Method for the Sparsest Solutions to Systems of Linear Equations.
SIAM Journal on Optimization. Roč. 25, č. 2 (2015), s. 1110-1134. ISSN 1052-6234. E-ISSN 1095-7189
R&D Projects: GA ČR(CZ) GAP201/12/0671
Grant - others:EPSRC(GB) EP/K00946X/1
Institutional support: RVO:67985556
Keywords : l(0)-minimization * sparsest solution * reweighted l(1)-method * sparsity recovery
Subject RIV: BA - General Mathematics
Impact factor: 2.659, year: 2015
http://library.utia.cas.cz/separaty/2015/MTR/kocvara-0448595.pdf

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.
Permanent Link: http://hdl.handle.net/11104/0250574