Abstract
Recent quasi-optimal error estimates for the finite element approximation of total-variation regularized minimization problems using the Crouzeix–Raviart element require the existence of a Lipschitz continuous dual solution, which is not generally given. We provide analytic proofs showing that the Lipschitz continuity of a dual solution is not necessary, in general. Using the Lipschitz truncation technique, we, in addition, derive error estimates that depend directly on the Sobolev regularity of a given dual solution.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In this article, we examine the finite element discretization of the Rudin–Osher–Fatemi (ROF) model from [33], which serves as a model problem for general convex and non-smooth minimization problems. This image processing model determines a function \(u\in BV(\Omega )\cap L^2(\Omega )\) via minimizing \(I:BV(\Omega )\cap L^2(\Omega )\rightarrow {\mathbb {R}}\), defined by
for all \( {v}\in BV(\Omega )\cap L^2(\Omega )\), where \(\vert D {v}\vert (\Omega )\) denotes the total variation, \(g\in L^2(\Omega )\) is the input data, e.g., a noisy image, and \(\Vert {v}-g\Vert _{L^2(\Omega )}^2\) is the so-called fidelity term. In addition, the fidelity parameter \(\alpha >0\) is a given constant, which determines the balance between de-noising and preserving the input image. For a more in-depth analysis of this model, concerning its analytical properties, explicit solutions, and numerical methods, we refer to [4, 5, 7, 10, 12, 13, 17,18,19,20,21, 26, 27, 29, 34]. Since this model allows for and preserves discontinuities of the input data g, cf. [17], continuous finite element methods are known to perform sub-optimally, cf. [10, 12]. Recent contributions, cf. [9, 10, 21], reveal that the quasi-optimal convergence rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) for discontinuous solutions on quasi-uniform triangulations can be obtained using the discontinuous, lower-order Crouzeix–Raviart element introduced in [22]. More precisely, these error estimates yield a bound for the error for the approximation of minimizers of \(I: BV(\Omega )\cap L^2(\Omega ) \rightarrow {\mathbb {R}}\) via minimizing the discrete functional \(I_h:{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\), defined by
for all \( {v_h} \in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\), where \({\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) is the Crouzeix–Raviart finite element space, i.e., the space of element-wise affine functions that are continuous at the midpoints of element sides, \(\nabla _h\!:\!{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\!\rightarrow \! {\mathcal {L}}^0({\mathcal {T}}_h)^d\) denotes the element-wise gradient, and \(\Pi _h\!:\!L^2(\Omega )\! \rightarrow \! {\mathcal {L}}^0({\mathcal {T}}_h)\) is the \(L^2\) –projection operator onto element-wise constant functions. Note that the family of discrete functionals \(I_h:{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\), \(h>0\), defines a non-conforming approximation of the functional \(I:BV(\Omega )\cap L^2(\Omega )\rightarrow {\mathbb {R}}\), as, e.g., jump terms of \(u_h\) across inter-element sides are not included. For this family recently a \(\Gamma \!\)–convergence result with respect to strong convergence in \(L^1(\Omega )\) or distributional convergence has been established under general assumptions, i.e., that \(g\in L^2(\Omega )\), cf. [21, Propositon 3.1]. However, the quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}} )}\) till now only holds if the dual problem given via maximizing \(D:W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\rightarrow {\mathbb {R}}\cup \{-\infty \}\), defined by
for all \( {y}\in W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\), where \({I_{K_1(0)}:L^\infty (\Omega ;{\mathbb {R}}^d)\rightarrow {\mathbb {R}}\cup \{+\infty \}}\) is for \( {y} \in L^\infty (\Omega ;{\mathbb {R}}^d)\) defined by \( I_{K_1(0)}( {y}) := 0\) if \(\Vert {y}\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)} \le 1\) and \({I_{K_1(0)}(y) := +\infty }\) else, admits a Lipschitz continuous solution. Unfortunately, the Lipschitz continuity of a maximum of \(D:W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\rightarrow {\mathbb {R}}\cup \{-\infty \}\) is not generally given, as [13, Section 3] clarified. Without the assumption that a Lipschitz continuous solution to (1.2) exists, but that \(g\!\in \! BV (\Omega ) \cap L^\infty (\Omega )\), in [21, Section 5.2], the sub-optimal convergence rate \(\smash {{\mathcal {O}}(h^{\frac{1}{4}})}\) has been established. The approach of [21, Section 5.2] consists in a convolution of a maximum \(z\in W^\infty _N(div ;\Omega )\) of (1.2) in order to comply with the crucial Lipschitz continuity property at least in an approximate sense.We use an alternative regularization approach, which operates highly at a local level, the celebrated Lipschitz truncation technique. Its basic purpose is to approximate Sobolev functions \(u \in W^{1,p}(\Omega )\) by \(\lambda \)–Lipschitz functions \({u_\lambda \in W^{1,\infty }(\Omega )}\), \({\lambda >0}\). The original approach of this technique traces back to Acerbi and Fusco, cf. [1,2,3]. Since then, the Lipschitz truncation technique is used in various areas of analysis: In the calculus of variations, in the existence theory of partial differential equations, and in regularity theory. For a longer list of references, we refer the reader to [23]. To the best of the authors knowledge, this article provides the first deployment of the Lipschitz truncation technique in the field of image processing. To be more precise, for the application in this article, the main advantage of the Lipschitz truncation technique in comparison to convolution is that not only u and \(u_\lambda \) coincide up to a set of small measure, but equally \(\nabla u\) and \(\nabla u_\lambda \) do. By deploying the Lipschitz truncation technique, we arrive at error estimates whose resulting rates directly depend on the respective Sobolev regularity of a given maximum \({z\!\in \! W^{1,p}(\Omega ;{\mathbb {R}}^d)}\) of (1.2). If only \(g\in L^\infty (\Omega )\) and one, in addition, has that, e.g., \({z\in W^{1,p}(\Omega ;{\mathbb {R}}^d)}\) for \({p\ge 3}\), then the results of this article yield the sub-optimal rate \(\smash {{\mathcal {O}}(h^\frac{1}{4})}\). In this manner, we intend to fill the gap between the optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) for \(z\in W^{1,\infty }(\Omega ;{\mathbb {R}}^d)\) and \(g\in L^\infty (\Omega )\) and the rate \(\smash {{\mathcal {O}}(h^{\frac{1}{4}})}\) for \(z\in W^\infty _N(div ;\Omega )\) and \({g\in L^\infty (\Omega )\cap BV(\Omega )}\).
As a maximum of (1.2) is not necessarily in a Sobolev space, but in \(W^2_N(div ;\Omega )\) \(\cap L^\infty (\Omega ;{\mathbb {R}}^d)\), we also study the case of a non-existence of Sobolev solutions to (1.2). It turns out that if a maximum \(z\!\in \! W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\) of (1.2) is element-wise Lipschitz continuous, i.e., the discontinuity set \(J_z\) is resolved by the triangulations, or at least in an approximate sense with the rate \({\mathcal {O}}(h)\), cf. Remark 4.8, then the optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) can be expected. Beyond that, we find that the optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) is attained if a dual solution fulfills \(\vert z\vert <1\) along its discontinuity set \(J_z\) while, simultaneously, its jump \([\![z]\!]\) over its discontinuity set \(J_z\) remains small. Some of these conditions apply, e.g., to the setting described in [13, Section 3] with a suitable triangulation \({\mathcal {T}}_h\), \(h>0\), of the domain \(\Omega \), for which the optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) could be reported without giving an analytical explanation. This article’s purpose is to give—at least for special cases—a missing analytical explanation.
This article is organized as follows: In Sect. 2, we introduce the employed notation, define the relevant finite element spaces and give a brief review of the continuous and discretized ROF model. In Sect. 3, using the Lipschitz truncation technique, we establish error estimates that depend directly on the Sobolev regularity of a maximum of (1.2). In Sect. 4, we prove quasi-optimal error estimates without explicitly assuming that a Lipschitz continuous maximum of (1.2) exists. In Sect. 5, we confirm our theoretical findings via numerical experiments.
2 Preliminaries
Throughout the article, if not otherwise specified, we denote by \({\Omega \subseteq {\mathbb {R}}^d}\), \({d \in {\mathbb {N}}}\), a bounded polyhedral Lipschitz domain, whose boundary is disjointly divided into a Dirichlet part \(\Gamma _D\) and a Neumann part \(\Gamma _N\), i.e., \({\partial \Omega = \Gamma _D\cup \Gamma _N}\) and \({\emptyset = \Gamma _D\cap \Gamma _N}\).
2.1 Function spaces
For \(p\in \left[ 1,\infty \right] \) and \(l\in {\mathbb {N}}\), we employ the standard notationsFootnote 1
\(\smash {W^{1,p}(\Omega ;{\mathbb {R}}^l):=W^{1,p}_D(\Omega ;{\mathbb {R}}^l)}\) if \(\smash {\Gamma _D=\emptyset }\), and \(\smash {W^{p}(div ;\Omega ):=W^{p}_N(div ;\Omega )}\) if \(\smash {\Gamma _N=\emptyset }\), where \(\smash {tr \!: \!W^{1,p}(\Omega ;{\mathbb {R}}^l) \!\rightarrow \! {L^p(\partial \Omega ;{\mathbb {R}}^l)}}\) and \( \smash {tr (\cdot ) \!\cdot \! n \!: \!W^p(div ;\Omega ) \!\rightarrow \! {W^{-\frac{1}{p},p}(\partial \Omega )}}\) denote the trace and normal trace operator. In particular, we predominantlyomit \(tr (\cdot )\) in this context. We fall back on the abbreviations \({L^p(\Omega ) := L^p(\Omega ;{\mathbb {R}}^1)}\), \(W^{1,p}(\Omega ) := W^{1,p}(\Omega ;{\mathbb {R}}^1)\) and \( {W^{1,p}_D(\Omega ) := W^{1,p}_D(\Omega ;{\mathbb {R}}^1)}\). Let \(\vert D (\cdot )\vert (\Omega ) :\) , defined byFootnote 2
for all \( {v}\in L^1_{loc }(\Omega )\), denote the total variation. Then, the space of functions of bounded variation is defined by \( {BV(\Omega ):=\left\{ v\in L^1(\Omega )\mid \vert D v\vert (\Omega )<\infty \right\} }\).
2.2 Triangulations
In what follows, we let \(({\mathcal {T}}_h)_{h>0}\) be a sequence of regular, i.e., uniformly shape regular and conforming, triangulations of \(\Omega \subseteq {\mathbb {R}}^d\), \(d\in {\mathbb {N}}\), cf. [15]. The sets \({\mathcal {S}}_h\) and \({\mathcal {N}}_h\) contain the sides and vertices (nodes), resp., of the elements. The parameter \(h>0\) refers to the maximal mesh-size of \({\mathcal {T}}_h\). More precisely, if we define \({h_T:=diam (T)}\) for all \({T\in {\mathcal {T}}_h}\), then we have that \(h=\max _{T\in {\mathcal {T}}_h}{h_T}\). For any \(k\in {\mathbb {N}}\) and \({T\in {\mathcal {T}}_h}\), we let \({\mathcal {P}}_k(T)\) denote the set of polynomials of maximal total degree k on T. Then, the set of element-wise polynomial functions or vector fields, resp., is defined by
For any \(T\in {\mathcal {T}}_h\) and \(S\in {\mathcal {S}}_h\), we let \(\smash {x_T:=\frac{1}{d+1}\sum _{z\in {\mathcal {N}}_h\cap T}{z}}\) and \(\smash {x_S:=\frac{1}{d}\sum _{z\in {\mathcal {N}}_h\cap S}{z}}\) denote the midpoints (barycenters) of T and S, resp. The \(L^2\)–projection operator onto element-wise constant functions or vector fields, resp., is denoted by
For \(v_h \in {\mathcal {L}}^1({\mathcal {T}}_h)^l\), it holds \(\Pi _hv_h|_T = v_h(x_T)\) for all \(T \in {\mathcal {T}}_h\). Moreover, for \({p \in \left[ 1,\infty \right] }\), there exists a constant \(c_{\Pi }>0\) such that for all \(v\in L^p(\Omega ;{\mathbb {R}}^l)\), cf. [24], we have that
-
(L0.1)
\(\Vert \Pi _h v\Vert _{L^p(\Omega ;{\mathbb {R}}^l)}\le \Vert v\Vert _{L^p(\Omega ;{\mathbb {R}}^l)}\),
-
(L0.2)
\(\Vert v-\Pi _h v\Vert _{L^p(\Omega ;{\mathbb {R}}^l)}\le c_{\Pi }h \Vert \nabla v\Vert _{L^p(\Omega ;{\mathbb {R}}^{l\times d})}\) if \(v\in W^{1,p}(\Omega ;{\mathbb {R}}^l)\).
2.3 Crouzeix–Raviart element
A particular instance of a larger class of non-conforming finite element spaces, introduced in [22], is the Crouzeix–Raviart finite element space, consisting of element-wise affine functions that are continuous at the midpoints of element sides, i.e.,Footnote 3
The element-wise application of the gradient to \(v_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) defines an element-wise constant vector field \(\nabla _hv_h\in {\mathcal {L}}^0({\mathcal {T}}_h)^d\) via \({\nabla _hv_h|_T:=\nabla (v_h|_T)}\) for all \({T\in {\mathcal {T}}_h}\). Crouzeix–Raviart finite element functions that vanish at midpoints of boundary element sides that correspond to the Dirichlet boundary \(\Gamma _{\! D}\) are contained in the space
In particular, we have that \( {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)= {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) if \(\Gamma _D=\emptyset \). A basis of \({\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) is given by the functions \(\varphi _S\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\), \(S\in {\mathcal {S}}_h\), satisfying the Kronecker property \(\varphi _S(x_{S'})=\delta _{S,S'}\) for all \(S,S'\in {\mathcal {S}}_h\). A basis of \({\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\) is given by \((\varphi _S)_{S\in {\mathcal {S}}_h;S\not \subseteq \Gamma _D}\). For any \(p\in \left[ 1,\infty \right] \), the quasi-interpolation operator \(\smash {I_{cr}:W^{1,p}_D(\Omega )\rightarrow {\mathcal {S}}^{1,cr}_D({\mathcal {T}}_h)}\), for every \(v\in W^{1,p}_D(\Omega )\) defined by
preserves averages of gradients, i.e., \(\nabla _h(I_{cr}v)\!=\!\Pi _h(\nabla v)\) in \({\mathcal {L}}^0({\mathcal {T}}_h)^d\) for \({v\!\in \! W^{1,p}_D(\Omega )}\). Moreover, for \(p \in \left[ 1,\infty \right] \), there exits a constant \({c_{cr} > 0}\) such that for all \({v \in W^{1,p}_D(\Omega )}\), cf. [14], we have that
-
(CR.1)
\(\Vert \nabla _h (I_{cr}v)\Vert _{L^p(\Omega ;{\mathbb {R}}^d)}\le \Vert \nabla v\Vert _{L^p(\Omega ;{\mathbb {R}}^d)}\),
-
(CR.2)
\(\Vert v-I_{cr}v\Vert _{L^p(\Omega )}\le c_{cr}h \Vert \nabla v\Vert _{L^p(\Omega ;{\mathbb {R}}^d)}\),
-
(CR.3)
\(\Vert I_{cr}v\Vert _{L^\infty (\Omega )}\le c_d\Vert v\Vert _{L^\infty (\Omega )}\), where \(c_d:=(d+1)(d-1)\), if \(v\in L^\infty (\Omega )\).
2.4 Raviart–Thomas element
The lowest order Raviart–Thomas finite element space, introduced in [32], consists of element-wise affine vector fields that have continuous constant normal components on inner element sides, i.e.,Footnote 4
Raviart–Thomas finite element functions that have vanishing normal components on the Neumann boundary \(\Gamma _N\) are contained in the space
In particular, we have that \({\mathcal {R}}T^0_N({\mathcal {T}}_h)={\mathcal {R}}T^0({\mathcal {T}}_h)\) if \(\Gamma _N=\emptyset \). A basis of \({\mathcal {R}}T^0({\mathcal {T}}_h)\) is given by the vector fields \(\psi _S\in {\mathcal {R}}T^0({\mathcal {T}}_h)\), \(S\in {\mathcal {S}}_h\), satisfying the Kronecker property \(\psi _S|_{S'}\cdot n_{S'}=\delta _{S,S'}\) on \(S'\) for all \(S\in {\mathcal {S}}_h\), where \(n_S\) for all \(S\in {\mathcal {S}}_h\) denotes the unit normal vector on S that points from \(T_-\) to \(T_+\) if \(S\!=\!\partial T_-\cap \partial T_+\!\in \! {\mathcal {S}}_h\). A basis of \({\mathcal {R}}T^0_N({\mathcal {T}}_h)\) is given by \(\psi _S\!\in \! {\mathcal {R}}T^0_N({\mathcal {T}}_h)\), \({S\!\in \! {\mathcal {S}}_h\!{\setminus }\!\Gamma _N}\). The quasi-interpolation operator \(I_{rt}:V^{div }(\Omega ):=\{y\in L^p(\Omega ;{\mathbb {R}}^d) \mid div (y)\in L^q(\Omega )\}\rightarrow {\mathcal {R}}T^0_N({\mathcal {T}}_h)\), where \(p>2\) and \(\smash {q>\frac{2d}{d+2}}\), for every \(\smash { {y}\in V^{div }(\Omega )}\) defined by
preserves averages of divergences, i.e., \(div (I_{rt} {y})=\Pi _h(div ( {y}))\) in \({\mathcal {L}}^0({\mathcal {T}}_h)\) for all \({ {y}\in V^{div }(\Omega )}\). Moreover, for \(p\in \left[ 1,\infty \right] \), there exists a constant \({c_{rt}>0}\) such that for all \( {y}\in V^{div }(\Omega )\), cf. [25], we have that
-
(RT.1)
\(\Vert {y}-I_{rt}y\Vert _{L^p(\Omega ;{\mathbb {R}}^d)}\le c_{rt}h \Vert \nabla {y}\Vert _{L^p(\Omega ;{\mathbb {R}}^{d\times d})}\) if \( {y}\in W^{1,p}(\Omega ;{\mathbb {R}}^d)\),
-
(RT.2)
\(\Vert I_{rt} {y}\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le c_{rt} \Vert { y}\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\) if \( {y}\in L^\infty (\Omega ;{\mathbb {R}}^d)\).
For \(p\!\in \! [1,\infty )\), due to the density of \(C^\infty (\Omega ;{\mathbb {R}}^d)\cap W^p_N(div ;\Omega )\) in \(W^p_N(div ;\Omega )\), the oper-ator and (RT.2) can be extended to \( {y}\!\in \! W^p_N(div ;\Omega )\), losing the representation (2.2).
2.5 The continuous Rudin–Osher–Fatemi (ROF) model
Given \(g\!\in \! L^2(\Omega )\) and \(\alpha \!>\!0\), the Rudin–Osher–Fatemi (ROF) model, cf. [33], determines a function \({u\!\in \! BV(\Omega )\cap L^2(\Omega )}\) that is minimal for \({I\!:\!BV(\Omega )\cap L^2(\Omega )\!\rightarrow \! {\mathbb {R}}}\), defined by
for all \(v\in BV(\Omega )\cap L^2(\Omega )\). In [8, Theorems 10.5 & 10.6], it is proved that for every \({g\in L^2(\Omega )}\), there exists a unique minimizer \(u\in BV(\Omega )\cap L^2(\Omega )\) of \({I: BV(\Omega )\cap L^2(\Omega ) \rightarrow {\mathbb {R}}}\). If \(g \in L^\infty (\Omega )\), then \(u \in L^\infty (\Omega )\) with \({\Vert u\Vert _{L^\infty (\Omega )}\!\le \! \Vert g\Vert _{L^\infty (\Omega )}}\) (cf. [8, Proposition 10.2]). In [27, Theorem 2.2], it is shown that the corresponding dual problem to (2.3) determines a vector field \({z\!\in \! W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)}\), where \(\Gamma _N\!=\!\partial \Omega \), that is maximal for \({D\!:\!W^2_N(div ;\Omega ) \cap L^\infty (\Omega ;{\mathbb {R}}^d)\!\rightarrow \! {\mathbb {R}} \cup \{-\infty \}}\), defined by
for all \(\smash {y\!\in \! W^2_N(div ;\Omega ) \cap L^\infty (\Omega ;{\mathbb {R}}^d)}\), where \(\smash {I_{K_1(0)}\!:\!L^\infty (\Omega ;{\mathbb {R}}^d)\!\rightarrow \! {\mathbb {R}} \cup \{\infty \}}\) is defined by \(I_{K_1(0)}(y) := 0\) if \(y\in L^\infty (\Omega ;{\mathbb {R}}^d)\) with \({\Vert y\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1}\) and \({I_{K_1(0)}(y):=\infty }\) else. Apart from that, in [27, Theorem 2.2], it is shown that (2.4) possesses a maximizer \({z\in W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)}\), which satisfies the strong duality principle
The strong duality principle (2.5), appealing to [8, Proposition 10.4] and referring to standard convex optimization arguments, is equivalent to the optimality relations
2.6 The discretized Rudin–Osher–Fatemi (ROF) model
Given some \(g\in L^2(\Omega )\) and \(\alpha >0\), setting \(g_h:=\Pi _hg\in {\mathcal {L}}^0({\mathcal {T}}_h)\), the discretized ROF model proposed by [21] determines a Crouzeix–Raviart function \({u_h\!\in \! {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)}\) that is minimal for \(I_h:{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\), defined by
for all \(v_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\). In [21] and [10], it has been shown that the corresponding dual problem to (2.7) determines a Raviart–Thomas vector field \({z_h\in {\mathcal {R}}T^0_N({\mathcal {T}}_h)}\), where \({\Gamma _N=\partial \Omega }\), that is maximal for \(D_h:{\mathcal {R}}T^0_N({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\cup \{-\infty \}\), defined by
for all \(y_h\!\in \! {\mathcal {R}}T^0_N({\mathcal {T}}_h)\). Apart from that, in [21] and [10], it has been established that a discrete weak duality principle holds, i.e., it holds
which is a cornerstone of the error analysis for (2.7). In particular, note that for the validity of (2.9) the \(L^2\)–projection operator \(\Pi _h\) in (2.7) and (2.8) plays a key role.
2.7 Piece-wise Lipschitz, but not globally Lipschitz, continuous solution to (2.4)
In [13, Section 3], the construction of an input data \(g\in BV(\Omega )\cap L^\infty (\Omega )\) that leads to a solution \(z\in W^\infty _N(div ;\Omega )\) to (2.4) such that \({z\notin W^{1,\infty }(\Omega ;{\mathbb {R}}^2)}\), in essence, is based on the asymmetry of the function
defined on a domain that is symmetric with respect to the \({\mathbb {R}}e_2\)–axis.Footnote 5 More precisely, using this asymmetry property, it is possible to reduce the minimization problem (2.3) on \(\Omega \) into two independent minimization problems on \(\Omega ^+:=\Omega \cap ({\mathbb {R}}_{> 0}\times {\mathbb {R}})\) and \(\Omega ^- := \Omega \cap ({\mathbb {R}}_{< 0} \times {\mathbb {R}})\) for which explicit solutions \({u^{\pm } \in BV(\Omega ^{\pm })\cap L^\infty (\Omega ^{\pm })}\) exist. In this way, the following result could be derived.
Proposition 2.1
Let \(\Omega \subseteq {\mathbb {R}}^2\) be symmetric with respect to the \({\mathbb {R}}e_2\)–axis and let \(r>0\) be such that \({B_r^2(\pm r e_1)\subset \subset \Omega }\). Then, for (2.10) and \({\alpha >0}\), the minimizer of \({I: {\mathcal {A}} \rightarrow {\mathbb {R}}}\), where \({{\mathcal {A}} := \{u \in BV(\Omega ) \cap L^\infty (\Omega )\mid tr (u) = 0 in L^1(\partial \Omega ) \}}\), is given via
Proof
See [13, Proposition 3.1]. \(\square \)
Combining the representation formula (2.11) and the optimality conditions (2.6), it turns out that there exists no Lipschitz continuous dual solution to the setting described in Proposition 2.1.
Corollary 2.2
Let the assumptions of Proposition 2.1 be satisfied with \({\alpha r>2}\). Then, any dual solution \(z\!\in \! W^\infty (div ;\Omega )\) to (2.11) is not \(\theta \)–Hölder continuous if \({\theta \!> \!\frac{1}{2}}\).
Proof
See [13, Corollary 3.2]. \(\square \)
Remark 2.3
If one carefully follows the proof in [13, Corollary 3.2], then one finds that the existence of non–Lipschitz continuous dual solutions is a consequence of the fact that the data \(g \in BV(\Omega )\cap L^\infty (\Omega )\) is set-wise constant on \(B_r^2(r e_1)\) and \(B_r^2(- r e_1)\), respectively, and anti-symmetric with respect to the \({\mathbb {R}}e_2\)–axis as well as that \(B_r^2( r e_1)\cup B_r^2( r e_2)\) has no \(\theta \)–Hölder continuous boundary if \(\theta >\frac{1}{2}\). Overall, here, the existence of a non–Lipschitz continuous dual solution traces back to the data \(g\in BV(\Omega )\cap L^\infty (\Omega )\) and not, e.g., to the regularity of the domains \(\Omega ^{+}\) and \(\Omega ^{-}\).
An example of a not–Lipschitz continuous dual solution to (2.11) is the following, which is separately Lipschitz continuous on \(\Omega ^+\) and \(\Omega ^-\), resp., and jumps over the \({\mathbb {R}}e_2\)–axis. We will resort to this dual solution to derive optimal error estimates for the setting described in Proposition 2.1, as already reported in [13, Example 6.1].
Proposition 2.4
Let \(\Omega \subseteq {\mathbb {R}}^2\) and \(r>0\) be such as in Proposition 2.1. Moreover, let \(\alpha >0\) be such that \(\alpha r>2\). Then, the vector field \(z:\Omega \subseteq {\mathbb {R}}^2\rightarrow {\mathbb {R}}^2\), defined by
for all \(x\!\in \! \Omega \), satisfies \(z\!\in \! W^\infty (div ; \Omega )\), \({\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\!\le \! 1}\), \(\vert D u\vert (\Omega )\!=\!-(u,div (z))_{L^2(\Omega )}\) and \( div (z)\!=\!\alpha (u-g)\) in \(L^\infty (\Omega )\), where \({u\!\in \!{\mathcal {A}}}\) is defined by (2.11), i.e.,\(z\in W^\infty (div ;\Omega )\) is a dual solution to (2.11).
Proof
Apparently, we have that \(z \in L^\infty (\Omega ;{\mathbb {R}}^d)\) with \({\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)} \le 1}\). In addition, it is not difficult to see that \(\smash {z|_{\Omega ^{\pm }}\in W^{1,\infty }(\Omega ^{\pm };{\mathbb {R}}^d)}\). Since \({z|_{\Omega ^+}\cdot n_{\Omega ^+} = -z|_{\Omega ^-}\cdot n_{\Omega ^-}}\) on \({\mathbb {R}}e_2\cap \Omega \), we find that \(z\!\in \! W^2(div ;\Omega )\). It is well-known, cf. [8, Example 10.4], that
Thus, we have that \( div (z)=\alpha (u-g)\) in \(L^\infty (\Omega )\), which implies that \({z\!\in \! W^\infty (div ;\Omega )}\). Apart from that, using that \(u=0\) continuously in \({\mathbb {R}}e_2\cap \Omega \), we finally conclude that \(\vert D u\vert (\Omega )=-(u,div (z))_{L^2(\Omega )}\), i.e., \(z\in W^\infty (div ;\Omega )\) is a dual solution to (2.11). \(\square \)
3 Error estimates depending on Sobolev regularity
The validity of quasi-optimal error estimates for the finite element approximation of total-variation regularized minimization problems by means of the Crouzeix–Raviart element in the case of an existing Lipschitz continuous solution to (2.4) in [10, 21], in essence, is based on four results: The discrete weak duality principle (2.9), the discrete strong coercivity of \(I_h:{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\), i.e.,
for all \(\smash {v_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)}\), where \(\smash {u_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)}\) is the minimum of \(\smash {I_h:{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\rightarrow {\mathbb {R}}}\), the strong duality principle (2.5), and the existence of appropriate primal and dual quasi-interpolants, guaranteed through the following two lemmas:
For the benefit of readability and without loss of generality, we assume for the remainder of this article, if not otherwise specified, that \(\alpha =1\).
Lemma 3.1
(Primal quasi-interpolant) For every \(u\in BV(\Omega )\cap L^\infty (\Omega )\), there exists a Crouzeix–Raviart function \({\tilde{u}}_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) with the following properties:
-
(P.1)
\(\Vert \nabla _h {\tilde{u}}_h\Vert _{L^1(\Omega ;{\mathbb {R}}^d)}\le \vert D u\vert (\Omega )\),
-
(P.2)
\(\Vert u-{\tilde{u}}_h\Vert _{L^1(\Omega )}\le c_{cr}h\vert D u\vert (\Omega )\),
-
(P.3)
\(\Vert {\tilde{u}}_h\Vert _{L^\infty (\Omega )}\le c_d\Vert u\Vert _{L^\infty (\Omega )}\),
-
(P.4)
\(I_h({\tilde{u}}_h)\le I(u)+2c_dc_{cr}\Vert u\Vert _{L^\infty (\Omega )}\vert D u\vert (\Omega )h-\frac{1}{2}\smash {\Vert g-g_h\Vert _{L^2(\Omega )}^2}\).
Proof
See [10, Lemma 4.4] or [21, Section 5]. \(\square \)
Lemma 3.2
(Dual quasi–interpolant) For every \({z\in W^{1,\infty }(\Omega ;{\mathbb {R}}^d)\cap W^2_N(div ;\Omega )}\) such that \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\!\le \! 1\), there exists a Raviart–Thomas vector field \({{\tilde{z}}_h\!\in \! {\mathcal {R}}T^0_N({\mathcal {T}}_h)}\) with the following properties:
-
(D.1)
\(\Vert \Pi _h{\tilde{z}}_h\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\),
-
(D.2)
\(D_h({\tilde{z}}_h)\!\ge \!D(z)\!-\!c_{rt}\Vert \nabla z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^{d\times d})}\Vert g\Vert _{L^2(\Omega )}\Vert div (z)\Vert _{L^2(\Omega )}h\!-\!\frac{1}{2}\Vert g\!-\!g_h\Vert _{L^2(\Omega )}^2\).
Proof
See [10, Lemma 4.5] or [21, Section 5]. \(\square \)
While Lemma 3.1 does not impose restrictive assumptions on the minimum \(u\in BV(\Omega )\cap L^2(\Omega )\), since already \(u\in L^\infty (\Omega )\) if \(g\in L^\infty (\Omega )\) (cf. [8, Proposition 10.2]), the required Lipschitz continuity of a solution \(z\!\in \! W_N^\infty (div ; \Omega )\) to (2.4) in Lemma 3.2 is often not fulfilled, cf. [13] or Sect. 2.7. We resort to the Lipschitz truncation technique to fulfill the Lipschitz continuity requirement on a solution to (2.4) in Lemma 3.2 at least in an approximate sense and, in this way, derive error estimates that depend directly on the Sobolev regularity of a solution \( {z\!\in \! W^{1,p}(\Omega ; {\mathbb {R}}^d)} \) to (2.4). The main advantage of this approach is that the Lipschitz truncation technique is based on local arguments, while regularization by convolution as in [21, Section 5.2], for example, operates highly non-local and, therefore, wipes out point-wise and/or local properties of a solution to (2.4) that potentially could have been incorporated. To be more precise, in [21, Section 5.2], the requirement \(g\in BV(\Omega )\cap L^\infty (\Omega )\) was needed to estimate \(\Vert div (z)-div (z_\varepsilon )\Vert _{\smash {L^1(\Omega )}}\), where \(z_\varepsilon := z\circ \omega _\varepsilon \in C^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)\), \({\varepsilon > 0}\), denotes the convolution with a suitably scaled kernel \(\omega _\varepsilon \in C^\infty _0({\mathbb {R}}^d)\), by \(\varepsilon \vert D g\vert (\Omega )\). In contrast to that, if \(z_\lambda \in W^{1,\infty }({\mathbb {R}}^d;{\mathbb {R}}^d)\), \(\lambda >0\), denotes the Lipschitz truncation of a suitable extension \({\overline{z}}\in W^{1,p}({\mathbb {R}}^d;{\mathbb {R}}^d)\) of \({z\in W^{1,p}(\Omega ;{\mathbb {R}}^d)}\), then we can exploit the particular properties \(\nabla z_\lambda \!=\!\nabla {\overline{z}}\) in \(\{z_\lambda = {\overline{z}}\}\) and \({\vert \{z_\lambda \ne {\overline{z}}\}\vert \!\le \! \vert \{{\mathcal {M}}(\nabla {\overline{z}})>\lambda \}\vert }\)Footnote 6, to conclude that \(\Vert div (z)-div (z_\lambda )\Vert _{\smash {L^1(\Omega )}} \le c\lambda ^{1-p}\Vert \nabla z\Vert _{L^p(\Omega ;{\mathbb {R}}^{d\times d})}\). In this way, we obtain the same rate \(\smash {{\mathcal {O}}(h^{\frac{1}{4}})}\) in [21, Section 5.2] without the assumption \(g\in BV(\Omega )\) but need to assume \(\smash {z\in W^{1,3}(\Omega ;{\mathbb {R}}^d)}\cap L^\infty (\Omega ;{\mathbb {R}}^d)\) instead of only \(\smash {z\in W^\infty _N(div ;\Omega )}\).
Theorem 3.3
(Lipschitz truncation technique) Let \(z\!\in \! W^{1,p}({\mathbb {R}}^d;{\mathbb {R}}^d)\), \({p\!\in \! \left[ 1,\infty \right) }\), and \(\theta ,\lambda \!>\!0\). Then, there is a Lipschitz continuous vector field \({z_{\theta ,\lambda }\!\in \! W^{1,\infty }({\mathbb {R}}^d;{\mathbb {R}}^d)}\) and a constant \({c_{LT } > 0}\), which does not depend on \({p \in \left[ 1,\infty \right) }\) and \({\theta ,\lambda > 0}\), such that the following statements apply:
-
(LT.1)
\(\Vert z_{\theta ,\lambda }\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)}\le \theta \),
-
(LT.2)
\(\Vert \nabla z_{\theta ,\lambda }\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^{d\times d})}\le c_{LT }\lambda \),
-
(LT.3)
\(\vert \{z_{\theta ,\lambda }\ne z\}\vert \le \vert \{{\mathcal {M}}(z)>\theta \}\vert +\vert \{ {\mathcal {M}}(\nabla z)> \lambda \}\vert \),
-
(LT.4)
\(\nabla z_{\theta ,\lambda }=\nabla z\) in \(\{z_{\theta ,\lambda }= z\}\).
Proof
See the first part of the proof of [23, Theorem 2.3] or [31, Section 1.3.3]. \(\square \)
A crucial property of the Lipschitz truncation technique for this article is that, similar to regularization by convolution, it does not increase the maximal length of a vector field.
Remark 3.4
(Maximal length preservation of the Lipschitz truncation technique) If \({z\in W^{1,p}({\mathbb {R}}^d;{\mathbb {R}}^d)\cap L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)}\), \({p\in \left[ 1,\infty \right) }\), for some \(\theta >0\) has the property \(\Vert z\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)} \le \theta \), then
i.e., \(\vert \{ {\mathcal {M}}( z)> \theta \}\vert =0\), which (cf. Theorem 3.3, (LT.3) for arbitrary \({\lambda >0}\) yields
Through the combination of both the p–type Tschebyscheff–Markoff–inequality, i.e., \(\smash {\vert \{{\mathcal {M}}(\nabla z)\!>\!\lambda \}\vert \!\le \! \lambda ^{-p}\Vert {\mathcal {M}}(\nabla z)\Vert _{L^{p}({\mathbb {R}}^d;{\mathbb {R}}^{d\times d})}^p}\), and the strong type (p, p)–estimate of the Hardy–Littlewood–Maximal operator (cf. [31, Theorem 1.22]), i.e., for \({c_{{\mathcal {M}}}\!>\!0}\)Footnote 7, \(\smash {\Vert {\mathcal {M}}(\nabla z)\Vert _{L^{p}({\mathbb {R}}^d;{\mathbb {R}}^{d\times d})}^p\le c _{{\mathcal {M}}} \Vert \nabla z\Vert _{L^{p}({\mathbb {R}}^d;{\mathbb {R}}^{d\times d})}^p}\), we deduce from (3.2) that
By means of (3.3), also using Theorem 3.3, (LT.2) & (LT.4), we, then, deduce that
Through the combination of Lemma 3.2, Theorem 3.3 and Remark 3.4, we arrive at the following result providing an admissible dual quasi-interpolant whose particular properties depend directly on the Sobolev regularity of a solution to (2.4).
Lemma 3.5
(Dual quasi–interpolant depending on Sobolev regularity for \({\Gamma _N = \emptyset }\)) Let \(g\in L^\infty (\Omega )\) and let \({z\in W^{1,p}(\Omega ;{\mathbb {R}}^d)\cap W^\infty (div ;\Omega )}\), \({p\in \left[ 2,\infty \right) }\), be such that \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\). Then, there exists a Raviart–Thomas vector field \({{\tilde{z}}_h\in {\mathcal {R}}T^0({\mathcal {T}}_h)}\) with the following properties:
- (\(D_p\).1):
-
\(\Vert \Pi _h{\tilde{z}}_h\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\).
- (\(D_p\).2):
-
\(\smash {D_h({\tilde{z}}_h)\ge D( z)-c_p(z)h^{\frac{p-2}{p-1}}-\frac{1}{2}\Vert g-g_h\Vert _{L^2(\Omega )}^2}\), where
$$\begin{aligned} \begin{aligned} c_p(z)&:=2c_{rt}\Vert g\Vert _{L^2(\Omega )}d^{\frac{1}{2}}\big (1+{c_{{\mathcal {M}}}}^{\smash {\!\frac{1}{2}}}c_{LT }\big ) c_{E }\Vert \nabla z\Vert _{L^2(\Omega ;{\mathbb {R}}^{d\times d})}c_{LT }\\ {}&\quad \quad +8dc_{LT }^2c_{{\mathcal {M}}}c_{E }^p\Vert \nabla z\Vert _{L^p(\Omega ;{\mathbb {R}}^{d\times d})}^p.\end{aligned} \end{aligned}$$(3.5)Here, \(c_{E }>0\) is the Lipschitz constant of the lower-order extension operator \(P: W^{1,q}(\Omega ;{\mathbb {R}}^l) \rightarrow W^{1,q}({\mathbb {R}}^d;{\mathbb {R}}^l)\), \(q \in [1,\infty ]\), constructed in [16, Section 9.2], which does not depend on \(q \in [1,\infty ]\).
Remark 3.6
-
(i)
The arguments remain valid for \(\Gamma _D\!\ne \! \partial \Omega \) if for \(z\!\in \! W^{1,p}(\Omega ;{\mathbb {R}}^d)\) \(\cap W^\infty _N(div ;\Omega )\), \(p\!\in \!\left[ 2,\infty \right) \), such that \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\!\le \! 1\), there exists an extension \(\smash {{\overline{z}}\in W^{1,p}({\mathbb {R}}^d;{\mathbb {R}}^d)}\) with \(\overline{ z}|_{\Omega }\!=\! z\) and \(\smash {\Vert \overline{ z}\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)}\!\le \! 1}\) and if for this extension, the Lipschitz truncation \({\overline{z}}_{1,\lambda }\in W^{1,\infty }({\mathbb {R}}^d;{\mathbb {R}}^d)\) from Theorem 3.3 satisfies \( {\overline{z}}_{1,\lambda }\cdot n =0\) in \(\Gamma _N\).
-
(ii)
In general, the constant \( {c_p(z)}\) deteriorates as \(p\!\rightarrow \! \infty \), i.e., \({ {c_p(z)}\!\rightarrow \! \infty }\) \({(p\!\rightarrow \!\infty )}\).
Proof
(of Lemma 3.5) Resorting to a lower-order extension operator, as, e.g., in [16, Theorem 9.7], we get some \(\smash {{\overline{z}}\!\in \! W^{1,p}({\mathbb {R}}^d;{\mathbb {R}}^d)}\) with \(\overline{ z}|_{\Omega }\!=\! z\) and \(\smash {\Vert \overline{ z}\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)}\!\le \! 1}\). Denote by \( z_{\lambda } := {\overline{z}}_{1,\lambda } \in W^{1,\infty }({\mathbb {R}}^d;{\mathbb {R}}^d)\), i.e., for \(\theta = 1\), the Lipschitz truncation of \({\overline{z}} \in W^{1,p}({\mathbb {R}}^d;{\mathbb {R}}^d)\) in the sense of Theorem 3.3. Then, also using Remark 3.4, we get:
- (\(\alpha \)):
-
\(\Vert z_{\lambda }\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^d)}\le 1\),
- (\(\beta \)):
-
\(\Vert \nabla z_{\lambda }\Vert _{L^\infty ({\mathbb {R}}^d;{\mathbb {R}}^{d\times d})}\le c_{LT }\lambda \),
- (\(\gamma \)):
-
\(\vert \{ z_{\lambda }\ne {\overline{z}}\}\vert \le \vert \{ {\mathcal {M}}(\nabla {\overline{z}})> \lambda \}\vert \),
- (\(\delta \)):
-
\(\nabla z_{\lambda }=\nabla {\overline{z}}\) in \(\{ z_{\lambda }= {\overline{z}}\}\).
For \( z_{\lambda }|_{\Omega }\in W^{1,\infty }(\Omega ;{\mathbb {R}}^d)\) we obtain, in analogy with Lemma 3.2, i.e., introducing \(\smash {z_h^{\lambda } := (\gamma _h^\lambda )^{-1}I_{rt}z_{\lambda } \in {\mathcal {R}}T^0({\mathcal {T}}_h)}\), where we define \({\gamma _h^\lambda := 1+c_{rt}\Vert \nabla z_\lambda \Vert _{L^\infty (\Omega ;{\mathbb {R}}^{d\times d})}h}\), a dual quasi-interpolant \(\smash {z_h^{\lambda }\in {\mathcal {R}}T^0({\mathcal {T}}_h)}\) such that both \(\smash {\Vert \Pi _h z_h^{\lambda }\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)} \le 1}\) and
Then, on the basis of (\(\beta \)) and (3.4), we find that
Using (\(\beta \)), (\(\delta \)) and (3.3), also assuming that \({d^{\frac{1}{2}}c_{LT }\lambda > \Vert div ( z)\Vert _{L^\infty (\Omega )} + 2\Vert g\Vert _{L^\infty (\Omega )}}\), we further deduce that
Therefore, on combining (3.6)–(3.8), we observe that
For \( {c_p(z)}>0\) defined as in (3.5) and \(\lambda = h^{-s}\), where \(s>0\) is arbitrary, (3.9) yields
We have that \(s(p-2) = 1-s\) if and only if \(\smash {s=\frac{1}{p-1} = \frac{p'}{p}}\). Thus, for \({\lambda = h^{-s}}\), \(\smash {s = \frac{1}{p-1}}\) and \(\smash {{\tilde{z}}_h:=z_h^\lambda \in {\mathcal {R}}T^0({\mathcal {T}}_h)}\), from (3.10), it follows that both (Dp.1) and (Dp.2) hold. \(\square \)
Theorem 3.7
(Error estimate depending on the Sobolev regularity for \({\Gamma _N=\emptyset }\)) Let \(g \in L^\infty (\Omega )\), let \( z \in W^{1,p}(\Omega ;{\mathbb {R}}^d)\cap W^\infty (div ;\Omega )\), \(p \in \left[ 2,\infty \right) \), with \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)} \le 1\) be maximal for \({D:W^\infty (div ;\Omega )\rightarrow {\mathbb {R}}\cup \{-\infty \}}\), let \(u\in {\mathcal {A}} := \{{v \in BV(\Omega )\cap L^\infty (\Omega )}\!\mid v = 0\text { in }L^1(\partial \Omega )\}\) be minimal for \({I:{\mathcal {A}}\rightarrow {\mathbb {R}}}\), and let \(u_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) be minimal for \({I_h:{\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\rightarrow {\mathbb {R}}}\). Then, there holds
where \(c>0\) depends only on the quantities \(c_{cr}\), \(c_d\), \( {c_p(z)}\), \(\Vert u\Vert _{L^\infty (\Omega )}\) and \(\vert D u\vert (\Omega )\).
Proof
Combining the discrete strong coercivity of \(I_h\!:\!{\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\!\rightarrow \! {\mathbb {R}}\), i.e., (3.1), and the discrete weak duality principle \(I_h(u_h) \ge D_h({\tilde{z}}_h)\) for all \({\tilde{z}}_h \in {\mathcal {R}}T^0({\mathcal {T}}_h)\) (cf. (2.9)), we obtain for all \({\tilde{u}}_h\in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\) and \({\tilde{z}}_h\in {\mathcal {R}}T^0({\mathcal {T}}_h)\)
Resorting to Lemma 3.1, we obtain a function \({\tilde{u}}_h \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}})\) satisfying (P.1)–(P.4). In addition, Lemma 3.5 yields a vector field \({\tilde{z}}_h \in {\mathcal {R}}T^0({\mathcal {T}}_h)\) with (Dp.1) and (Dp.2). Combining (P.4), (Dp.2) and the strong duality principle \({I(u)=D(z)}\) (cf. (2.5)), we deduce from (3.11) that
where \(c_p\!>\!0\) is as in Lemma 3.5. Since \({{\tilde{u}}_h\!-\!\Pi _h{\tilde{u}}_h\!=\!\nabla _h {\tilde{u}}_h\!\cdot \!(id _{{\mathbb {R}}^d}\!-\!\Pi _hid _{{\mathbb {R}}^d})}\) in \({\mathcal {L}}^1({\mathcal {T}}_h)\), using (P.1), (P.3) and \(\smash {\Vert id _{{\mathbb {R}}^d}-\Pi _hid _{{\mathbb {R}}^d}\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le h}\), we find that
Using (P.2), (P.3), (L0.1) and proceeding as for (3.13), we further obtain that
Eventually, combining (3.12)–(3.14), we conclude the claimed error bound. \(\square \)
4 Error estimates for discontinuous dual solutions
In this section, we establish error estimates for the ROF model without explicitly assuming that the dual solution possesses Sobolev regularity. Recall that, in general, a solution of the dual ROF model only needs to satisfy \({z\!\in \! W^2_N(div ;\Omega )\!\cap \! L^\infty (\Omega ;{\mathbb {R}}^d)}\) with \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\!\le \! 1\). The following lemma gives general assumptions on the dual solution for which it is still possible to construct a suitable dual quasi-interpolant.
Lemma 4.1
(Dual quasi-interpolant for non–Sobolev vector fields) Let \({g\in L^2(\Omega )}\) and \(z\in W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\). If \(\Vert \Pi _h I_{rt}z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1+\kappa (h)\) for \(\kappa (h)\ge 0\), then the re-scaled vector field \(\smash {{\tilde{z}}_h:=\frac{1}{\gamma _h}I_{rt}z\in {\mathcal {R}}T^0_N({\mathcal {T}}_h)}\), where \(\gamma _h:=1+\kappa (h)>0\), has the following properties:
-
(D.1*)
\(\Vert \Pi _h{\tilde{z}}_h\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\).
-
(D.2*)
\(D_h({\tilde{z}}_h)\ge D( z)-\kappa (h)\Vert g\Vert _{L^2(\Omega )}\Vert div ( z)\Vert _{L^2(\Omega )}-\frac{1}{2}\Vert g-g_h\Vert _{L^2(\Omega )}^2\).
Proof
Claim (D.1*) is evident. Resorting to \(div (I_{rt}z)=\Pi _h(div (z))\) in \({\mathcal {L}}^0({\mathcal {T}}_h)\), we deduce that \(\smash {div ({\tilde{z}}_h)+g_h=\Pi _h(\frac{1}{\gamma _h}div (z)+g)}\) in \({\mathcal {L}}^0({\mathcal {T}}_h)\) and, hence, also using \(\Vert g-g_h\Vert _{L^2(\Omega )}^2\!=\!\Vert g\Vert _{L^2(\Omega )}^2\!-\! \Vert g_h\Vert _{L^2(\Omega )}^2\), \(I_{K_1(0)}(\Pi _h{\tilde{z}}_h)\!=\!0\) and Jensen’s inequality, that
Eventually, using \(\smash {\frac{1}{\gamma _h^2}}\le 1\) and \(\smash {1-\frac{1}{\gamma _h}\le \kappa (h)}\), we conclude that (D.2*) holds. \(\square \)
Theorem 4.2
(Error estimate for discontinuous dual solution) Let \(g\in L^\infty (\Omega )\), let \( z \in W^\infty _N(div ;\Omega )\) be maximal for \(D: W^\infty _N(div ;\Omega ) \rightarrow {\mathbb {R}}\cup \{-\infty \}\) with the same properties as in Lemma 4.1, let \(u \in BV(\Omega )\cap L^\infty (\Omega )\) minimal for \({I: BV(\Omega ) \cap L^2(\Omega ) \rightarrow {\mathbb {R}}}\), and let \(u_h \in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) minimal for \({I_h: {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h) \rightarrow {\mathbb {R}}}\). Then, we have that
where \(c>0\) depends only on the quantities \(c_{cr}\), \(c_d\), \(\Vert u\Vert _{L^\infty (\Omega )}\), and \(\vert D u\vert (\Omega )\).
Proof
Using the discrete strong coercivity of \(I_h:{\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\), i.e., (3.1), and the discrete weak duality principle \(I_h(u_h) \ge D_h({\tilde{z}}_h)\) for all \({\tilde{z}}_h \in {\mathcal {R}}T^0_N({\mathcal {T}}_h)\) (cf. (2.9)), we obtain for all \({\tilde{u}}_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) and \({\tilde{z}}_h\in {\mathcal {R}}T^0_N({\mathcal {T}}_h)\)
Resorting to Lemma 3.1, we obtain a function \({\tilde{u}}_h \in {\mathcal {S}}^{1,\textit{cr}} ({\mathcal {T}})\) satisfying (P.1)–(P.4). In addition, Lemma 4.1 yields a vector field \({\tilde{z}}_h\in {\mathcal {R}}T^0_N({\mathcal {T}}_h)\) with (D.1*) and (D.2*). Then, using (P.4), (D.2*) and the strong duality principle \({I(u)\!=\!D(z)}\) (cf. (2.5)), we deduce from (4.1) that
Hence, incorporating (3.13) and (3.14), we conclude the claimed error bound. \(\square \)
A sufficient condition for a solution to (2.4) to guarantee the quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}} )}\) is element-wise Lipschitz continuity. In addition, if a solution to (2.4) is only element-wise \(\alpha \)–Hölder continuous, it is, however, possible to derive the rate \(\smash {{\mathcal {O}}(h^{\frac{\alpha }{2}})}\).
Lemma 4.3
(Dual quasi-interpolant for element-wise \(\alpha \)–Hölder vector fields) Let \(g\in L^2(\Omega )\) and let \(z\in W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\) be such that \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\). Furthermore, assume that there exist constants \(\alpha \in \left[ 0,1\right] \) and \(c_{\alpha }>0\) such that for every \({T\in {\mathcal {T}}_h}\), it holds \({z|_T\in C^{0,\alpha }(T;{\mathbb {R}}^d)}\) with
for all \(x,y\!\in \! T\). Then, the assumptions in Lemma 4.1 are satisfied with \(\smash {\kappa (h)\!=\!{\mathcal {O}}(h^{\alpha })}\).
Remark 4.4
Lemma 4.3 is of particular interest if the discontinuity set \(J_z\) of a piece-wise regular (piece-wise Lipschitz or piece-wise \(\alpha \)–Hölder continuous) vector field \(z\!\in \! W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\) is resolved by the triangulation, i.e., \({J_z\!\subseteq \!\bigcup _{S\in {\mathcal {S}}_h}\!{S}}\).
Proof
(of Lemma 4.3) We need to check that \(\Vert \Pi _h I_{rt}z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\!\le \! 1+\kappa (h)\) for some \({\kappa (h) \ge 0}\) with \({\kappa (h) = {\mathcal {O}}(h^{\alpha })}\). Note that \(I_{rt}(z(x_T)) = z(x_T)\) in T for all \({T \in {\mathcal {T}}_h}\), which results from \(div (I_{rt}(z(x_T)))=\Pi _h(div (z(x_T)))=0\) in T for all \(T\in {\mathcal {T}}_h\). Using this, (RT.2), (4.2) and that \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\), we deduce that for all \(T\in {\mathcal {T}}_h\)
i.e., setting \(\kappa (h) := c_{rt}c_\alpha h^\alpha \), we conclude that \(\Vert \Pi _h I_{rt}z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)} \le 1+\kappa (h)\). \(\square \)
Theorem 4.5
(Error estimate for element-wise \(\alpha \)–Hölder dual solution) Let \(z\in W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\) be maximal for \(D\!\!:\!\!W^2_N(div ;\Omega )\cap L^\infty (\Omega ;{\mathbb {R}}^d)\rightarrow {\mathbb {R}}\cup \{-\infty \}\) with the same properties as in Lemma 4.3, let \(u\in BV(\Omega )\cap L^\infty (\Omega )\) minimal for \({I: BV(\Omega )\cap L^2(\Omega ) \rightarrow {\mathbb {R}}}\) and let \(u_h\in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h)\) minimal for \({I_h: {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_h) \rightarrow {\mathbb {R}}}\). Then, we have that
where \(c\!>\!0\) depends only on the quantities \(c_{cr}\), \(c_d\), \(c_\alpha \), \(\Vert u\Vert _{L^\infty (\Omega )}\), and \(\vert D u\vert (\Omega )\).
Proof
Follows from Theorem 4.2 by resorting to Lemma 4.3. \(\square \)
Remark 4.6
(Comparison of Theorem 3.7 and Theorem 4.5)
-
(i)
If \(\alpha = 1\), then Theorem 4.5 extends the results [10, Proposition 4.2] and [21, Sectioin 5.1.1] to the case of an existing element-wise Lipschitz continuous solution to (2.4).
-
(ii)
If \(p>d\) in Theorem 3.7, then \(z\in W^{1,p}(\Omega ;{\mathbb {R}}^d)\) satisfies \(z\in C^{0,\alpha }({\overline{\Omega }};{\mathbb {R}}^d)\) for \(\alpha =1-\frac{d}{p}\) by Sobolev’s embedding theorem [16, Corollary 9.14]. As a result, Theorem 4.5 in the particular case \(\Gamma _{\!N}\!=\!\emptyset \) is applicable and yields the rate \(\smash {{\mathcal {O}}( h^{ \frac{\alpha }{2}} )}\). On the other hand, Theorem 3.7 yields the slightly improved rate \(\smash {{\mathcal {O}}(h^{\smash {\frac{p-2}{2(p-1)}}})}\), which gives the impression that Theorem 3.7 is utterly superior to Theorem 4.5. Nevertheless, the major strength of Theorem 4.5—and equally of Lemma 4.3—is that it is also applicable when it is unclear whether a solution to (2.4) with Sobolev regularity is available. This allows us to justify analytically the quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) for the setting in Sect. 2.7 at least for the particular case that the discontinuity set \(J_z\) is resolved by the triangulation, i.e., \({J_z\!\subseteq \! \bigcup _{S\in {\mathcal {S}}_h}{\!S}}\), cf. Examples 5.2 and 5.3.
If the discontinuity set of a solution to (2.4) is not resolved by the triangulation, then, apparently, Theorem 4.5 does not apply. In this case, however, the following argument applies, which exploits that for \({g \in L^\infty (\Omega )}\), we have that \({div (z) \in L^\infty (\Omega )}\), which to some extent can serve as a substitute for \({\nabla z\in L^\infty (\Omega ;{\mathbb {R}}^{d\times d})}\).
Remark 4.7
(Optimal dual quasi-interpolant for non–Lipschitz vector fields) Let \(z\in W^\infty _N(div ;\Omega )\) be such that \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^d)}\le 1\). Furthermore, assume that there exists a constant \({\tilde{c}}_z>0\) such that for all \(T\in {\mathcal {T}}_h\), there exists some \({{\widetilde{x}}}_T\in T\) such that
For each \(T\in {\mathcal {T}}_h\), since \(I_{rt}z\in {\mathcal {R}}T^0_N({\mathcal {T}}_h)\subseteq {\mathcal {L}}^1({\mathcal {T}}_h)^d\), we have that
for all \(x\!\in \! T\). Thus, resorting to \({div (I_{rt}z)\!=\!\Pi _h(div (z))}\) in \({\mathcal {L}}^0({\mathcal {T}}_h)\), also using (4.4) and (L0.1) in (4.5) at \(x={{\widetilde{x}}}_T\in T\), we conclude that
i.e., we have that \(\Vert \Pi _hI_{rt}z\Vert _{L^\infty (T;{\mathbb {R}}^d)}\le 1+\big ({\tilde{c}}_z+d^{-1}\Vert div (z)\Vert _{L^\infty (\Omega )}\big )h\).
The following remark discusses particular sufficient conditions for (4.4) on a vector field \(z\in W^\infty _N(div ;\Omega )\) that is piece-wise Lipschitz continuous, such as, e.g., that its discontinuity set \(J_z\) is approximated by \({\mathcal {T}}_h\), \(h>0\), with rate \({\mathcal {O}}(h)\) or that \(\vert z\vert <1\) along \(J_z\) while, simultaneously, its jump \([\![z]\!]\) over \(J_z\) remains small. On the other hand, this remark finds that (4.4) cannot be expected, in general, for piece-wise Lipschitz continuous vector fields, even in generic situations.
Remark 4.8
(Sufficient conditions for (4.4)) Let \(d=2\) and \(z\in W^\infty _N(div ;\Omega )\) with \(\Vert z\Vert _{L^\infty (\Omega ;{\mathbb {R}}^2)}\le 1\) be piece-wise Lipschitz continuous, i.e., there exist open \(\Omega _i\subseteq \Omega \), \(i\!=\!1,\dots ,m\), \(m\!\in \! {\mathbb {N}}\), with \(z|_{\Omega _i}\!\in \! W^{1,\infty }(\Omega _i;{\mathbb {R}}^2)\) for all \(i\!=\!1,\dots ,m\) and \({{\overline{\Omega }}\!=\!\bigcup _{i=1}^m{\overline{\Omega _i}}}\). Next, we fix an arbitrary \(T\in {\mathcal {T}}_h\). Then, we need to distinguish two cases:
-
(i)
Assume that \(T\subseteq \overline{\Omega _i}\) for some \(i=1,\dots ,m\). Then, we deduce along the lines of the proof of (4.3) that
$$\begin{aligned} \vert (I_{rt}z)(x_T)\vert \le 1+ c_{rt} \Vert \nabla z\Vert _{L^\infty (\Omega _i;\mathbb {R}^{2\times 2})} h_T, \end{aligned}$$i.e., \(\vert (I_{rt}z)(x_T)\vert \!\le \! 1+c_zc_{rt}h_T\), where \(c_z\!:=\!\max _{i=1,\dots ,m}{\!\Vert \nabla ( z|_{\Omega _i} )\Vert _{L^\infty (\Omega _i;\mathbb {R}^{2\times 2})}}\).
-
(ii)
Assume that there exists an interface \(\gamma =\partial \Omega _a\cap \partial \Omega _b\) for some \({a,b=1,\dots ,m}\) such that \(int (T)\cap \gamma \ne \emptyset \).Footnote 8 As \(z|_{\smash {\Omega _a}}\in W^{1,\infty }(\Omega _a;\mathbb {R}^2)\) and \(z|_{\smash {\Omega _b}}\in W^{1,\infty }(\Omega _b;\mathbb {R}^2)\), without loss of generality, we may assume that \({\gamma \subseteq b_\gamma +\mathbb {R}t_\gamma }\) for some \(b_\gamma \in \mathbb {R}^2\) and \({t_\gamma \in \mathbb {S}^1}\). Next, fix \(x_\gamma \in \gamma \) and set \({z_a:=(z|_{\smash {\overline{\Omega _a}}})(x_\gamma ), z_b:=(z|_{\smash {\overline{\Omega _b}}})(x_\gamma )\in \mathbb {R}^2}\). Then, for \(i\in \{a,b\}\), it holds
$$\begin{aligned} \vert z_i-(z|_{\smash {\overline{\Omega _i}}})(x)\vert&\le \Vert \nabla (z|_{\smash {\Omega _i}})\Vert _{L^\infty (\Omega _i;\mathbb {R}^{2\times 2})}\vert x_{\gamma }-x\vert \le c_zh_T\;\;\text { for all }x\in T\cap \overline{\Omega _i}. \end{aligned}$$Furthermore, if \(n_\gamma \in \mathbb {S}^1\) denotes a unit normal vector to \(t_\gamma \in \mathbb {S}^1\), i.e., \({n_\gamma \cdot t_\gamma = 0}\), then, taking into account that \(z\in W^\infty _N(div ;\Omega )\), we find that \({z_a\cdot n_\gamma =z_b\cdot n_\gamma }\). Thus, if we define \(z_T(x):=z_a\) for \(x\in T\cap \overline{\Omega _a}\) and \(z_T(x):=z_b\) for \(x\in T\cap \overline{\Omega _b}\), cf. Fig. 1, (\(\alpha \)), then \(z_T\in W^{\infty }(div ;T)\) and, owing to (RT.2),
$$\begin{aligned} \begin{aligned} \Vert I_{rt}z_T-I_{rt}z\Vert _{L^\infty (T;\mathbb {R}^2)} \le c_{rt}\Vert z_T-z\Vert _{L^\infty (T;\mathbb {R}^2)}\le c_{rt}c_zh_T, \end{aligned} \end{aligned}$$i.e., we have that
$$\begin{aligned} \Vert I_{rt}z\Vert _{L^\infty (T;\mathbb {R}^2)}\le \Vert I_{rt}z_T\Vert _{L^\infty (T;\mathbb {R}^2)}+c_{rt}c_zh_T. \end{aligned}$$(4.6)As a result of (4.6), it is sufficient to prove \({\Vert I_{rt}z_T\Vert _{L^\infty (T;\mathbb {R}^2)}\le 1+\mathcal {O}(h)}\) to conclude that \(\Vert I_{rt}z\Vert _{L^\infty (T;\mathbb {R}^2)}\le 1+\mathcal {O}(h)\). Because, owing to Lemma 4.1 (ii), it holds
$$\begin{aligned} div (I_{rt}z_T)=\Pi _h(div (z_T))=0\quad \text { in }T, \end{aligned}$$where \(I_{rt}z_T:=\sum _{S\in \mathcal {S}_h;S\subseteq \partial T}{z_T\cdot n_S\psi _S}\), it even holds \({I_{rt}z_T\equiv const }\) in T. Next, we denote by \(S_1\in \mathcal {S}_h\) a side of \(T\in \mathcal {T}_h\) such that \(S_1\cap \gamma \ne \emptyset \) and by \(S_2\in \mathcal {S}_h\) the side of \({T\in \mathcal {T}_h}\) such that \({S_2\cap \gamma = \emptyset }\). Let \(n_1,n_2\in \mathbb {S}^1\) denote the corresponding unit normal vectors to \({S_1,S_2\in \mathcal {T}_h}\), resp., cf. Fig. 1, (\(\alpha \)). Then, it holds
$$\begin{aligned} \left. \begin{aligned} I_{rt}z_T\cdot n_1&= \int _{S_1}{z_T\cdot n_1\,d s}=\frac{\vert S_1\cap \Omega _b\vert }{\vert S_1\vert }z_b\cdot n_1+\frac{\vert S_1\cap \Omega _a\vert }{\vert S_1\vert }z_a\cdot n_1,\\ I_{rt}z_T\cdot n_2&= \int _{S_2}{z_T\cdot n_2\,d s}=z_b\cdot n_2. \end{aligned}\;\right\} \end{aligned}$$(4.7)Introducing \(\rho :=\vert S_1\cap \Omega _b\vert /\vert S_1\vert \in \left[ 0,1\right] \) as well as \({M_T:=(n_1,n_2)\in \mathbb {R}^{2\times 2}}\), also exploiting that \(z_a=z_b+((z_a-z_b)\cdot t_\gamma )t_\gamma \), where we used that \({z_a\cdot n_\gamma =z_b\cdot n_\gamma }\), the system (4.7) can be rewritten as
$$\begin{aligned} M^\top _T I_{rt}z_T= M^\top _T z_b+(1-\rho )((z_a-z_b)\cdot t_\gamma )(t_\gamma \cdot n_1)e_1, \end{aligned}$$i.e., since \(M_T^\top \in \mathbb {R}^{2\times 2}\) is a regular matrix, we find that
$$\begin{aligned} I_{rt}z_T= z_b+(1-\rho )((z_a-z_b)\cdot t_\gamma )(t_\gamma \cdot n_1)M_T^{-\top }e_1. \end{aligned}$$(4.8)
Resorting to the formula (4.8), we can derive special cases that imply (4.4):
-
(ii.a)
If \(t_\gamma \cdot n_1=\mathcal {O}(h)\), i.e., \((b_\gamma +\mathbb {R}t_\gamma )\cap T\) approximates \(S_1\) with rate \(\mathcal {O}(h)\), cf. Fig. 1, (\(\beta \)), then \( \vert I_{rt}z_T\vert \le \vert z_b\vert +\mathcal {O}(h)\le 1+\mathcal {O}(h)\).
-
(ii.b)
If \(1-\rho =\mathcal {O}(h)\), i.e., \(S_1\cap \Omega _b\) approximates \(S_1\) with rate \(\mathcal {O}(h)\), cf. Fig. 1, (\(\gamma \)), then \( \vert I_{rt}z_T\vert \le \vert z_b\vert +\mathcal {O}(h)\le 1+\mathcal {O}(h)\).
Apparently, (ii.a) and (ii.b) describe the particular case in which the discontinuity set \(J_z\) is not resolved by the triangulation but approximated with rate \(\mathcal {O}(h)\).
-
(ii.c)
If we have that both \(\vert z_b\vert <1 \) and \((z_a-z_b)\cdot t_\gamma \) is sufficiently small, i.e., such that \( \vert (1-\rho )((z_a-z_b)\cdot t_\gamma )M^{-\top }_T(t_\gamma \cdot n_1)e_1\vert \le 1-\vert z_b\vert +\mathcal {O}(h)\), then \( \vert I_{rt}z_T\vert \le \vert z_b\vert +1-\vert z_b\vert +\mathcal {O}(h)= 1+\mathcal {O}(h)\).
-
(ii.d)
If T is nearly right-angled, so that \(M_T\) is approximately an orthogonal matrix, i.e., \( M_T^{-\top } = M_T+\mathcal {O}(h)\), and \({t_\gamma =\pm n_1+\mathcal {O}(h)}\), then, using that \(z_a\cdot n_2=z_b\cdot n_2+\mathcal {O}(h)\) because \(n_\gamma = \pm n_2+\mathcal {O}(h)\), we deduce that \(z_b=(z_b\cdot n_1)n_1+(1-\rho )(z_a\cdot n_2)n_2+\rho (z_b\cdot n_2)n_2+\mathcal {O}(h)\) and, thus, that
$$\begin{aligned} I_{rt}z_T&=z_b+(1-\rho )((z_a-z_b)\cdot n_1)n_1+\mathcal {O}(h)\\ {}&=\rho ((z_b\cdot n_1)n_1+\rho (z_b\cdot n_2)n_2)\\ {}&\quad +(1-\rho )((z_a\cdot n_1)n_1+(z_a\cdot n_2)n_2)+\mathcal {O}(h)\\ {}&=(1-\rho )z_a+\rho z_b+\mathcal {O}(h), \end{aligned}$$which implies that \(\vert I_{rt}z_T\vert \le (1-\rho )\vert z_a\vert +\rho \vert z_b\vert +\mathcal {O}(h)\le 1+\mathcal {O}(h)\).
More generally, the sub-cases (ii.a)–(ii.d) can occur in combination so that the conclusion holds under significantly weaker conditions on the individual factors. On the other hand, the formula (4.8), simultaneously, demonstrates that \( \Vert I_{rt}z_T\Vert _{L^\infty (T;\mathbb {R}^2)}\le 1+\mathcal {O}(h) \) and, therefore, also \({\Vert I_{rt}z\Vert _{L^\infty (T;\mathbb {R}^2)}\le 1+\mathcal {O}(h)}\) cannot be expected in general, even in generic situations.
5 Numerical experiments
In this section, we verify the theoretical findings of Sect. 4 via numerical experiments. To compare approximations to an exact solution, we impose Dirichlet boundary conditions on \(\Gamma _D = \partial \Omega \), though an existence theory is difficult to establish, in general. However, the error estimates derived in Sect. 4 carry over verbatimly with \(\Gamma _N=\emptyset \) provided that a minimizer exists.
All experiments were conducted using the finite element software FEniCS, cf. [30]. All graphics are generated using the Matplotlib library, cf. [28].
5.1 Experimental convergence rates
All computations are based on using the regularized discrete ROF functional, i.e., for \(\varepsilon >0\) and \(g\in L^2(\Omega )\), the functional \(I^\varepsilon _h:{\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\rightarrow {\mathbb {R}}\), defined by
for all \(v_h\in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\), where \(\vert \cdot \vert _\varepsilon \in C^1({\mathbb {R}}^d)\) is the regularized modulus, defined by \(\vert a\vert _\varepsilon :=(\vert a\vert ^2 +\varepsilon ^2)^{\frac{1}{2}}\) for all \(a \in {\mathbb {R}}^d\) and \(\varepsilon > 0\). Based on \(0 \le \vert a\vert _\varepsilon - \vert a\vert \le \varepsilon \) for all \(a \in {\mathbb {R}}^d\) and \(\varepsilon > 0\), for the minima \({u_h,u_h^\varepsilon \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)}\) of \({I_h,I_h^\varepsilon : {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h) \rightarrow {\mathbb {R}}}\), resp., it holds
Thus, in order to bound the error \(\Vert u-\Pi _hu_h\Vert _{L^2(\Omega )} \), it suffices to determine the error \(\Vert u-\Pi _hu_h^\varepsilon \Vert _{L^2(\Omega )}\), e.g., for \(\varepsilon =h\). The iterative minimization of \(\smash {I^h_h:{\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\rightarrow {\mathbb {R}}}\), i.e., for \(\varepsilon \!=\!h\), is realized using a semi-implicit discretized \(L^2\)–gradient flow from [11], see also [9, Section 5].
Algorithm 5.1
(Semi-implicit discretized \(L^2\)–gradient flow) Let \(g_h\in {\mathcal {L}}^0({\mathcal {T}}_h)\) and choose \(\tau ,\varepsilon _{stop}^h > 0\). Moreover, let \(u^0_h \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\) and set \(k = 1\). Then, for \({k \ge 1}\):
-
(i)
Compute the iterate \(\smash {u_h^k \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)}\) such that for every \(\smash {v_h \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)}\), it holds
$$\begin{aligned} \left( d_tu_h^k,v_h\right) _{L^2(\Omega )}+\left( \frac{\nabla _hu_h^k}{\left| \nabla _hu_h^{k-1}\right| _h},\nabla _hv_h \right) _{\! \! L^2(\Omega ;{\mathbb {R}}^d)}\!+\alpha \left( \Pi _hu_h^k-g_h,\Pi _hv_h\right) _{L^2(\Omega )}=0, \end{aligned}$$where \(d_tu_h^k:=\frac{1}{\tau }(u_h^k-u_h^{k-1})\) denotes the backward difference quotient.
-
(ii)
Compute the residual \(\smash {r_h^k \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)}\) such that for every \(\smash {v_h \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)}\), it holds
$$\begin{aligned} \left( r_h^k,v_h\right) _{L^2(\Omega )}=\left( \frac{\nabla _hu_h^k}{\left| \nabla _hu_h^{k}\right| _h},\nabla _hv_h \right) _{\! \! L^2(\Omega ;{\mathbb {R}}^d)}\!+\alpha \left( \Pi _hu_h^k-g_h,\Pi _hv_h\right) _{L^2(\Omega )}, \end{aligned}$$Stop if \(\Vert r_h^k\Vert _{L^2(\Omega )}\le \varepsilon _{stop}^h\); otherwise, increase \(k\!\rightarrow \! k+1\) and continue with (i).
Appealing to [10, Remark 5.5], the iterates \(u_h^k \in {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\), \(k \in {\mathbb {N}}\), and residuals \(r_h^k\!\in \! {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)\), \(k\!\in \! {\mathbb {N}}\), generated by Algorithm 5.1, and the minimizer \({u_h^h\!\in \! {\mathcal {S}}^{1,\textit{cr}}_D({\mathcal {T}}_h)}\) of (5.1) for \(\varepsilon =h\) satisfy
As a consequence, if we choose as a stopping criteria that \(\smash {\Vert r_h^k\Vert _{L^2(\Omega )}\le \varepsilon _{\textit{stop}}^h:= h^{\frac{1}{2}}}\), then, owing to (5.2), \(\smash {\Vert \Pi _h(u_h-u_h^k)\Vert _{L^2(\Omega )}\!\le \! \smash {(2\!+\!\frac{2}{\alpha }\vert \Omega \vert ) h^{\frac{1}{2}}}}\). Thus, to bound the error \(\smash {\Vert u-\Pi _hu_h\Vert _{L^2(\Omega )}} \) experimentally, it is sufficient to compute \(\smash {\Vert u-\Pi _hu_h^k\Vert _{L^2(\Omega )}} \).
The energy stability of the semi-implicit scheme established in [10, 11] shows that \(d_t u_h^k \rightarrow 0\) in \(L^2(\Omega )\) \((k \rightarrow \infty )\), which, in turn, implies \( r_h^k \rightarrow 0\) in \(L^2(\Omega )\) \({(k \rightarrow \infty )}\) and, hence, that Algorithm 5.1 terminates within a finite number of iterations, so that employing the h–independent step-size \(\tau = 1\) is reasonable.
Example 5.2
(Two disks problem) Let \(\Omega =(-1,1)^2\subseteq {\mathbb {R}}^2\), \(r=0.4\), \(\alpha =10\), and \({\tilde{g}} := g\circ \Phi \in BV(\Omega )\cap L^\infty (\Omega )\), where \(g:=\chi _{B_r^2(re_1)}-\chi _{B_r^2(-re_1)}\in BV(\Omega )\cap L^\infty (\Omega )\) and for some angle \(\phi \in [0,2\pi ]\) and some vector \(b_\gamma =(b_1,b_2)^\top \in {\mathbb {R}}^2\),
for all \(x = (x_1,x_2)^\top \!\!\in {\mathbb {R}}^2\), i.e., \(\Phi : {\mathbb {R}}^2\!\rightarrow \! {\mathbb {R}}^2\) performs a rotation by \(\phi \) and a shift by b. The same argumentation as in the proof of Proposition 2.1 demonstrates that the corresponding primal solution is given via \({\tilde{u}}:=u\circ \Phi =(1-\frac{2}{\alpha r}){\tilde{g}}\in BV(\Omega )\cap L^\infty (\Omega )\), where \(u:=(1-\frac{2}{\alpha r})g\in BV(\Omega )\cap L^\infty (\Omega )\), cf. Proposition 2.1.
For \(z\in W^{\infty }(div ;\Omega )\) defined as in Proposition 2.4, we define the vector field \({\tilde{z}}:=\det (D\Phi )(D\Phi )^{-1}z\circ \Phi =(D\Phi )^{-1}z\circ \Phi \in W^{\infty }(div ;\Omega )\). Then, resorting to properties of the contra-variant Piola transform, cf. [14, (2.1.71)], we find that
We define the decomposition \(\Omega ^+_\Phi :=\Omega \cap \Phi ({\mathbb {R}}_{>0}\times {\mathbb {R}})\) and \(\Omega ^-_\Phi :=\Omega \cap \Phi ({\mathbb {R}}_{<0}\times {\mathbb {R}})\). Then, using that \({\tilde{u}}=0\) continuously on \(b_\gamma +{\mathbb {R}}t_\gamma \cap \Omega \), where \({t_\gamma =(-\sin (\phi ),\cos (\phi ))^\top }\!\), and the transformation theorem, we further obtain that
where we used in the last equality sign that \(supp ({\tilde{u}})\subseteq \Phi ^{-1}(\Omega )\cap \Omega \). Consequently, if we combine (5.5) and (5.6) and refer to the optimality conditions (2.6), then we find that \({\tilde{z}}\in W^{\infty }(div ;\Omega )\) is a dual solution to \({{\tilde{u}}\in BV(\Omega )\cap L^\infty (\Omega )}\). Apparently, \({\tilde{z}}\in W^{\infty }(div ;\Omega )\) is piece-wise Lipschitz continuous in the sense of Remark 4.8 and its jump set is given via \(J_{{\tilde{z}}}=b_\gamma +{\mathbb {R}} t_\gamma \). As a consequence, if for every \(T\in {\mathcal {T}}_h\), either of the cases (ii.a)–(ii.d) in Remark 4.8 is satisfied, then the quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) is guaranteed by Remark 4.8, Lemma 4.7, Lemma 4.1 and Theorem 4.2.
Example 5.3
(Four disks problem) Let \(\Omega =(-1,1)^2\subseteq {\mathbb {R}}^2\), \({r=0.4}\), \({\alpha =10}\), and
The same argumentation as for the proof of Proposition 2.1 shows that a minimum of (2.3) is given via \({u:=(1-\frac{2}{r\alpha })g\in BV(\Omega )\cap L^\infty (\Omega )}\). A straightforward adaption of the proof of Corollary 2.2 implies that any dual solution \({z \in W^\infty (div ;\Omega )}\) is not \(\theta \)–Hölder continuous at \({x=\pm r e_1}\) and \({x=\pm r e_2}\) if \({\theta >\frac{1}{2}}\). Apart from that, arguing as in the proof of Proposition 2.4, we find that an example of a dual solution \({\overline{z}}\in W^\infty (div ;\Omega )\) is given via \({\overline{z}}(x):= \pm z(x\mp re_2)\) if \(\pm x_2\ge 0\) for all \(x=(x_1,x_2)^\top \in \Omega \), where \(z\in W^\infty (div ;\Omega )\) is defined as in Proposition 2.4. In addition, if \(\Phi : {\mathbb {R}}^2 \rightarrow {\mathbb {R}}^2\) is defined as in Example 5.2, then for \({{\tilde{g}} := g\circ \Phi \in BV(\Omega ) \cap L^\infty (\Omega )}\), the primal solution is given via \({{\tilde{u}}:=u\circ \Phi \in BV(\Omega )\cap L^\infty (\Omega )}\) and a dual solution is given via \({\tilde{z}}:=(D\Phi )^{-1}{\overline{z}}\circ \Phi \in W^\infty (div ;\Omega )\). Apparently, \({\tilde{z}}\in W^\infty (div ;\Omega )\) is piece-wise Lipschitz continuous in the sense of Remark 4.8 and its jump set is given via \(J_{{\tilde{z}}}\!=\! b_\gamma +{\mathbb {R}}t_\gamma +{\mathbb {R}}n_\gamma \), where \({t_\gamma \!=\!(\!-\!\sin (\phi ),\cos (\phi ))^\top \!\!}\) and \({n_\gamma \!=\!(\cos (\phi ),\sin (\phi ))^\top \!\!}\). As a consequence, if for every \(T\!\in \! {\mathcal {T}}_h\), either of the cases (ii.a)–(ii.d) in Remark 4.8 is satisfied, then the quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) is guaranteed by Remark 4.8, Lemma 4.7, Lemma 4.1 and Theorem 4.2.
The experimental convergence rates in Fig. 2 are obtained on k–times red-refined triangulations \({\mathcal {T}}_{h_k}\), \(k=1,\dots ,9\), of an initial triangulation \({\mathcal {T}}_{h_0}\) with two elements, i.e., \(h_k=h_0 2^{-k}\) and \(\varepsilon _{stop}^{h_k}=\smash {h_k^{\frac{1}{2}}}\) for every \({k=1,\dots ,9}\). In addition, for a simple implementation, we employ \({\tilde{g}}_{h_k}\in {\mathcal {L}}^0({\mathcal {T}}_{h_k})\), defined by , where \(x_{{\mathcal {T}}_{h_k}}|_T:=x_T\) for all \(T\in {\mathcal {T}}_{h_k}\), instead of \({g_{h_k}:=\Pi _{h_k}{\tilde{g}}\in {\mathcal {L}}^0({\mathcal {T}}_{h_k})}\). However, since for each input data \({\tilde{g}}\in BV(\Omega )\cap L^\infty (\Omega )\) considered in this section, it holds \(\Vert {\tilde{g}}-{\tilde{g}}_{h_k}\Vert _{L^1(\Omega )}\!\le \! c h_k\vert \partial B_r^2(0)\vert \), the error estimate remains valid. The linear systems merging in each iterations of Algorithm 5.1 are solved using PETSc’s preconditioned conjugate gradient method with an incomplete LU factorization, cf. [6]. Figure 2 contains logarithmic plots for the experimental convergence rates of
versus the total number of vertices \(\smash {N_k=(2^k+1)^2\sim h_k^{-2}}\) for \({k=3,\dots ,9}\). We find that the errors (5.7) converge at the quasi-optimal convergence rate \(\smash {{\mathcal {O}}( h^{\frac{1}{2}} )}\). This behavior is reported for both examples, i.e., Examples 5.2 and 5.3, for \(\phi = 0.0\) and \(b_\gamma = (0.0,0.0)^\top \) as well as for \(\phi = \frac{7\pi }{18}\) and \({b_\gamma = (0.1,0.0)^\top }\). Recall that for \(\phi = 0.0\) and \(b_\gamma = (0.0,0.0)^\top \), the quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) is analytically guaranteed in both examples (cf. Examples 5.2 and 5.3). Apart from that, we also could report the quasi-optimal rate \(\smash {{\mathcal {O}}( h^{\frac{1}{2}} )}\) for \(d=3\), a uniform triangulation of \(\Omega =(-1,1)^3\) and \(g\in L^\infty (\Omega )\cap BV(\Omega )\) given via two or four touching balls, with several rotations and shifts, for which no Lipschitz continuous dual solution exists.
In Fig. 3, the numerical solution \(u_{h_5} \in {\mathcal {S}}^{1,\textit{cr}}({\mathcal {T}}_{h_5})\) obtained in Example 5.3 and its \(L^2\)–projection \(\Pi _{h_5}u_{h_5}\!\in \! {\mathcal {L}}^0({\mathcal {T}}_{h_5})\) are displayed for \({\phi \!=\!0.0}\) and \({b_\gamma \!=\!(0.0,0.0)^\top \!}\). Large gradients occur near the contact points of the disks, the midpoint values do not, however, show artifacts. In Fig. 4, the \(L^2\)–projection \(\Pi _{h_5}z_{h_5}\in {\mathcal {L}}^0({\mathcal {T}}_{h_5})^2\) of the discrete dual solution \({z_{h_5}\!:=\!\nabla _{h_5} u_{h_5}\vert \nabla _{h_5} u_{h_5}\vert _{h_5}^{-1}\!+\!\frac{\alpha }{2}\Pi _{h_5}(u_{h_5}-g)(id _{{\mathbb {R}}^2}\!-\!\Pi _{h_5}id _{{\mathbb {R}}^2})}\) \(\in \! {\mathcal {R}}T^0({\mathcal {T}}_{h_5})\) with respect to the regularized ROF functional (5.1) (cf. [13, Section 5]) is displayed for \({\phi =0.0}\) and \({b_\gamma =(0.0,0.0)^\top }\).
5.2 Experimental verification of condition (4.4)
In this section, we examine whether the dual solutions given in Example 5.2 for every \({\phi \in [0,2\pi ]}\) and \(b_\gamma \in {\mathbb {R}}^2\) comply with condition (4.4) in Lemma 4.7, which, in view of Lemma 4.1 and Theorem 4.2 yields a guarantee for the quasi-optimal convergence rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\). If we compute the quantities
where \({\tilde{z}}\in W^\infty (div ;\Omega )\) is defined as in Example 5.2, then we find that for \(\phi =0.0\) and \(b_\gamma =(0.0,0.0)^\top \), \(\phi =\frac{\pi }{2}\) and \(b_\gamma =(0.0,0.1)^\top \), \(\phi =0.0\) and \(b_\gamma =(0.1,0.0)^\top \), and \(\phi =-\frac{\pi }{4}\) and \(b_\gamma =(0.0,0.0)^\top \), there exists a constant \(c_z>0\)—presumably, one has that \(c_z=1\)—such that for \(k=1,\dots ,8\), there holds
These results confirm the findings in Remark 4.8 as they fall within one of the cases (ii.a)–(ii.d). Apart from that, for \(\phi =\frac{\pi }{4}\) and \(b_\gamma =(0.0,0.0)^\top \) as well as for \(\phi =\frac{7\pi }{18}\) and \(b_\gamma =(0.0,0.0)^\top \), we cannot report the existence of a constant \(c_z>0\) such that (5.9) holds. This behavior can also be easily predicted analytically by resorting to the formula (4.8). All results can be found in Fig. 5, which displays the quantities (5.8) versus the total number of vertices \({N_k\!=\!(2k+1)^2\!\sim \! h_k^{-2}}\) for \({k\!= \! 1,\dots ,8}\).
Possible explanations for the observed quasi-optimal rate \(\smash {{\mathcal {O}}(h^{\frac{1}{2}})}\) for \(\phi =\frac{\pi }{4}\) and \(b_\gamma =(0.0,0.0)^\top \) as well as for \(\phi =\frac{7\pi }{18}\) and \(b_\gamma =(0.0,0.0)^\top \), even though (5.9) could not be reported, might be that this violation is merely pre-asymptotic or occurs only along the interface \((b_\gamma +{\mathbb {R}}t_\gamma )\cap \Omega \) (the latter, we observed experimentally), that the proofs presented are still sub-optimal, or that there exists an alternative dual solution for which (5.9) can be reported.
Notes
Here, \(W^{\smash {-\frac{1}{p},p}}(\Gamma _N):=\left( W^{\smash {1-\frac{1}{p'},p'}}(\Gamma _N)\right) ^*\) and \(W^{\smash {-\frac{1}{p},p}}(\Omega ):=\left( W^{\smash {1-\frac{1}{p'},p'}}(\Omega )\right) ^*\).
Here, \(C_c^\infty (\Omega ;{\mathbb {R}}^d)\) denotes the space of smooth and in \(\Omega \) compactly supported vector fields.
Here, for every \(S\in {\mathcal {S}}_h\setminus \partial \Omega \), \(\llbracket {v_h}\rrbracket _S:=v_h|_{T_+}-v_h|_{T_-}\) on S, where \(T_+, T_-\in {\mathcal {T}}_h\) satisfy \(\partial T_+\cap \partial T_-=S\), and for every \(S\in {\mathcal {S}}_h\cap \partial \Omega \), \(\llbracket {v_h}\rrbracket _S:=v_h|_T\) on S, where \(T\in {\mathcal {T}}_h\) satisfies \({S\subseteq \partial T}\).
Here, for every \(S\in {\mathcal {S}}_h{\setminus }\partial \Omega \), \(\llbracket {y_h\cdot n}\rrbracket _S:=\smash {y_h|_{T_+}\!\cdot n_{T_+}+y_h|_{T_-}\!\cdot n_{T_-}}\) on S, where \({T_+, T_-\in {\mathcal {T}}_h}\) satisfy \(\smash {\partial T_+\cap \partial T_-=S}\) and for every \(T\in {\mathcal {T}}_h\), \(\smash {n_T:\partial T\rightarrow {\mathbb {S}}^{d-1}}\) denotes the outward unit normal vector field to T, and for every \(\smash {S\in {\mathcal {S}}_h\cap \partial \Omega }\), \(\smash {\llbracket {y_h\cdot n}\rrbracket _S:=\smash {y_h|_T\cdot n}}\) on S, where \(T\in {\mathcal {T}}_h\) satisfies \(S\subseteq \partial T\) and \(\smash {n:\partial \Omega \rightarrow {\mathbb {S}}^{d-1}}\) denotes the outward unit normal vector field to \(\Omega \).
For every \(i=1,\dots ,d\), we denote by \(e_i\in {\mathbb {S}}^{d-1}\), the i–th. unit vector.
Here, \({\mathcal {M}}\!:\!L^p({\mathbb {R}}^d;{\mathbb {R}}^l)\!\rightarrow \! L^p({\mathbb {R}}^d;{\mathbb {R}}^l)\), \(d,l\in {\mathbb {N}}\), defined by for a.e. \(x\in {\mathbb {R}}^d\) and all \(f\in L^p({\mathbb {R}}^d;{\mathbb {R}}^l)\), denotes the Hardy–Littlewood–Maximal operator.
More precisely, one has \(c_{{\mathcal {M}}}\!=\!2 \big (\frac{p}{p-1}\big )^{\frac{1}{p}}5^{\frac{d}{p}}\), implying the limit behavior \(c_{{\mathcal {M}}}\!\rightarrow \! 2\) for \((p \!\rightarrow \! \infty )\).
Apparently, we should also take into account the case in which \(T\in \mathcal {T}_h\) is intersected by two or more interfaces. However, for the benefit of readability, we limit ourselves to this simplified case.
References
Acerbi, E., Fusco, N.: Semicontinuity problems in the calculus of variations. Arch. Rational Mech. Anal. 86, 125–145 (1984). https://doi.org/10.1007/BF00275731
Acerbi, E., Fusco, N.: A regularity theorem for minimizers of quasiconvex integrals. Arch. Ration. Mech. Anal. 99, 261–281 (1987). https://doi.org/10.1007/BF00284509
Acerbi, E., Fusco, N.: An approximation lemma for \(W^{1,p}\) functions. In: Material instabilities in continuum mechanics (Edinburgh, 1985–1986) Oxford Sci. Publ., pp. 1–5. Oxford University Press, New York
Ambrosio, L., Fusco, N., Pallara, D.: Functions of bounded variation and free discontinuity problems. The Clarendon Press, Oxford University Press, New York (2000)
Attouch, H., Buttazzo, G., Michaille, G.: Variational analysis in Sobolev and BV spaces, second ed., MOS-SIAM series on optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2014). https://doi.org/10.1137/1.9781611973488
Balay, S.: et. al. , PETSc Web page, https://www.mcs.anl.gov/petsc, (2019)
Bartels, S.: Total variation minimization with finite elements: convergence and iterative solution. SIAM J. Numer. Anal. 50, 1162–1180 (2012). https://doi.org/10.1137/11083277X
Bartels, S.: Numerical methods for nonlinear partial differential equations, Springer series in computational mathematics 47, Springer. Cham (2015). https://doi.org/10.1007/978-3-319-13797-1
Bartels, S.: Error estimates for a class of discontinuous Galerkin methods for nonsmooth problems via convex duality relations. Math. Comput. 90, 2579–2602 (2021). https://doi.org/10.1090/mcom/3656
Bartels, S.: Nonconforming discretizations of convex minimization problems and precise relations to mixed methods. Comput. Math. Appl. 93, 214–229 (2021). https://doi.org/10.1016/j.camwa.2021.04.014
Bartels, S., Diening, L., Nochetto, R.H.: Unconditional stability of semi-implicit discretizations of singular flows. SIAM J. Numer. Anal. 56, 1896–1914 (2018). https://doi.org/10.1137/17M1159166
Bartels, S., Nochetto, R.H., Salgado, A.J.: A total variation diminishing interpolation operator and applications. Math. Comp. 84, 2569–2587 (2015). https://doi.org/10.1090/mcom/2942
Bartels, S., Tovey, R., Wassmer, F.: Singular solutions, graded meshes, and adaptivity for total-variation regularized minimization problems. ESAIM Math. Model. Numer. Anal. 56(6), 1871–1888 (2022)
Boffi, D., Brezzi, F., Fortin, M.: Mixed finite element methods and applications, Springer series in computational mathematics 44, Springer. Heidelberg (2013). https://doi.org/10.1007/978-3-642-36519-5
Brenner, S.C., Scott, L.R.: The mathematical theory of finite element methods, third ed., texts in applied mathematics, vol. 15. Springer, New York (2008). https://doi.org/10.1007/978-0-387-75934-0
Brézis, H. Function analysis, Sobolev spaces and partial differential equations (2010). https://doi.org/10.1007/978-0-387-70914-7
Caselles, V., Chambolle, A., Novaga, M.: The discontinuity set of solutions of the TV denoising problem and some extensions. Multiscale Model. Simul. 6, 879–894 (2007). https://doi.org/10.1137/070683003
Chambolle, A., Caselles, V., Cremers, D., Novaga, M., Pock, T.: Theoretical foundations and numerical methods for sparse recovery. In: Radon series on computational and applied mathematics, vol. 9. Walter de Gruyter GmbH & Co. KG, Berlin (2010). Papers from the Summer School held in Linz, August 31–September 4, (2009). https://doi.org/10.1515/9783110226157
Chambolle, A., Levine, S.E., Lucier, B.J.: An upwind finite-difference method for total variation-based image smoothing. SIAM J. Imaging Sci. 4, 277–299 (2011). https://doi.org/10.1137/090752754
Chambolle, A., Lions, P.-L.: Image recovery via total variation minimization and related problems. Numer. Math. 76, 167–188 (1997). https://doi.org/10.1007/s002110050258
Chambolle, A., Pock, T.: Crouzeix-Raviart approximation of the total variation on simplicial meshes. J. Math. Imaging Vis. 62, 872–899 (2020). https://doi.org/10.1007/s10851-019-00939-3
Crouzeix, M., Raviart, P.A.: Conforming and nonconforming finite element methods for solving the stationary Stokes equations. I,. Rev. Française Automat. Informat. Recherche Opér. Sér. Rouge 7, 33–75 (1973)
Diening, L., Málek, J., Steinhauer, M.: On Lipschitz truncations of Sobolev functions (with variable exponent) and their selected applications, ESAIM: Control. Optim. Calc. Var. 14, 211–232 (2008). https://doi.org/10.1051/cocv:2007049
Ern, A., Guermond, J.-L.: Theory and practice of finite elements, applied mathematical sciences, vol. 159. Springer-Verlag, New York (2004). https://doi.org/10.1007/978-1-4757-4355-5
Ern, A., Guermond, J.L.: Finite Elements I: Approximation and Interpolation, texts in applied mathematics, no. 1. Springer International Publishing, (2021). https://doi.org/10.1007/978-3-030-56341-7
Herrmann, M., Herzog, R., Schmidt, S., Vidal-Núñez, J., Wachsmuth, G.: Discrete total variation with finite elements and applications to imaging. J. Math. Imaging Vis. 61, 411–431 (2019). https://doi.org/10.1007/s10851-018-0852-7
Hintermüller, M., Kunisch, K.: Total bounded variation regularization as a bilaterally constrained optimization problem. SIAM J. Appl. Math. 64, 1311–1333 (2004). https://doi.org/10.1137/S0036139903422784
Hunter, J.D.: Matplotlib: a 2d graphics environment. Comput. Sci. Eng. 9, 90–95 (2007). https://doi.org/10.1109/MCSE.2007.55
Lai, M.-J., MatambaMessi, L.: Piecewise linear approximation of the continuous Rudin-Osher-Fatemi model for image denoising. SIAM J. Numer. Anal. 50, 2446–2466 (2012). https://doi.org/10.1137/110854539
Logg, A., Wells, G.N.: Dolfin: automated finite element computing. ACM Trans. Math. Softw. 10(1145/1731022), 1731030 (2010)
Malý, J., Ziemer, W.P.: Fine regularity of solutions of elliptic partial differential equations, mathematical surveys and monographs, vol. 51. American Mathematical Society, Providence, RI (1997). https://doi.org/10.1090/surv/051
Raviart,P.-A., Thomas, J.M.: A mixed finite element method for 2nd order elliptic problems. In: Mathematical aspects of finite element methods (Proc. Conf., Consiglio Naz. delle Ricerche (C.N.R.), Rome, 1975), Vol. 606, pp. 292–315. Lecture Notes in Mathematics (1977)
Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms, vol. 60. In: Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991), pp. 259–268 (1992). https://doi.org/10.1016/0167-2789(92)90242-F
Wang, J., Lucier, B.J.: Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing. SIAM J. Numer. Anal. 49, 845–868 (2011). https://doi.org/10.1137/090769594
Funding
Open Access funding enabled and organized by Projekt DEAL.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Bartels, S., Kaltenbach, A. Error estimates for total-variation regularized minimization problems with singular dual solutions. Numer. Math. 152, 881–906 (2022). https://doi.org/10.1007/s00211-022-01324-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-022-01324-w