Analysis of total variation flow and its finite element approximations
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 37 (2003) no. 3, p. 533-556

We study the gradient flow for the total variation functional, which arises in image processing and geometric applications. We propose a variational inequality weak formulation for the gradient flow, and establish well-posedness of the problem by the energy method. The main idea of our approach is to exploit the relationship between the regularized gradient flow (characterized by a small positive parameter $\epsilon$, and the minimal surface flow [21] and the prescribed mean curvature flow [16]. Since our approach is constructive and variational, finite element methods can be naturally applied to approximate weak solutions of the limiting gradient flow problem. We propose a fully discrete finite element method and establish convergence to the regularized gradient flow problem as $h,k\to 0$, and to the total variation gradient flow problem as $h,k,\epsilon \to 0$ in general cases. Provided that the regularized gradient flow problem possesses strong solutions, which is proved possible if the datum functions are regular enough, we establish practical a priori error estimates for the fully discrete finite element solution, in particular, by focusing on the dependence of the error bounds on the regularization parameter $\epsilon$. Optimal order error bounds are derived for the numerical solution under the mesh relation $k=O\left({h}^{2}\right)$. In particular, it is shown that all error bounds depend on $\frac{1}{\epsilon }$ only in some lower polynomial order for small $\epsilon$.

DOI : https://doi.org/10.1051/m2an:2003041
Classification:  35B25,  35K57,  35Q99,  65M60,  65M12
Keywords: bounded variation, gradient flow, variational inequality, equations of prescribed mean curvature and minimal surface, fully discrete scheme, finite element method
@article{M2AN_2003__37_3_533_0,
author = {Feng, Xiaobing and Prohl, Andreas},
title = {Analysis of total variation flow and its finite element approximations},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
publisher = {EDP-Sciences},
volume = {37},
number = {3},
year = {2003},
pages = {533-556},
doi = {10.1051/m2an:2003041},
zbl = {1050.35004},
mrnumber = {1994316},
language = {en},
url = {http://www.numdam.org/item/M2AN_2003__37_3_533_0}
}

Feng, Xiaobing; Prohl, Andreas. Analysis of total variation flow and its finite element approximations. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 37 (2003) no. 3, pp. 533-556. doi : 10.1051/m2an:2003041. http://www.numdam.org/item/M2AN_2003__37_3_533_0/

[1] L. Ambrosio, N. Fusco and D. Pallara, Functions of bounded variation and free discontinuity problems. The Clarendon Press Oxford University Press, New York (2000). | MR 1857292 | Zbl 0957.49001

[2] F. Andreu, C. Ballester, V. Caselles and J.M. Mazón, The Dirichlet problem for the total variation flow. J. Funct. Anal. 180 (2001) 347-403. | Zbl 0973.35109

[3] F. Andreu, C. Ballester, V. Caselles and J.M. Mazón, Minimizing total variation flow. Differential Integral Equations 14 (2001) 321-360. | Zbl 1020.35037

[4] F. Andreu, V. Caselles, J.I. Díaz and J.M. Mazón, Some qualitative properties for the total variation flow. J. Funct. Anal. 188 (2002) 516-547. | Zbl 1042.35018

[5] G. Bellettini and V. Caselles, The total variation flow in ${𝐑}^{N}$. J. Differential Equations (accepted). | Zbl 1036.35099

[6] S.C. Brenner and L.R. Scott, The mathematical theory of finite element methods. Springer-Verlag, New York, 2nd ed. (2002). | MR 1894376 | Zbl 0804.65101

[7] H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. North-Holland Publishing Co., Amsterdam, North-Holland Math. Stud., No. 5. Notas de Matemática (50) (1973). | MR 348562 | Zbl 0252.47055

[8] E. Casas, K. Kunisch and C. Pola, Regularization by functions of bounded variation and applications to image enhancement. Appl. Math. Optim. 40 (1999) 229-257. | Zbl 0942.49014

[9] A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems. Numer. Math. 76 (1997) 167-188. | Zbl 0874.68299

[10] T. Chan and J. Shen, On the role of the BV image model in image restoration. Tech. Report CAM 02-14, Department of Mathematics, UCLA (2002). | MR 2011710 | Zbl 1035.94501

[11] T.F. Chan, G.H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20 (1999) 1964-1977 (electronic). | Zbl 0929.68118

[12] P.G. Ciarlet, The finite element method for elliptic problems. North-Holland Publishing Co., Amsterdam, Stud. Math. Appl. 4 (1978). | MR 520174 | Zbl 0383.65058

[13] M.G. Crandall and T.M. Liggett, Generation of semi-groups of nonlinear transformations on general Banach spaces. Amer. J. Math. 93 (1971) 265-298. | Zbl 0226.47038

[14] D.C. Dobson and C.R. Vogel, Convergence of an iterative method for total variation denoising. SIAM J. Numer. Anal. 34 (1997) 1779-1791. | Zbl 0898.65034

[15] C. Gerhardt, Boundary value problems for surfaces of prescribed mean curvature. J. Math. Pures Appl. 58 (1979) 75-109. | Zbl 0413.35024

[16] C. Gerhardt, Evolutionary surfaces of prescribed mean curvature. J. Differential Equations 36 (1980) 139-172. | Zbl 0485.35053

[17] D. Gilbarg and N.S. Trudinger, Elliptic partial differential equations of second order. Springer-Verlag, Berlin (2001). Reprint of the 1998 ed. | MR 1814364 | Zbl 1042.35002

[18] E. Giusti, Minimal surfaces and functions of bounded variation. Birkhäuser Verlag, Basel (1984). | MR 775682 | Zbl 0545.49018

[19] R. Hardt and X. Zhou, An evolution problem for linear growth functionals. Comm. Partial Differential Equations 19 (1994) 1879-1907. | Zbl 0811.35061

[20] C. Johnson and V. Thomée, Error estimates for a finite element approximation of a minimal surface. Math. Comp. 29 (1975) 343-349. | Zbl 0302.65086

[21] A. Lichnewsky and R. Temam, Pseudosolutions of the time-dependent minimal surface problem. J. Differential Equations 30 (1978) 340-364. | Zbl 0368.49016

[22] J.-L. Lions, Quelques méthodes de résolution des problèmes aux limites non linéaires. Dunod (1969). | MR 259693 | Zbl 0189.40603

[23] R. Rannacher, Some asymptotic error estimates for finite element approximation of minimal surfaces. RAIRO Anal. Numér. 11 (1977) 181-196. | Numdam | Zbl 0356.35034

[24] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms. Phys. D 60 (1992) 259-268. | Zbl 0780.49028

[25] J. Simon, Compact sets in the space ${L}^{p}\left(0,T;B\right)$. Ann. Mat. Pura Appl. 146 (1987) 65-96. | Zbl 0629.46031

[26] M. Struwe, Applications to nonlinear partial differential equations and Hamiltonian systems, in Variational methods. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics (Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics), Vol. 34. Springer-Verlag, Berlin, 3rd ed. (2000). | MR 1736116 | Zbl 0939.49001