Non-local Functionals Related to the Total Variation and Connections with Image Processing

We present new results concerning the approximation of the total variation, \(\int _{\Omega } |\nabla u|\), of a function u by non-local, non-convex functionals of the form

as \(\delta \rightarrow 0\), where \(\Omega \) is a domain in \(\mathbb {R}^d\) and \(\varphi : [0, + \infty ) \rightarrow [0, + \infty )\) is a non-decreasing function satisfying some appropriate conditions. The mode of convergence is extremely delicate and numerous problems remain open. De Giorgi’s concept of \(\Gamma \)-convergence illuminates the situation, but also introduces mysterious novelties. The original motivation of our work comes from Image Processing.

1. In [33], this result is stated for balls but a similar argument works for cubes with arbitrary orientations.

2. In [33], this result is stated for balls but a similar argument works for cubes with arbitrary orientations.

We are extremely grateful to J. Bourgain for sharing fruitful ideas which led to the joint work [10] with the second author. Some of the techniques developed in [10] served as a source of inspiration for many subsequent works. The first author (H.B.) warmly thanks R. Kimmel and J. M. Morel for useful discussions concerning Image Processing.

Authors and Affiliations

1. Department of Mathematics, Hill Center, Busch Campus, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ, 08854, USA

   Haïm Brezis

2. Departments of Mathematics and Computer Science, Technion, Israel Institute of Technology, 32.000, Haifa, Israel

   Haïm Brezis

3. Laboratoire Jacques-Louis Lions UPMC, 4 Place Jussieu, 75005, Paris, France

   Haïm Brezis

4. EPFL SB MATHAA CAMA, Station 8, 1015, Lausanne, Switzerland

   Hoai-Minh Nguyen

Corresponding author

Correspondence to Haïm Brezis.

H. Brezis: Research partially supported by NSF Grant DMS-1207793.

Appendix: Proof of Pathology 2

We construct a function \(u \in W^{1, 1}(0, 1)\) such that, for \(\varphi = c_1 \tilde{\varphi } _1\),

Set \(x_n = 1 - 1/ n\) for \(n \ge 1\). Set \(\delta _1 = 1/100\) and \(T_1 = e^{-\delta _1^{-1}}\). Let \(y_1\) be the middle point of the interval \((x_1, x_1 + T_1)\) and fix \(0< t_1< T_1/ 4\) such that

Since

for all \(\alpha< \beta < \gamma \), such a \(t_1\) exists. Define \(u_1 \in W^{1, 1}(0, 1)\) by

Assuming that \(\delta _{k}\), \(T_{k}\), \(t_{k}\), and \(u_k\) are constructed for \(1 \le k \le n-1\) and for \(n \ge 2\) such that \(u_k\) is Lipschitz. We then obtain \(\delta _n\), \(T_n\), \(t_n\), and \(u_n\) as follows. Fix \(0< \delta _{n}< \delta _{n-1}/ 8\) sufficiently small such that

Such a constant \(\delta _n\) exists by Proposition 1 (in fact \(u_{n-1}\) is only Lipschitz; however Proposition 1 holds as well for Lipschitz functions, see also Proposition C1). Set \(T_n = e^{- \delta _n^{-1}}\) and let \(y_n\) be the middle point of the interval \((x_n, x_n + T_n)\) and fix \(0< t_n< T_n/ 4\) such that

Such a \(t_n\) exists by (A2). Define a continuous function \(w_n: [0, 1] \mapsto [0, 1]\), \(n \ge 2\), as follows

Set

Since \(w_n\) and \(u_{n-1}\) are Lipschitz, it follows that \(u_n\) is Lipschitz. Moreover, one can verify that \((u_n)\) converges in \(W^{1, 1}(0, 1)\) by noting that

Let u be the limit of \((u_n)\) in \(W^{1, 1}(0, 1)\). We derive from the construction of \(u_n\) that u is non-decreasing, and for \(n \ge 1\),

since \(\delta _k < \delta _{k-1}/ 8\). We have

It is clear that

and

since u is constant in \([x_{n-1} + T_{n-1}, x_n]\). It follows from (A3) that

On the other hand, from (A4), (A5), and the definition of \(w_n\), we have, for \(n \ge 1\),

Combining (A8) and (A9) and noting that \(u_n \rightarrow u\) in \(W^{1, 1}(0, 1)\), we obtain the conclusion. \(\square \)

Appendix: Proof of Pathology 3

We first establish (2.41) for \(\varphi = c_1 \tilde{\varphi } _1\) where \(c_1 = 1/ 2\) is the normalization constant.

Let \(c \ge 5\) and for each \(k \in \mathbb {N}\) (\(k \ge 4\)) define a non-decreasing continuous function \(v_{k}: [0, 1] \mapsto [0, 1]\) with \(v_k(1) = 1\) as follows

Clearly,

Define

Since \(c_1 = 1/2\), one can show that (see [43, page 683])

Since, for \(c \ge 2\),

it follows that, for sufficiently large c,

Fix such a constant c. We are now going to define by induction a sequence of \(u_n: [0, 1] \mapsto [0, 1]\). Set

Assume that \(u_{n-1}\) (\(n \ge 1\)) is defined and satisfies the following properties:

and there exists a partition \(0 = t_{0, n-1}< t_{1, n-1}< \cdots < t_{2 l_{n-1}, n-1} = 1\) such that, with the notation \(J_{i, n-1} = [t_{i, n-1}, t_{i+1, n-1}]\), the following four properties hold:

the total variation of \(u_{n-1}\) on the interval \(J_{i, n-1}\) with i odd (where \(u_{n-1}\) is not constant) is always \(1/ l_{n-1}\), i.e.,

