A total variation diminishing interpolation operator and applications

Bartels, Sören; Nochetto, Ricardo; Salgado, Abner

doi:10.1090/mcom/2942

A total variation diminishing interpolation operator and applications
HTML articles powered by AMS MathViewer

by Sören Bartels, Ricardo H. Nochetto and Abner J. Salgado PDF

Math. Comp. 84 (2015), 2569-2587 Request permission

Abstract:

We construct an interpolation operator that does not increase the total variation and is defined on continuous first degree finite elements over Cartesian meshes for any dimension $d$ and right triangular meshes for $d = 2$. The operator is stable and exhibits second order approximation properties in any $L^p$, $1\leq p \leq \infty$. With the help of it we provide improved error estimates for discrete minimizers of the total variation denoising problem and for total variation flows. We also explore computationally the limitations of the total variation diminishing property over non-Cartesian meshes.

References

Luigi Ambrosio, Nicola Fusco, and Diego Pallara, Functions of bounded variation and free discontinuity problems, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 2000. MR 1857292
Fuensanta Andreu-Vaillo, Vicent Caselles, and José M. Mazón, Parabolic quasilinear equations minimizing linear growth functionals, Progress in Mathematics, vol. 223, Birkhäuser Verlag, Basel, 2004. MR 2033382, DOI 10.1007/978-3-0348-7928-6
Gabriele Anzellotti, Pairings between measures and bounded functions and compensated compactness, Ann. Mat. Pura Appl. (4) 135 (1983), 293–318 (1984). MR 750538, DOI 10.1007/BF01781073
W. Bangerth, R. Hartmann, and G. Kanschat, deal.II differential equations analysis library, technical reference, http://www.dealii.org.
W. Bangerth, R. Hartmann, and G. Kanschat, deal.II—a general-purpose object-oriented finite element library, ACM Trans. Math. Software 33 (2007), no. 4, Art. 24, 27. MR 2404402, DOI 10.1145/1268776.1268779
Sören Bartels, Total variation minimization with finite elements: convergence and iterative solution, SIAM J. Numer. Anal. 50 (2012), no. 3, 1162–1180. MR 2970738, DOI 10.1137/11083277X
Sören Bartels, Ricardo H. Nochetto, and Abner J. Salgado, Discrete total variation flows without regularization, SIAM J. Numer. Anal. 52 (2014), no. 1, 363–385. MR 3163248, DOI 10.1137/120901544
H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert, North-Holland Mathematics Studies, No. 5, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973 (French). MR 0348562
A. Chambolle, Total variation minimization and a class of binary MRF models, Energy Minimization Methods in Computer Vision and Pattern Recognition (A. Rangarajan, B. Vemuri, and A.L. Yuille, eds.), Lecture Notes in Computer Science, vol. 3757, Springer, Berlin, Heidelberg, 2005, pp. 136–152.
Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), no. 1, 120–145. MR 2782122, DOI 10.1007/s10851-010-0251-1
Zhiming Chen and Ricardo H. Nochetto, Residual type a posteriori error estimates for elliptic obstacle problems, Numer. Math. 84 (2000), no. 4, 527–548. MR 1742264, DOI 10.1007/s002110050009
Ph. Clément, Approximation by finite element functions using local regularization, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. 9 (1975), no. R-2, 77–84 (English, with Loose French summary). MR 0400739
W. Dahmen, B. Faermann, I. G. Graham, W. Hackbusch, and S. A. Sauter, Inverse inequalities on non-quasi-uniform meshes and application to the mortar element method, Math. Comp. 73 (2004), no. 247, 1107–1138. MR 2047080, DOI 10.1090/S0025-5718-03-01583-7
Todd Dupont and Ridgway Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441–463. MR 559195, DOI 10.1090/S0025-5718-1980-0559195-7
Ricardo G. Durán, On polynomial approximation in Sobolev spaces, SIAM J. Numer. Anal. 20 (1983), no. 5, 985–988. MR 714693, DOI 10.1137/0720068
Ricardo G. Durán and Ariel L. Lombardi, Error estimates on anisotropic $\scr Q_1$ elements for functions in weighted Sobolev spaces, Math. Comp. 74 (2005), no. 252, 1679–1706. MR 2164092, DOI 10.1090/S0025-5718-05-01732-1
Xiaobing Feng and Andreas Prohl, Analysis of total variation flow and its finite element approximations, M2AN Math. Model. Numer. Anal. 37 (2003), no. 3, 533–556. MR 1994316, DOI 10.1051/m2an:2003041
Xiaobing Feng, Markus von Oehsen, and Andreas Prohl, Rate of convergence of regularization procedures and finite element approximations for the total variation flow, Numer. Math. 100 (2005), no. 3, 441–456. MR 2194526, DOI 10.1007/s00211-005-0585-6
P.-W. Fok, R.R. Rosales, and D. Margetis, Facet evolution on supported nanostructures: Effect of finite height, Phys. Rev. B 78 (2008), 235–401.
E.S. Fu, D.-J. Liu, M.D. Johnson, J.D. Weeks, and E.D. Williams, The effective charge in surface electromigration, Surface Science 385 (1997), no. 2–3, 259 – 269.
Mi-Ho Giga and Yoshikazu Giga, Very singular diffusion equations: second and fourth order problems, Jpn. J. Ind. Appl. Math. 27 (2010), no. 3, 323–345. MR 2746654, DOI 10.1007/s13160-010-0020-y
Mi-Ho Giga, Yoshikazu Giga, and Ryo Kobayashi, Very singular diffusion equations, Taniguchi Conference on Mathematics Nara ’98, Adv. Stud. Pure Math., vol. 31, Math. Soc. Japan, Tokyo, 2001, pp. 93–125. MR 1865089, DOI 10.2969/aspm/03110093
Helge Holden and Nils Henrik Risebro, Front tracking for hyperbolic conservation laws, Applied Mathematical Sciences, vol. 152, Springer, New York, 2011. First softcover corrected printing of the 2002 original. MR 2866066, DOI 10.1007/978-3-642-23911-3
Ryo Kobayashi, James A. Warren, and W. Craig Carter, A continuum model of grain boundaries, Phys. D 140 (2000), no. 1-2, 141–150. MR 1752970, DOI 10.1016/S0167-2789(00)00023-3
Ricardo H. Nochetto, Giuseppe Savaré, and Claudio Verdi, A posteriori error estimates for variable time-step discretizations of nonlinear evolution equations, Comm. Pure Appl. Math. 53 (2000), no. 5, 525–589. MR 1737503, DOI 10.1002/(SICI)1097-0312(200005)53:5<525::AID-CPA1>3.0.CO;2-M
Ricardo H. Nochetto and Lars B. Wahlbin, Positivity preserving finite element approximation, Math. Comp. 71 (2002), no. 240, 1405–1419. MR 1933037, DOI 10.1090/S0025-5718-01-01369-2
L.I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena 60 (1992), no. 1–4, 259–268.
Jim Rulla, Error analysis for implicit approximations to solutions to Cauchy problems, SIAM J. Numer. Anal. 33 (1996), no. 1, 68–87. MR 1377244, DOI 10.1137/0733005
L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483–493. MR 1011446, DOI 10.1090/S0025-5718-1990-1011446-7
S. L. Sobolev, Nekotorye primeneniya funkcional′nogo analiza v matematičeskoĭ fizike, Izdat. Leningrad. Gos. Univ., Leningrad, 1950 (Russian). MR 0052039
Luc Tartar, An introduction to Sobolev spaces and interpolation spaces, Lecture Notes of the Unione Matematica Italiana, vol. 3, Springer, Berlin; UMI, Bologna, 2007. MR 2328004
Jingyue Wang and Bradley J. Lucier, Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing, SIAM J. Numer. Anal. 49 (2011), no. 2, 845–868. MR 2792398, DOI 10.1137/090769594
William P. Ziemer, Weakly differentiable functions, Graduate Texts in Mathematics, vol. 120, Springer-Verlag, New York, 1989. Sobolev spaces and functions of bounded variation. MR 1014685, DOI 10.1007/978-1-4612-1015-3