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
Additional Information
- Sören Bartels
- Affiliation: Abteilung für Angewandte Mathematik, Albert-Ludwigs-Universität Freiburg Hermann-Herder-Str. 1079104 Freiburg i.Br., Germany.
- Email: bartels@mathematik.uni-freiburg.de
- Ricardo H. Nochetto
- Affiliation: Department of Mathematics and Institute for Physical Science and Technology, University of Maryland, College Park, Maryland 20742
- MR Author ID: 131850
- Email: rhn@math.umd.edu
- Abner J. Salgado
- Affiliation: Department of Mathematics, University of Maryland, College Park, Maryland 20742
- Address at time of publication: Department of Mathematics, University of Tennessee, Knoxville, Tennessee 37996
- Email: asalgad1@utk.edu
- Received by editor(s): November 5, 2012
- Received by editor(s) in revised form: July 10, 2013, and February 12, 2014
- Published electronically: March 30, 2015
- Additional Notes: This work was partially supported by NSF grants DMS-0807811 and DMS-1109325. The third author was also partially supported by an AMS-Simons grant.
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 2569-2587
- MSC (2010): Primary 65D05, 49M25, 65K15, 65M60, 65N15, 49J40
- DOI: https://doi.org/10.1090/mcom/2942
- MathSciNet review: 3378839