Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A total variation diminishing interpolation operator and applications

Authors: Sören Bartels, Ricardo H. Nochetto and Abner J. Salgado
Journal: Math. Comp. 84 (2015), 2569-2587
MSC (2010): Primary 65D05, 49M25, 65K15, 65M60, 65N15, 49J40
Published electronically: March 30, 2015
MathSciNet review: 3378839
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (2003a:49002)
  • [2] 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 (2005c:35002)
  • [3] Gabriele Anzellotti, Pairings between measures and bounded functions and compensated compactness, Ann. Mat. Pura Appl. (4) 135 (1983), 293-318 (1984). MR 750538 (85m:46042),
  • [4] W. Bangerth, R. Hartmann, and G. Kanschat, deal.II differential equations analysis library, technical reference,
  • [5] 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 (2009b:65292),
  • [6] 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,
  • [7] 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,
  • [8] H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert, North-Holland Publishing Co., Amsterdam, 1973 (French). North-Holland Mathematics Studies, No. 5. Notas de Matemática (50). MR 0348562 (50 #1060)
  • [9] 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.
  • [10] 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 (2012b:94004),
  • [11] 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 (2001c:65134),
  • [12] Ph. Clément, Approximation by finite element functions using local regularization, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. RAIRO Analyse Numérique 9 (1975), no. R-2, 77-84. MR 0400739 (53 #4569)
  • [13] 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 (2005d:65187),
  • [14] Todd Dupont and Ridgway Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441-463. MR 559195 (81h:65014),
  • [15] Ricardo G. Durán, On polynomial approximation in Sobolev spaces, SIAM J. Numer. Anal. 20 (1983), no. 5, 985-988. MR 714693 (85e:42010),
  • [16] Ricardo G. Durán and Ariel L. Lombardi, Error estimates on anisotropic $ \mathcal {Q}_1$ elements for functions in weighted Sobolev spaces, Math. Comp. 74 (2005), no. 252, 1679-1706. MR 2164092 (2006e:65216),
  • [17] 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 (2004f:65149),
  • [18] 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 (2006m:65201),
  • [19] 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.
  • [20] 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.
  • [21] 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 (2011h:35149),
  • [22] 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 (2002i:35099)
  • [23] 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 (2012i:35003)
  • [24] 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 (2000m:74071),
  • [25] 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 (2000k:65142),$ \langle $525::AID-CPA1$ \rangle $3.0.CO;2-M
  • [26] Ricardo H. Nochetto and Lars B. Wahlbin, Positivity preserving finite element approximation, Math. Comp. 71 (2002), no. 240, 1405-1419. MR 1933037 (2003i:65110),
  • [27] 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.
  • [28] Jim Rulla, Error analysis for implicit approximations to solutions to Cauchy problems, SIAM J. Numer. Anal. 33 (1996), no. 1, 68-87. MR 1377244 (97c:65151),
  • [29] 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 (90j:65021),
  • [30] S. L. Sobolev, Nekotorye primeneniya funkcionalnogo analiza v matematičeskoĭ fizike, Izdat. Leningrad. Gos. Univ., Leningrad, 1950 (Russian). MR 0052039 (14,565a)
  • [31] Luc Tartar, An Introduction to Sobolev Spaces and Interpolation Spaces, Lecture Notes of the Unione Matematica Italiana, vol. 3, Springer, Berlin, 2007. MR 2328004 (2008g:46055)
  • [32] 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 (2012h:65244),
  • [33] William P. Ziemer, Weakly Differentiable Functions: Sobolev Spaces and Functions of Bounded Variation, Graduate Texts in Mathematics, vol. 120, Springer-Verlag, New York, 1989. MR 1014685 (91e:46046)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D05, 49M25, 65K15, 65M60, 65N15, 49J40

Retrieve articles in all journals with MSC (2010): 65D05, 49M25, 65K15, 65M60, 65N15, 49J40

Additional Information

Sören Bartels
Affiliation: Abteilung für Angewandte Mathematik, Albert-Ludwigs-Universität Freiburg Hermann-Herder-Str. 1079104 Freiburg i.Br., Germany.

Ricardo H. Nochetto
Affiliation: Department of Mathematics and Institute for Physical Science and Technology, University of Maryland, College Park, Maryland 20742

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

Keywords: Total variation, interpolation, approximation, finite elements
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.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society