and the intervals \(J_{i, n-1}\) with i odd have the same length which is less than the one of any interval \(J_{i, n-1}\) with i even, i.e.,

Since \(u_{n-1} (0) = 0\), it follows from the properties of \(u_{n-1}\) in (B5) and (B6) that

Set

(\(B_{n-1}\) is the union of all intervals on which \(u_{n-1}\) is constant). For \(n \in \mathbb {N}\), let \(k_n\) be a sufficient large integer such that

and

Since, for a small positive number \(\tau \),

such a constant \(k_n\) exists by (B3). Define

where \(s = (t - t_{2i +1, n-1}) / |J_{2i + 1, n-1}|\). Then \(u_n\) satisfies (B4)-(B8) for some \(l_n\) and \(t_{i, n}\). Since \(0 \le v_k(x) \le x\) for \(x \in [0, 1]\), we deduce from (B9) and the definition of \(u_{n}\) that \(u_n \le u_{n-1}\). On the other hand, we derive from (B9) and (B13) that, for \(m\ge n\),

Hence the sequence \((u_n)\) is Cauchy in C([0, 1]). Let u be the limit and set

It follows from the definition of \(u_n\) and u that

From the construction of \(u_n\) in (B13), the property of \(v_k\) in (B2), and (B8), we derive that

where \(\tau _n\) is defined in (B11). Since \(u_{n-1}\) is constant in \(J_{2i, n-1}\) for \(0 \le i \le l_{n-1} - 1\) by (B5), it follows from (B13) that u is constant in \(J_{2i, n-1}\) for \(0 \le i \le l_{n-1} - 1\). We derive that

Using (B16), we have, by (B11),

We now estimate, for \(0 \le i \le l_{n-1} - 1\),

Define \(g_i : J_{2i + 1, n-1} \rightarrow [0, 1]\), for \(0 \le i \le l_{n-1} - 1\), as follows

We claim that, for \(0 \le i \le l_{n-1} - 1\),

then

In fact, if \(g_i(z) \in [i/ k_{n}, (i+2)/ k_n - 1 / (c k_n)]\) then

Here we used (B15) and the fact that u is non-decreasing. It follows from the definition of \(u_n\) that, if \(g_i(x), g_i(y) \in [i/ k_{n}, (i+2)/ k_n - 1 / (c k_n)]\) then

The claim is proved.

By a change of variables, for \(i=0, \cdots , 2 l_{n-1} -1\),

we deduce from the claim that

It follows from (B12) and (B14) that

Combining (B17), (B18), and (B19) yields

Since \(c_1 = 1/2\), we have, for \(\varphi = c_1 \tilde{\varphi } _1\),

Note that \(u \in C([0, 1])\) is non-decreasing and \(u(0) =0\) and \(u(1) = 1\). This implies

Therefore (2.41) holds for \(\varphi = c_1 \tilde{\varphi } _1\) and u.

We next construct a continuous function \(\varphi _\ell \) which is “close” to \(c_1 \tilde{\varphi } _1\) such that (2.41) holds for \(\varphi _\ell \) and the function u constructed above. For \(\ell \ge 1\), define a continuous function \(\varphi _\ell : [0 , + \infty ) \mapsto \mathbb {R}\) by

where \(\alpha _\ell \) is the constant such that

Then \(\varphi _{\ell } \in \mathcal{A}\). Moreover, \(\varphi _\ell (t) \le \alpha _\ell \tilde{\varphi } _1 (\beta _\ell t)\) where \(\beta _\ell = 1 + 1/\ell \). It follows from (B20) that

Since \(a_\ell \rightarrow c_1 = 1/2\) and \(\beta _\ell \rightarrow 1\) as \(\ell \rightarrow +\infty \), the conclusion holds for \(\varphi _\ell \) when \(\ell \) is large. The proof is complete. \(\square \)

Appendix: Pointwise Convergence of \(\Lambda _{\delta }(u)\) When \(u \in W^{1, p}(\Omega )\)

In this section, we prove the following result

Proposition C1

Let \(d \ge 1\), \(\Omega \) be a smooth bounded open subset of \(\mathbb {R}^d\), and \(\varphi \in \mathcal{A}\). We have

Proof

We already know by Proposition 1 that

Assume now that \(u \in W^{1, p}(\Omega )\) for some \(p>1\). We are going to prove that

Consider an extension of u to \(\mathbb {R}^d\) which belongs to \(W^{1, p}(\mathbb {R}^d)\). For simplicity, we still denote the extension by u.

Clearly

and thus it suffices to establish that

Using polar coordinates and a change of variables, we have, as in (2.10),

As in (2.12), we also obtain

As in (2.15), we have

On the other hand, since \(\varphi \) is non-decreasing, it follows that, for \(\delta >0\),

where

Indeed, we have

We claim that

Assuming (C9), we may then apply the dominated convergence theorem using (C4), (C5), (C6), (C7), and (C9), and conclude that (C3) holds.

To show (C9), it suffices to prove that, for all \(\sigma \in \mathbb {S}^{d-1}\),

Here and in what follows C denotes a positive constant independent of u and \(\delta \); it depends only on \(\Omega \) and p. For simplicity of notation, we assume that \(\sigma = e_{d}: = (0, \cdots , 0, 1 )\). By a change of variables, we have

Note that

We have

Since, by the theory of maximal functions in one dimension,

it follows from (C12) that

Combining (C11) and (C13) implies (C10) for \(\sigma = e_d\). The proof is complete. \(\square \)

Remark 10

The above proof shows that

The idea of using the theory of maximal functions to derive a similar estimate (in a slightly different context but still for \(\varphi = c_1 \tilde{\varphi } _1\)) is originally due to A. Ponce and J. Van Schaftingen [51]; see also H.-M. Nguyen [42].

Reprints and permissions