A New Computational Method for the Sparsest Solutions to Systems of Linear Equations
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F15%3A00448595" target="_blank" >RIV/67985556:_____/15:00448595 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1137/140968240" target="_blank" >http://dx.doi.org/10.1137/140968240</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/140968240" target="_blank" >10.1137/140968240</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A New Computational Method for the Sparsest Solutions to Systems of Linear Equations
Popis výsledku v původním jazyce
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 sparses
Název v anglickém jazyce
A New Computational Method for the Sparsest Solutions to Systems of Linear Equations
Popis výsledku anglicky
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 sparses
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GAP201%2F12%2F0671" target="_blank" >GAP201/12/0671: Variační a numerická analýza v nehladké mechanice kontinua</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Optimization
ISSN
1052-6234
e-ISSN
—
Svazek periodika
25
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
25
Strana od-do
1110-1134
Kód UT WoS článku
000357406900015
EID výsledku v databázi Scopus
2-s2.0-84940396270