Efficient schemes for total variation minimization under constraints in image processing

Pierre Weiss 1 Gilles Aubert 2 Laure Blanc-Féraud 1
1 ARIANA - Inverse problems in earth monitoring
CRISAM - Inria Sophia Antipolis - Méditerranée , SIS - Signal, Images et Systè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. 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(\frac{1}{\epsilon^2})$ iterations at worst. For a general convex constraint, we propose a scheme that allows to obtain a solution of precision $\epsilon$ in $O(\frac{1}{\epsilon})$ iterations. For a strongly convex constraint, we solve a dual problem with a scheme that requires $O(\frac{1}{\sqrt{\epsilon}})$ 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.
Type de document :
[Research Report] RR-6260, INRIA. 2007, pp.36
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger

Contributeur : Pierre Weiss <>
Soumis le : vendredi 7 mars 2008 - 17:40:30
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 21:36:56


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00166096, version 3


Pierre Weiss, Gilles Aubert, Laure Blanc-Féraud. Efficient schemes for total variation minimization under constraints in image processing. [Research Report] RR-6260, INRIA. 2007, pp.36. 〈inria-00166096v3〉



Consultations de la notice


Téléchargements de fichiers