A finite element approach for the dual Rudin-Osher-Fatemi model and its nonoverlapping domain decomposition methods. (English) Zbl 1412.65220
Summary: We consider a finite element discretization for the dual Rudin-Osher-Fatemi model [L. I. Rudin et al., Physica D 60, No. 1–4, 259–268 (1992; Zbl 0780.49028)] using a Raviart-Thomas basis for \(H_0 (\mathrm{div} ; \Omega)\). Since the proposed discretization has a splitting property for the energy functional, which is not satisfied for existing finite difference-based discretizations, it is more adequate for designing domain decomposition methods. In this paper, a primal domain decomposition method is proposed which resembles the classical Schur complement method for the second order elliptic problems, and it achieves \(O(1/n^2)\) convergence. A primal-dual domain decomposition method based on the method of Lagrange multipliers on the subdomain interfaces is also considered. Local problems of the proposed primal-dual domain decomposition method can be solved at a linear convergence rate. Numerical results for the proposed methods are provided.
MSC:
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65Y05 | Parallel numerical computation |
| 68U10 | Computing methodologies for image processing |
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
| 35J15 | Second-order elliptic equations |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Keywords:
total variation; Raviart-Thomas elements; domain decomposition; parallel computation; image processingCitations:
Zbl 0780.49028References:
| [1] | A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, . · Zbl 1175.94009 |
| [2] | D. Boffi, F. Brezzi, and M. Fortin, {\it Mixed Finite Element Methods and Applications}, Springer Ser. Comput. Math. 44, Springer-Verlag, Berlin, 2013, . · Zbl 1277.65092 |
| [3] | A. Chambolle, {\it An algorithm for total variation minimization and applications}, J. Math. Imaging Vision, 20 (2004), pp. 89-97, . · Zbl 1366.94048 |
| [4] | A. Chambolle and T. Pock, {\it A first-order primal-dual algorithm for convex problems with applications to imaging}, J. Math. Imaging Vision, 40 (2011), pp. 120-145, . · Zbl 1255.68217 |
| [5] | A. Chambolle and T. Pock, {\it An introduction to continuous optimization for imaging}, Acta Numer., 25 (2016), pp. 161-319, . · Zbl 1343.65064 |
| [6] | T. F. Chan and S. Esedoḡlu, {\it Aspects of total variation regularized \({L}^1\) function approximation}, SIAM J. Appl. Math., 65 (2005), pp. 1817-1837, . · Zbl 1096.94004 |
| [7] | H. Chang, X.-C. Tai, L.-L. Wang, and D. Yang, {\it Convergence rate of overlapping domain decomposition methods for the Rudin-Osher-Fatemi model based on a dual formulation}, SIAM J. Imaging Sci., 8 (2015), pp. 564-591, . · Zbl 1329.94010 |
| [8] | Y. Duan, H. Chang, and X.-C. Tai, {\it Convergent non-overlapping domain decomposition methods for variational image segmentation}, J. Sci. Comput., 69 (2016), pp. 532-555, . · Zbl 1409.68313 |
| [9] | C. Farhat, M. Lesoinne, and K. Pierson, {\it A scalable dual-primal domain decomposition method}, Numer. Linear Algebra Appl., 7 (2000), pp. 687-714, . · Zbl 1051.65119 |
| [10] | C. Farhat and F.-X. Roux, {\it A method of finite element tearing and interconnecting and its parallel solution algorithm}, Internat. J. Numer. Methods Engrg., 32 (1991), pp. 1205-1227, . · Zbl 0758.65075 |
| [11] | M. Fornasier, A. Langer, and C.-B. Schönlieb, {\it A convergent overlapping domain decomposition method for total variation minimization}, Numer. Math., 116 (2010), pp. 645-685, . · Zbl 1206.65170 |
| [12] | M. Fornasier and C.-B. Schönlieb, {\it Subspace correction methods for total variation and \(ℓ_1\)-minimization}, SIAM J. Numer. Anal., 47 (2009), pp. 3397-3428, . · Zbl 1203.65098 |
| [13] | V. Girault and P.-A. Raviart, {\it Finite Element Methods for Navier-Stokes Equations: Theory and Algorithms}, Springer Ser. Comput. Math. 5, Springer-Verlag, Berlin, 2012, . |
| [14] | M. Hintermüller and A. Langer, {\it Subspace correction methods for a class of nonsmooth and nonadditive convex variational problems with mixed \({L}^1/{L}^2\) data-fidelity in image processing}, SIAM J. Imaging Sci., 6 (2013), pp. 2134-2173, . · Zbl 1279.68327 |
| [15] | M. Hintermüller and A. Langer, {\it Non-overlapping domain decomposition methods for dual total variation based image denoising}, J. Sci. Comput., 62 (2015), pp. 456-481, . · Zbl 1323.65016 |
| [16] | C.-O. Lee, J. H. Lee, H. Woo, and S. Yun, {\it Block decomposition methods for total variation by primal-dual stitching}, J. Sci. Comput., 68 (2016), pp. 273-302, . · Zbl 1343.49046 |
| [17] | C.-O. Lee and C. Nam, {\it Primal domain decomposition methods for the total variation minimization, based on dual decomposition}, SIAM J. Sci. Comput., 39 (2017), pp. B403-B423, . · Zbl 1365.65173 |
| [18] | R. J. LeVeque, {\it Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems}, SIAM, Philadelphia, 2007, . · Zbl 1127.65080 |
| [19] | P. Monk, {\it Finite Element Methods for Maxwell’s Equations}, Oxford University Press, New York, 2003, . · Zbl 1024.78009 |
| [20] | J.-C. Nédélec, {\it Mixed finite elements in \(\mathbb{R}^3\)}, Numer. Math., 35 (1980), pp. 315-341, . · Zbl 0419.65069 |
| [21] | Y. Nesterov, {\it Smooth minimization of non-smooth functions}, Math. Program., 103 (2005), pp. 127-152, . · Zbl 1079.90102 |
| [22] | P.-A. Raviart and J.-M. Thomas, {\it A mixed finite element method for 2-nd order elliptic problems}, in Mathematical Aspects of Finite Element Methods, Springer, Berlin, 1977, pp. 292-315, . · Zbl 0362.65089 |
| [23] | L. I. Rudin, S. Osher, and E. Fatemi, {\it Nonlinear total variation based noise removal algorithms}, Phys. D, 60 (1992), pp. 259-268, . · Zbl 0780.49028 |
| [24] | D. Strong and T. Chan, {\it Edge-preserving and scale-dependent properties of total variation regularization}, Inverse Problems, 19 (2003), pp. S165-S187, . · Zbl 1043.94512 |
| [25] | J. Xu, X.-C. Tai, and L.-L. Wang, {\it A two-level domain decomposition method for image restoration}, Inverse Probl. Imaging, 4 (2010), pp. 523-545, . · Zbl 1204.68250 |
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.
