|
|
Publications sur gradient and subgradient descent
Résultat de la recherche dans la liste des publications :
Rapport de recherche et Rapport technique |
1 - Efficient schemes for total variation minimization under constraints in image processing.
P. Weiss et L. Blanc-Féraud et G. Aubert. Rapport de Recherche 6260, INRIA, juillet 2007.
Mots-clés : l1 norm, total variation minimization, duality lp norms, gradient and subgradient descent, nesterov scheme, texture + geometry decomposition.
@TECHREPORT{RR-6260,
|
| author |
= |
{Weiss, P. and Blanc-Féraud, L. and Aubert, G.}, |
| title |
= |
{Efficient schemes for total variation minimization under constraints in image processing}, |
| year |
= |
{2007}, |
| month |
= |
{juillet}, |
| institution |
= |
{INRIA}, |
| type |
= |
{Research Report}, |
| number |
= |
{6260}, |
| url |
= |
{http://hal.inria.fr/inria-00166096/fr/}, |
| pdf |
= |
{http://hal.inria.fr/docs/00/26/16/35/PDF/RR-6260.pdf}, |
| ps |
= |
{http://hal.inria.fr/docs/00/26/16/35/PS/RR-6260.ps}, |
| keyword |
= |
{l1 norm, total variation minimization, duality lp norms, gradient and subgradient descent, nesterov scheme, texture + geometry decomposition} |
| } |
Résumé :
Ce papier présente de nouveaux algorithmes pour minimiser la variation totale, et plus généralement des normes l^1, sous des contraintes convexes. Ces algorithmes proviennent d'une avancée récente en optimisation convexe proposée par Yurii Nesterov. Suivant la régularité de l'attache aux données, nous résolvons soit un problème primal, soit un problème dual. Premièrement, nous montrons que les schémas standard de premier ordre permettent d'obtenir des solutions de précision epsilon en O(frac1epsilon^2) itérations au pire des cas. Pour une contrainte convexe quelconque, nous proposons un schéma qui permet d'obtenir une solution de précision epsilon en O(frac1epsilon) itérations. Pour une contrainte fortement convexe, nous résolvons un problème dual avec un schéma qui demande O(frac1sqrtepsilon) itérations pour obtenir une solution de précision epsilon. Suivant la contrainte, nous gagnons donc un à deux ordres dans la rapidité de convergence par rapport à des approches standard. Finalement, nous faisons quelques expériences numériques qui confirment les résultats théoriques sur de nombreux problèmes. |
Abstract :
This paper presents new algorithms to minimize total variation and more generally l^1-norms under a general convex constraint. The algorithms are based on a recent advance in convex optimization proposed by Yurii Nesterov citeNESTEROV. Depending on the regularity of the data fidelity term, we solve either a primal problem, either a dual problem. First we show that standard first order schemes allow to get solutions of precision epsilon in O(frac1epsilon^2) iterations at worst. For a general convex constraint, we propose a scheme that allows to obtain a solution of precision epsilon in O(frac1epsilon) iterations. For a strongly convex constraint, we solve a dual problem with a scheme that requires O(frac1sqrtepsilon) iterations to get a solution of precision epsilon. Thus, depending on the regularity of the data term, we gain from one to two orders of magnitude in the convergence rates with respect to standard schemes. Finally we perform some numerical experiments which confirm the theoretical results on various problems. |
|
 haut de la page
Ces pages sont générées par 
|
Rapport d'activité 2011
bibtex
