Stability and experimental comparison of prototypical iterative schemes for total variation regularized problems. (English) Zbl 1342.65152
Summary: Various iterative methods are available for the approximate solution of non-smooth minimization problems. For a popular non-smooth minimization problem arising in image processing, we discuss the suitable application of three prototypical methods and their stability. The methods are compared experimentally with a focus on choice of stopping criteria, influence of rough initial data, step sizes as well as mesh sizes. An overview of existing algorithms is given.
MSC:
| 65K15 | Numerical methods for variational inequalities and related problems |
| 49M29 | Numerical methods involving duality |
Software:
RecPFReferences:
| [1] | Acerbi E. and Fusco N., Semicontinuity problems in the calculus of variations, Arch. Ration. Mech. Anal. 86 (1984), no. 2, 125-145.; Acerbi, E.; Fusco, N., Semicontinuity problems in the calculus of variations, Arch. Ration. Mech. Anal., 86, 2, 125-145 (1984) · Zbl 0565.49010 |
| [2] | Ambrosio L. and Dal Maso G., On the relaxation in \({BV(\Omega;\mathbb{R}^m)}\) of quasi-convex integrals, J. Funct. Anal. 109 (1992), 76-97.; Ambrosio, L.; Dal Maso, G., On the relaxation in \({BV(\Omega;\mathbb{R}^m)}\) of quasi-convex integrals, J. Funct. Anal., 109, 76-97 (1992) · Zbl 0769.49009 |
| [3] | Ambrosio L., Fusco N. and Pallara D., Functions of Bounded Variation and Free Discontinuity Problems, Oxford Math. Monogr., Clarendon Press, Oxford, 2000.; Ambrosio, L.; Fusco, N.; Pallara, D., Functions of Bounded Variation and Free Discontinuity Problems (2000) · Zbl 0957.49001 |
| [4] | Ambrosio L., Mortola S. and Tortorelli V. M., Functionals with linear growth defined on vector valued BV functions, J. Math. Pures Appl. (9) 70 (1991), 269-323.; Ambrosio, L.; Mortola, S.; Tortorelli, V. M., Functionals with linear growth defined on vector valued BV functions, J. Math. Pures Appl. (9), 70, 269-323 (1991) · Zbl 0662.49007 |
| [5] | Andreu-Vaillo F., Caselles V. and Mazón J. M., Parabolic Quasilinear Equations Minimizing Linear Growth Functionals, Progr. Math. 223, Birkhäuser, Basel, 2004.; Andreu-Vaillo, F.; Caselles, V.; Mazón, J. M., Parabolic Quasilinear Equations Minimizing Linear Growth Functionals (2004) · Zbl 1053.35002 |
| [6] | Attouch H., Buttazzo G. and Michaille G., Variational Analysis in Sobolev and BV Spaces, MPS/SIAM Ser. Optim. 6, Mathematical Programming Society, Philadelphia, 2006.; Attouch, H.; Buttazzo, G.; Michaille, G., Variational Analysis in Sobolev and BV Spaces (2006) · Zbl 1095.49001 |
| [7] | Bartels S., Total variation minimization with finite elements: Convergence and iterative solution, SIAM J. Numer. Anal. 50 (2012), 1162-1180.; Bartels, S., Total variation minimization with finite elements: Convergence and iterative solution, SIAM J. Numer. Anal., 50, 1162-1180 (2012) · Zbl 1257.65067 |
| [8] | Bartels S., Broken Sobolev space iteration for total variation regularized minimization problems, IMA J. Numer. Anal. (2015), 10.1093/imanum/drv023.; Bartels, S., Broken Sobolev space iteration for total variation regularized minimization problems, IMA J. Numer. Anal. (2015) · Zbl 1433.94010 · doi:10.1093/imanum/drv023 |
| [9] | Bartels S., Numerical Methods for Nonlinear Partial Differential Equations, Springer, Heidelberg, 2015.; Bartels, S., Numerical Methods for Nonlinear Partial Differential Equations (2015) · Zbl 1314.65003 |
| [10] | Bartels S., Mielke A. and Roubiček T., Quasi-static small-strain plasticity in the limit of vanishing Hardening and its numerical approximation, SIAM J. Numer. Anal. 50 (2012), no. 2, 951-976.; Bartels, S.; Mielke, A.; Roubiček, T., Quasi-static small-strain plasticity in the limit of vanishing Hardening and its numerical approximation, SIAM J. Numer. Anal., 50, 2, 951-976 (2012) · Zbl 1248.35105 |
| [11] | Bartels S., Nochetto R. H. and Salgado A. J., Discrete total variation flows without regularization, SIAM J. Numer. Anal. 52 (2014), 363-385.; Bartels, S.; Nochetto, R. H.; Salgado, A. J., Discrete total variation flows without regularization, SIAM J. Numer. Anal., 52, 363-385 (2014) · Zbl 1292.65106 |
| [12] | Beck A. and Teboulle M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183-202.; Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009 |
| [13] | Benamou J.-D. and Carlier G., Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations, J. Optim. Theory Appl. 167 (2015), 1-26.; Benamou, J.-D.; Carlier, G., Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations, J. Optim. Theory Appl., 167, 1-26 (2015) · Zbl 1326.49074 |
| [14] | Bewersdorff J., Algebra für Einsteiger, 5th ed., Springer, Heidelberg, 2013.; Bewersdorff, J., Algebra für Einsteiger (2013) · Zbl 1388.12001 |
| [15] | Bildhauer M. and Fuchs M., Convex variational problems with linear growth, Geometric Analysis and Nonlinear Partial Differential Equations, Springer, Berlin (2003), 327-344.; Bildhauer, M.; Fuchs, M., Convex variational problems with linear growth, Geometric Analysis and Nonlinear Partial Differential Equations, 327-344 (2003) · Zbl 1046.35020 |
| [16] | Bildhauer M. and Fuchs M., A variational approach to the denoising of images based on different variants of the TV-regularization, Appl. Math. Optim. 66 (2012), 331-361.; Bildhauer, M.; Fuchs, M., A variational approach to the denoising of images based on different variants of the TV-regularization, Appl. Math. Optim., 66, 331-361 (2012) · Zbl 1260.49074 |
| [17] | Bregman L. M., The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys. 7 (1967), 200-217.; Bregman, L. M., The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys., 7, 200-217 (1967) · Zbl 0186.23807 |
| [18] | Chambolle A., An algorithm for total variation minimization and applications, J. Math. Imaging Vision 20 (2004), 89-97.; Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20, 89-97 (2004) · Zbl 1366.94048 |
| [19] | Chambolle A. and Lions P.-L., Image recovery via total variation minimization and related problems, Numer. Math. 76 (1997), 167-188.; Chambolle, A.; Lions, P.-L., Image recovery via total variation minimization and related problems, Numer. Math., 76, 167-188 (1997) · Zbl 0874.68299 |
| [20] | Chambolle A. and Pock T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), 120-145.; Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40, 120-145 (2011) · Zbl 1255.68217 |
| [21] | Chambolle A. and Pock T., A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions, SIAM J. Comput. Math. 1 (2015), 29-54.; Chambolle, A.; Pock, T., A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions, SIAM J. Comput. Math., 1, 29-54 (2015) · Zbl 1416.65170 |
| [22] | Chan R. H. and Liang H.-X., Half-quadratic algorithm for \(\ell_p- \ell_q\) problems with applications to TV-\( \ell_1\) image restoration and compressive sensing, Efficient Algorithms for Global Optimization Methods in Computer Vision, Lecture Notes in Comput. Sci. 8293, Springer, Berlin (2014), 78-103.; Chan, R. H.; Liang, H.-X., Half-quadratic algorithm for \(\ell_p- \ell_q\) problems with applications to TV-\( \ell_1\) image restoration and compressive sensing, Efficient Algorithms for Global Optimization Methods in Computer Vision, 78-103 (2014) |
| [23] | Chan T. F., Golub G. H. and Mulet P., A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput. 20 (1999), 1964-1977.; Chan, T. F.; Golub, G. H.; Mulet, P., A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20, 1964-1977 (1999) · Zbl 0929.68118 |
| [24] | Chan T. F. and Mulet P., On the convergence of the lagged diffusivity fixed point method in total variation image restoration, SIAM J. Numer. Anal. 36 (1999), 354-367.; Chan, T. F.; Mulet, P., On the convergence of the lagged diffusivity fixed point method in total variation image restoration, SIAM J. Numer. Anal., 36, 354-367 (1999) · Zbl 0923.65037 |
| [25] | Clason C. and Kunisch K., A duality-based approach to elliptic control problems in non-reflexive Banach spaces, ESAIM Control Optim. Calc. Var. 17 (2011), 243-266.; Clason, C.; Kunisch, K., A duality-based approach to elliptic control problems in non-reflexive Banach spaces, ESAIM Control Optim. Calc. Var., 17, 243-266 (2011) · Zbl 1213.49041 |
| [26] | Conti S., Ginster J. and Rumpf M., A BV functional and its relaxation for joint motion estimation and image sequence recovery, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 5, 1463-1487.; Conti, S.; Ginster, J.; Rumpf, M., A BV functional and its relaxation for joint motion estimation and image sequence recovery, ESAIM Math. Model. Numer. Anal., 49, 5, 1463-1487 (2015) · Zbl 1326.49019 |
| [27] | Dal Maso G., DeSimone A. and Mora M. G., Quasistatic evolution problems for linearly elastic-perfectly plastic materials, Arch. Ration. Mech. Anal. 180 (2006), 237-291.; Dal Maso, G.; DeSimone, A.; Mora, M. G., Quasistatic evolution problems for linearly elastic-perfectly plastic materials, Arch. Ration. Mech. Anal., 180, 237-291 (2006) · Zbl 1093.74007 |
| [28] | Darbon J. and Sigelle M., A fast and exact algorithm for total variation minimization, Pattern Recognition and Image Analysis, Lecture Notes in Comput. Sci., Springer, Berlin (2005), 351-359.; Darbon, J.; Sigelle, M., A fast and exact algorithm for total variation minimization, Pattern Recognition and Image Analysis, 351-359 (2005) · Zbl 1478.94026 |
| [29] | Dobson D. C. and Vogel C. R., Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal. 34 (1997), no. 5, 1779-1791.; Dobson, D. C.; Vogel, C. R., Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal., 34, 5, 1779-1791 (1997) · Zbl 0898.65034 |
| [30] | Eckstein J. and Bertsekas D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program. 55 (1992), 293-318.; Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073 |
| [31] | Ekeland I. and Témam R., Convex Analysis and Variational Problems, Classics Appl. Math. 28, Society for Industrial and Applied Mathematics, Philadelphia, 1999.; Ekeland, I.; Témam, R., Convex Analysis and Variational Problems (1999) · Zbl 0939.49002 |
| [32] | Elliott C. M. and Smitheman S. A., Numerical analysis of the tv regularization and \({H^{-1}}\) fidelity model for decomposing an image into cartoon plus texture, IMA J. Numer. Anal. 29 (2009), 651-689.; Elliott, C. M.; Smitheman, S. A., Numerical analysis of the tv regularization and \({H^{-1}}\) fidelity model for decomposing an image into cartoon plus texture, IMA J. Numer. Anal., 29, 651-689 (2009) · Zbl 1169.94003 |
| [33] | Feng X. and Prohl A., Analysis of total variation flow and its finite element approximations, ESAIM Math. Model. Numer. Anal. 37 (2003), 533-556.; Feng, X.; Prohl, A., Analysis of total variation flow and its finite element approximations, ESAIM Math. Model. Numer. Anal., 37, 533-556 (2003) · Zbl 1050.35004 |
| [34] | Fortin M. and Glowinski R., Augmented Lagrangian Methods, Stud. Math. Appl. 15, North-Holland, Amsterdam, 1983.; Fortin, M.; Glowinski, R., Augmented Lagrangian Methods (1983) · Zbl 0525.65045 |
| [35] | Glowinski R. and Le Tallec P., Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989.; Glowinski, R.; Le Tallec, P., Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics (1989) · Zbl 0698.73001 |
| [36] | Goldfarb D. and Yin W., Second-order cone programming methods for total variation-based image restoration, SIAM J. Sci. Comput. 27 (2005), 622-645.; Goldfarb, D.; Yin, W., Second-order cone programming methods for total variation-based image restoration, SIAM J. Sci. Comput., 27, 622-645 (2005) · Zbl 1094.68108 |
| [37] | Goldstein T., O’Donoghue B., Setzer S. and Baraniuk R., Fast alternating direction optimization methods, SIAM J. Imaging Sci. 7 (2014), 1588-1623.; Goldstein, T.; O’Donoghue, B.; Setzer, S.; Baraniuk, R., Fast alternating direction optimization methods, SIAM J. Imaging Sci., 7, 1588-1623 (2014) · Zbl 1314.49019 |
| [38] | Goldstein T. and Osher S., The split Bregman method for L1 regularized problems, SIAM J. Imaging Sci. 2 (2009), 323-343.; Goldstein, T.; Osher, S., The split Bregman method for L1 regularized problems, SIAM J. Imaging Sci., 2, 323-343 (2009) · Zbl 1177.65088 |
| [39] | Güler O., Foundations of Optimization, Grad. Texts in Math. 258, Springer, New York, 2010.; Güler, O., Foundations of Optimization (2010) · Zbl 1220.90001 |
| [40] | Hintermüller M., Ito K. and Kunisch K., The primal-dual active set strategy as a semismooth newton method, SIAM J. Optim. 13 (2003), 865-888.; Hintermüller, M.; Ito, K.; Kunisch, K., The primal-dual active set strategy as a semismooth newton method, SIAM J. Optim., 13, 865-888 (2003) · Zbl 1080.90074 |
| [41] | Hintermüller M. and Kunisch K., Total bounded variation regularization as a bilaterally constrained optimization method, SIAM J. Appl. Math. 64 (2004), 1311-1333.; Hintermüller, M.; Kunisch, K., Total bounded variation regularization as a bilaterally constrained optimization method, SIAM J. Appl. Math., 64, 1311-1333 (2004) · Zbl 1055.94504 |
| [42] | Nesterov Y., Smooth minimization of non-smooth functions, Math. Program. 103 (2005), 127-152.; Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 127-152 (2005) · Zbl 1079.90102 |
| [43] | Papadakis N., Peyré G. and Oudet E., Optimal transport with proximal splitting, SIAM J. Imaging Sci. 7 (2014), 212-238.; Papadakis, N.; Peyré, G.; Oudet, E., Optimal transport with proximal splitting, SIAM J. Imaging Sci., 7, 212-238 (2014) · Zbl 1295.90047 |
| [44] | Rockafellar R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976), 877-898.; Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898 (1976) · Zbl 0358.90053 |
| [45] | Rudin L. I., Osher S. and Fatemi E., Nonlinear total variation based noise removal algorithms, Phys. D 60 (1992), 259-268.; Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D, 60, 259-268 (1992) · Zbl 0780.49028 |
| [46] | Thomas M., Quasistatic damage evolution with spatial BV-regularization, Discrete Contin. Dyn. Syst. Ser. S 6 (2013), 235-255.; Thomas, M., Quasistatic damage evolution with spatial BV-regularization, Discrete Contin. Dyn. Syst. Ser. S, 6, 235-255 (2013) · Zbl 1375.74009 |
| [47] | Tseng P., Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optim. 29 (1991), 119-138.; Tseng, P., Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optim., 29, 119-138 (1991) · Zbl 0737.90048 |
| [48] | Vogel C. R. and Oman M. E., Iterative methods for total variation denoising, SIAM J. Sci. Comput. 17 (1996), 227-238.; Vogel, C. R.; Oman, M. E., Iterative methods for total variation denoising, SIAM J. Sci. Comput., 17, 227-238 (1996) · Zbl 0847.65083 |
| [49] | Wang J. and Lucier B. J., Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing, SIAM J. Numer. Anal. 49 (2011), 845-868.; Wang, J.; Lucier, B. J., Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing, SIAM J. Numer. Anal., 49, 845-868 (2011) · Zbl 1339.94013 |
| [50] | Wang Y., Yang J., Yin W. and Zhang Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci. 1 (2008), 248-272.; Wang, Y.; Yang, J.; Yin, W.; Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1, 248-272 (2008) · Zbl 1187.68665 |
| [51] | Wu C. and Tai X.-C., Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and higher order models, SIAM J. Imaging Sci. 3 (2010), 300-339.; Wu, C.; Tai, X.-C., Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and higher order models, SIAM J. Imaging Sci., 3, 300-339 (2010) · Zbl 1206.90245 |
| [52] | Zhu M., Fast numerical algorithms for total variation based image restoration, Ph.D. thesis, University of California, Los Angeles, 2008.; Zhu, M., Fast numerical algorithms for total variation based image restoration (2008) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
