Caillaud, Corentin
[VerfasserIn]
;
Institut polytechnique de Paris
[MitwirkendeR];
Chambolle, Antonin
[MitwirkendeR]
Asymptotical estimates for some algorithms for data and image processing : a study of the Sinkhorn algorithm and a numerical analysis of total variation minimization ; Estimations asymptotiques pour des algorithmes de traitement d'images et de données : une étude de l'algorithme de Sinkhorn et une analyse numérique de la minimisation de la variation totale
Titel:
Asymptotical estimates for some algorithms for data and image processing : a study of the Sinkhorn algorithm and a numerical analysis of total variation minimization ; Estimations asymptotiques pour des algorithmes de traitement d'images et de données : une étude de l'algorithme de Sinkhorn et une analyse numérique de la minimisation de la variation totale
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Cette thèse traite de problèmes discrets d'optimisation convexe et s'intéresse à des estimations de leurs taux de convergence. Elle s'organise en deux parties indépendantes.Dans la première partie, nous étudions le taux de convergence de l'algorithme de Sinkhorn et de certaines de ses variantes. Cet algorithme apparaît dans le cadre du Transport Optimal (TO) par l'intermédiaire d'une régularisation entropique. Ses itérations, comme celles de ses variantes, s'écrivent sous la forme de produits composante par composante de matrices et de vecteurs positifs. Pour les étudier, nous proposons une nouvelle approche basée sur des inégalités de convexité simples et menant au taux de convergence linéaire observé en pratique. Nous étendons ce résultat à un certain type de variantes de l'algorithme que nous appelons algorithmes de Sinkhorn équilibrés de dimension 1. Nous présentons ensuite des techniques numériques traitant le cas de la convergence vers zéro du paramètre de régularisation des problèmes de TO. Enfin, nous menons l'analyse complète du taux de convergence en dimension 2.Dans la deuxième partie, nous donnons des estimations d'erreur pour deux discrétisations de la variation totale (TV) dans le modèle de Rudin, Osher et Fatemi (ROF). Ce problème de débruitage d'image, qui revient à calculer l'opérateur proximal de la variation totale, bénéficie de propriétés d'isotropie assurant la conservation de discontinuités nettes dans les images débruitées, et ce dans toutes les directions. En discrétisant le problème sur un maillage carré de taille h et en utilisant une variation totale discrète standard dite TV isotrope, cette propriété est perdue. Nous démontrons que dans une direction particulière l'erreur sur l'énergie est d'ordre h^{2/3}, ce qui est relativement élevé face aux attentes pour de meilleures discrétisations. Notre preuve repose sur l'analyse d'un problème équivalent en dimension 1 et de la TV perturbée qui y intervient. La deuxième variation totale discrète que nous considérons copie la définition de la ...