Monday, August 20, 2012

The coarea formula for BV functions

Today, we will discuss the coarea formula for $BV$ functions, established by Fleming and Rishel in 1960 (W. Fleming, R. Rishel, An integral formula for total gradient variation, Arch. Math. 11 (1960), 218-222.)

Let us first recall the lower semicontinuity property of the total variation with respect to the strong convergence in $L^1(\Omega)$:
Let $\{u_n\}_{n\in\Omega}$ be a sequence in $BV(\Omega)$ strongly converging to some $u$ in $L^1(\Omega)$ and satisfying $|u_{n}|_{BV} < \infty$. Then $u\in BV(\Omega)$ and $$|u|_{BV(\Omega)} \leq \lim\inf_{n\rightarrow \infty} |u_n|_{BV(\Omega)}.$$ The coarea formula is as stated as follows:

Coarea formula: Let $u$ be a given function in $BV(\Omega)$. Then for almost every $t$ in $\mathbb{R}$, the level set $E_t=\{ x\in \Omega \subset \mathbb{R}^N: u(x) > t\}$ of $u$ is a set of finite perimeter in $\Omega$, and
&Du=\int_{-\infty}^{\infty} D\chi_{E_t}\, dt,\\
&|u|_{BV(\Omega)}=|Du|(\Omega)=\int_{-\infty}^{\infty} \int_{\Omega}|D\chi_{E_t}|\, dt.
The second assertion above is often written in terms of the perimeter of level sets as follows:
|u|_{BV(\Omega)}=\int_{-\infty}^{\infty} Per(E_t, \Omega) dt,
where $Per(E_t, \Omega)=\mathcal{H}^{N-1}(\Omega \cap \partial E_t)$ is the perimeter of the level set $E_t$.

Proof of the coarea formula: We follow the treatment of Variational Analysis in Sobolev and BV spaces by Attouch et al.

Part I: Proof of $|Du|(\Omega) \leq \int_{-\infty}^{\infty}\int_{\Omega}|D\chi_{E_t}|\, dt$:

Let us assume that $D\chi_{E_t}$ belongs to $\mathbf{M}(\Omega, \mathbb{R}^N)$, the set of all $\mathbb{R}^N-$ valued Borel measures which is the set of all the $\sigma-$ additive set functions $\mu:\mathcal{B}(\Omega)\rightarrow \mathbb{R}^N$, with $\mu(\emptyset)=0$. For all $t$ in $\mathbb{R}$ set
\chi_{E_t} & \mbox{if } t \geq 0 \\
-\chi_{\Omega \backslash E_t} & \mbox{if } t < 0 \end{array} \right. \end{equation} It is easy to see that $u(x)=\int_{-\infty}^{\infty}f_t(x)\,dt$ for all $x\in \Omega$. For all $\bar{\phi} \in C_c^1(\Omega, \mathbb{R}^N)$ we have \begin{align*} &\langle Du, \bar{\phi} \rangle \\ &= -\int_{\Omega} u \, \mbox{div} \,\bar{\phi} \, dx \\ & = - \int_{\Omega} \int_{-\infty}^{\infty} f_t \, \mbox{div} \,\bar{\phi} \, dt\,dx\\ &= - \int_{\Omega} \int_{-\infty}^{0} f_t \, \mbox{div} \,\bar{\phi} \, dt\,dx -\int_{\Omega} \int_{0}^{\infty} f_t \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= \int_{\Omega} \int_{-\infty}^{0} \chi_{\Omega \backslash E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx -\int_{\Omega} \int_{0}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &=\int_{\Omega} \int_{-\infty}^{0} (1-\chi_{E_t}) \, \mbox{div} \,\bar{\phi} \, dt\,dx -\int_{\Omega} \int_{0}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &=\int_{\Omega} \int_{-\infty}^{0} \mbox{div} \,\bar{\phi} \, dt\,dx - \int_{\Omega} \int_{-\infty}^{0} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx-\int_{\Omega} \int_{0}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= \int_{\Omega} \int_{-\infty}^{0} \mbox{div} \,\bar{\phi} \, dt\,dx-\int_{\Omega} \int_{-\infty}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= 0-\int_{\Omega} \int_{-\infty}^{\infty} \chi_{E_t} \, \mbox{div} \,\bar{\phi} \, dt\,dx \\ &= \int_{-\infty}^{\infty} \langle D\chi_{E_t}, \bar{\phi}\rangle \,dt \end{align*} Hence, $Du=\int_{-\infty}^{\infty} D\chi_{E_t}\, dt$, and $|Du|(\Omega) \leq \int_{-\infty}^{\infty}\int_{\Omega}|D\chi_{E_t}|\, dx dt$.

Part II: (coverse) Proof of $\int_{-\infty}^{\infty}\int_{\Omega}|D\chi_{E_t}|\, dxdt\leq |Du|(\Omega) $:

Step i. We first assume that $u$ belongs to the space $\mathcal{A}(\Omega)$ of piecewise linear and continuous functions in $\Omega$. By linearity, one can assume that $u=a\cdot x+b$ with $a\in \mathbb{R}^N$ and $b\in \mathbb{R}$, so that

&\int_{\Omega} |D\chi_{E_t}|\\
&=\mathcal{H}(\Omega \cap \partial E_t)\\
&=\mathcal{H}(\Omega \cap \{x| a\cdot x +b=t\})\\
&=\int_{\Omega \cap \{x| a\cdot x +b=t\}} d\mathcal{H}^{N-1}(x)\\
&=\int_{\{x| a\cdot x +b=t\}}\chi_{\Omega}(x)\, d\mathcal{H}^{N-1}(x)
Thus we get,
&\int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_t}|\, dx dt\\
&=\int_{\{x| a\cdot x +b=t\}}\chi_{\Omega}(x)\, d\mathcal{H}^{N-1}(x)\\
&=\int_{\Omega} |Du|
Hence we have,
\int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_t}|\, dx dt=|Du|(\Omega) \dots \mbox{ if } u=a\cdot x+b.

Step ii. Now we prove that $\int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_t}|\, dx dt\leq|Du|(\Omega)$ for all $u\in BV(\Omega)$. We know that the space of piecewise linear and continuous functions $\mathcal{A}(\Omega)$ is dense in $W^{1, 1}(\Omega)$ when equipped with the strong topology. We also know that the space $C^{\infty}\cap W^{1, 1}(\Omega)$ is dense in $BV$ when equipped with the intermediate convergence. Thus, there exists a sequence $\{u_n\}_{n\in \mathbb{N}} \in \mathcal{A}(\Omega)$ such that $u_n\rightharpoonup u$ for the intermediate convergence. For each of the functions $u_n$ we set $E_{n, t}:=\{x\in \Omega: u_n(x) > t\}$. Due to the intermediate convergence, we have
&\int_{\Omega}|Du|=\lim_{n\rightarrow \infty}\int_{\Omega}|Du_n| \dots \mbox{the intermediate convergence}\\
&=\lim_{n\rightarrow \infty} \int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_{n,t}}|\, dx dt \dots \mbox{from step i}\\
&\geq \int_{-\infty}^{\infty} \lim\inf_{n\rightarrow \infty} \int_{\Omega} |D\chi_{E_{n,t}}|\, dx dt \dots \mbox{Fatou's lemma}\\
From the intermediate convergence we also have $u_n\rightarrow u$ in $L^1(\Omega)$. i.e.
\int_{\Omega} |u_n-u|=\int_{\Omega} \int_{-\infty}^{\infty} |\chi_{E_{n,t}}-\chi_{E_t}|\ dt dx = \int_{-\infty}^{\infty} \Big(\int_{\Omega} |\chi_{E_{n,t}}-\chi_{E_t}|\ dx \Big) dt=0.
Thus, for a subsequence $E_{n_m, t}$, and for almost all $t \in \mathbb{R}$, $\chi_{E_{n_m, t}}\rightarrow \chi_{E_{n, t}}$ strongly in $L^1(\Omega)$. The lower semicontinuity of the total variation with respect to the strong convergence in $L^1(\Omega)$ we get $\lim\inf_{n\rightarrow \infty} \int_{\Omega} |D\chi_{E_{n_m,t}}|\, dx \geq \int_{\Omega} |D\chi_{E_{t}}|\, dx$. Thus, we get,
$$ \int_{\Omega}|Du| \geq \int_{-\infty}^{\infty} \int_{\Omega} |D\chi_{E_{t}}|\, dx dt. $$
This completes the proof!

(By the way, step ii also proves that $D\chi_{E_t} \in \mathbf{M}(\Omega, \mathbb{R}^N)$ for a.e. $t\in \mathbb{R}$, something that we used in Part I of the proof.)

Thursday, August 9, 2012

Hausdorff measure and dimension

Let us talk about Hausdorff measure $\mathcal{H}^s$ named after Felix Hausdorff, which comes up in image processing often. These measures allow us to measure very small subsets of $\mathbb{R}^n$. The idea is that $A$ is an $s-$ dimensional subset of $\mathbb{R}^n$ if $0<\mathcal{H}^s(A)<\infty$. We will follow the notation and treatment of Evans and Gariepy.

Felix Hausdorff
(i) Let $A\subset \mathbb{R}^n$, $0\leq s < \infty$, $0<\delta\leq \infty$. Define $$\mathcal{H}^s_{\delta}(A)=\inf \Big\{ \sum_{j=1}^{\infty} \alpha(s) \Big( \frac{\mbox{diam}(C_j)}{2} \Big)^s \, \Big\vert \,A\subset \cup_{j=1}^{\infty}C_j, \mbox{diam}(C_j)\leq \delta \Big\},$$ where $\{C_j\}\subset \mathbb{R}^n$ is the covering of the set $A$ and $\alpha(s)=\frac{\pi^{\frac{s}{2}}}{\Gamma(\frac{s}{2}+1)}.$ Here $\Gamma(s)=\int_0^{\infty}e^{-x}x^{s-1}\,dx,\,\,(0< s<\infty),$ is the usual gamma function. (ii) The $s-$dimensional Hausdorff measure of $A$ is denoted by $\mathcal{H}^s(A)$ and it is defined as the limit:
$$ \mathcal{H}^s(A)=\lim_{\delta\rightarrow 0}\mathcal{H}^s_{\delta}(A)=\sup_{\delta >0} \mathcal{H}^s_{\delta}(A).$$

The book: 'Measure theory and fine properties of functions' by Evans and Gariepy includes the normalizing constant $\alpha(s)$ in the definition, whereas some other authors do not include this constant. The constant $\alpha(s)$ is included because if $s$ is an integer, then $\mathcal{H}^s(A)$ is equal to the $s-$dimensional surface area for nice sets (graph of Lipschitz function).

Some properties of Hausdorff measure:
1.$\mathcal{H}^s$ is a Borel regular measure. Refer to E.G. for the proof.

2. Let us consider a Hausdorff measure $\mathcal{H}^0$ of a singleton $\{a\}\in \mathbb{R}^n$. First note that $\alpha(0)=1$. So, $\mathcal{H}^0(\{a\})=\mathcal{H}^0_{\delta}(\{a\})=1$. Thus, $\mathcal{H}^0$ is a counting measure.

3. $\mathcal{H}^1=\mathcal{L}^1$ on $\mathbb{R}^1$, i.e. $\mathcal{H}^1$ measure of a line segment is its length.

4. Since $\mathbb{R}^n$ is not $\sigma-$finite, $\mathcal{H}^s$ is not a Radon measure for $0\leq s < n$.

5. If $s > n$ then $\mathcal{H}^s\equiv 0$ on $\mathbb{R}^n$.
To see this is easy. Let us consider a unit cube $Q$ in $\mathbb{R}^n$, fix an integer $m \geq 1$. The unit cube can be decomposed into $m^n$ cubes with sides $1/m$ and diameter ${n^{1/2}}/{m}$. Therefore,
$$ \mathcal{H}^s_{{\sqrt{n}}/{m}}(Q)\leq \sum_{i=1}^{m^n} \alpha(s) (n^{1/2}/m)^s = \alpha(s) n^{s/2} m^{n-s}.$$If $s >n$, then $m^{n-s}\rightarrow 0$ as $m\rightarrow \infty$ i.e. as the size of the covering vanishes. Thus, $\mathcal{H}^s(Q)=0$, so $\mathcal{H}^s(\mathbb{R}^n)=0$ for $s >n$.

6. Scaling: $\mathcal{H}^s(\lambda A)=\lambda^s\mathcal{H}^s(A)$ for all $\lambda > 0$, $A \subset \mathbb{R}^n$. (Easy to prove.)

7. Invariance under affine transformation: $\mathcal{H}^s(L(A))=\mathcal{H}^s(A)$ for each affine isometry $L:\mathbb{R}^n\rightarrow \mathbb{R}^n, \, A \subset \mathbb{R}^n$.

8. $\mathcal{H}^n=\mathcal{L}^n$ on $\mathbb{R}^n$.

Hausdorff-Besicovitch dimension:
The hausdorff dimension of a set $A\subset \mathbb{R}^n$ is defined to be

$$\mathcal{H}_{\mbox{dim}}(A)=\inf\{ 0\leq s < \infty | \mathcal{H}^s(A)=0 \}.$$

The following assertions follow from the definition:
Countable sets have Hausdorff dimension $0$. The Euclidean space has Hausdorff dimension $n$.
The circle has Hausdorff dimension $1$.
The Cantor set (a zero-dimensional topological space) is a union of two copies of itself, each copy shrunk by a factor 1/3; this fact can be used to prove that its Hausdorff dimension is ${\ln 2}/{\ln 3}$.

Thursday, July 26, 2012

Rudin-Osher-Fatemi image denoising model

Today we will finally touch the subject of the celebrated image denoising model proposed by Rudin, Osher and Fatemi in 1992, ( L. Rudin, S. Osher, E. Fatemi, "Nonlinear total variation based noise removal algorithms", Physica D, vol. 60, pp. 259–268, 1992.)

This model is motivated by the following problem in image restoration:
Given a noisy image $f:\Omega\rightarrow \mathbb{R}$, where $\Omega$ is bounded open subset of $\mathbb{R}^2$, we need to obtain a clean image $u$.

For solving this problem they proposed the following minimization problem:
$$\mbox{ minimize } \int_{\Omega}|\nabla u|\\\mbox{ subject to } \int_{\Omega} u=\int_{\Omega}f \, \hspace{10 pt}\mbox{ and } \hspace{10 pt}\int_{\Omega} |f-u|^2 = \sigma^2.$$ where $\sigma^2$ is the estimated global variance of the additive noise. This can be also formulated in terms of soft constraint minimization:
$$u_{\lambda}=\arg\min_u \{\,|u|_{BV(\Omega)} + \lambda \Vert f-u\Vert_{L^2(\Omega)}^2\}.$$ where $|u|_{BV(\Omega)}$ is the BV-seminorm.
In general, this belongs to the class of minimization problems of the following type
$$u_{\lambda}=\arg\min_u \{\,J(u) + H(f, u) \}$$ where $J$ is a convex nonnegative regularization functional and the fitting functional $H$ is convex nonnegative with respect to $u$ for fixed $f$. Due to convexity there exists a minimizer $u_{\lambda}$ such that '0' is in the sub-differential of $J(u) + H(f, u)$ at $u_{\lambda}$ i.e.
$$0\in\partial_u J(u_{\lambda})+\partial_u H(u_{\lambda}, f).$$
(here subdifferential $\partial_u J$ at $u_{\lambda}$ is the set $\partial_u J(u_{\lambda}):=\{v:J(u)\geq J(u_{\lambda})+\langle v, u-u_{\lambda} \rangle \}$. )

If $H(u, f)=\lambda\Vert f-u\Vert_{L^2(\Omega)}^2$, then $\partial_u H(u, f)=2\lambda (u-f)$. Moreover if $H(u, f)=\lambda\Vert f-Ku\Vert_{L^2(\Omega)}^2$, where $K:L^2(\Omega)\rightarrow \mathcal{H}$, $\mathcal{H}$ being some Hilbert space, then $\partial_u H(u, f)=2\lambda K^*(Ku-f)$, where $K^*$ denotes an adjoint of $K$.

Formally, we can write $\partial J(u)=-\mbox{div}\Big( \frac{\nabla u}{|\nabla u|}\Big)$, and we can write the Euler-Lagrange differential equation for the Rudin Osher Fatemi model as follows:
$$ 0=-\mbox{div}\Big( \frac{\nabla u}{|\nabla u|}\Big)+2\lambda(u-f)$$ or equivalently,
$$ u=f+\frac{1}{2\lambda}\mbox{div}\Big( \frac{\nabla u}{|\nabla u|}\Big)$$
We impose Neumann boundary condition $\nabla u\cdot\nu=0$ in the boundary $\partial \Omega$, this ensures the condition on the mean: $\int_{\Omega}u=\int_{\Omega}f$.

Dependence on the scaling parameter $\lambda$:

The parameter $\lambda$ determines the denoising level. If $\lambda$ is small, then it is equivalent to penalizing the fidelity term more and the minimizer $u_{\lambda}$ is very close to the original image. On the other hand, for large $\lambda$ the minimizer is a cartoon representation of the image $f$.

We perform a few experiments on the image of Lenna:
Original image, Lena.

For $\lambda=0.8$ and the image in the range [0, 255] we get the following result:
The denoised image $u_{\lambda}$ for $\lambda=0.8$
We see above that for this $\lambda=0.8$ the denoising is minimal.

For $\lambda=0.05$ and the image in the range [0, 255] we get the following result:

The denoised image $u_{\lambda}$ for $\lambda=0.05$.

Here we see the details are gone, but we still see a lot of structure. Let's see what happens if we take $\lambda=0.01$, with image in [0, 255].
The denoised image $u_{\lambda}$ for $\lambda=0.01$.

We here see that we get only a cartoon image of Lena. In other words we get only large-scale structures in the image of Lena.

Properties of the ROF denoising:
Let us look at some properties of the ROF model now.

1. The $L^2$-norm of the minimizer $u_{\lambda}$ is bounded, and the bound is independent of $\lambda$.

This nice property can be proven (Nezzar) by realizing that $u_{\lambda}$ is a minimizer of the ROF functional, thus for any $w\in BV(\Omega)$ we have:
$$|u_{\lambda}|_{BV(\Omega)}+\lambda \Vert f-u_{\lambda}\Vert_{L^2(\Omega)}^2\leq |w|_{BV(\Omega)}+\lambda \Vert f-w\Vert_{L^2(\Omega)}^2.$$This is true even if we choose $w \equiv 0$, which gives us:$$|u_{\lambda}|_{BV(\Omega)}+\lambda \Vert f-u_{\lambda}\Vert_{L^2(\Omega)}^2\leq \lambda \Vert f\Vert_{L^2(\Omega)}^2.$$As $0\leq |u_{\lambda}|_{BV(\Omega)}$ we have:$$\Vert f-u_{\lambda}\Vert_{L^2(\Omega)}^2\leq \Vert f\Vert_{L^2(\Omega)}^2.$$By expanding the $L^2$ term and using Cauchy-Schwartz inequality we get $$\int_{\Omega} f^2-2fu_{\lambda}+u_{\lambda}^2 \leq \int_{\Omega}f^2,\\
\int_{\Omega} u_{\lambda}^2 \leq \int_{\Omega}2fu_{\lambda} \leq 2 \Vert u_{\lambda}\Vert_{L^2(\Omega)}\Vert f \Vert_{L^2(\Omega)},\\
\Vert u_{\lambda} \Vert_{L^2(\Omega)}\leq 2 \Vert f \Vert_{L^2(\Omega)}.$$

2. The average of the minimizer $u_{\lambda}$ is the same as the average of the original image $f$.

To prove this it suffices to prove that $\int_{\Omega}u_{\lambda}=\int_{\Omega}f.$ This follows from integrating the Euler-Lagrange differential equation and Neumann boundary condition.

Now let us discuss properties of the ROF minimization proven by Yves Meyer. Let's define a few things first.

Definition: Let $G$ denote the space as follows $G=\{v=\mbox{div } \bar{g}: \bar{g}=(g_1, g_2); \mbox{ with }g_1, g_2 \in L^{\infty}(\mathbb{R}^2)\}.$
The star-norm $\Vert v \Vert_*$ of $v\in G$ is defined as follows:
$$\Vert v \Vert_* =\inf \{\Vert |\bar{g}|_{l^2}\Vert_{L^{\infty}}:v=\mbox{div } \bar{g}\}$$

3. If $v\in L^2(\mathbb{R}^2)$, then
$$ \int f\, v \leq |f|_{BV(\Omega)} \Vert v\Vert_{*}.$$
This property is true for $f\in W^{1, 1}(\mathbb{R}^2)$. Then we can use the density of $W^{1, 1}(\mathbb{R}^2)$ in $BV(\mathbb{R}^2)$.

4. Meyer: If $\Vert f \Vert_* \geq \frac{1}{2\lambda}$, then the Rudin-Osher-Fatemi decomposition $f=u_{\lambda}+v_{\lambda}$ is characterized by the following two conditions:$$ \Vert v_{\lambda} \Vert_* = \frac{1}{2\lambda} \mbox{ and } \int u_{\lambda}v_{\lambda}=\frac{1}{2\lambda} |u_{\lambda}|_{BV}.$$
Moreover, if $\Vert f \Vert_* \leq \frac{1}{2\lambda}$, then $u_{\lambda}=0$ and $v_{\lambda}=f$.

To prove this assertion, consider that if $u_{\lambda}$ is the minimizer of the ROF energy then $u_{\lambda}+\epsilon h$ is not! for a constant $\epsilon$ and a function $h$. This gives $|\int vh|\leq \frac{1}{2\lambda}|h|_{BV}$. Secondly, taking $h=u_{\lambda}$ we obtain equality.

Thursday, May 31, 2012

More on intermediate convergence

According to the vectorial version of the Riesz-Alexandroff representation theorem, the dual norm $\vert u \vert_{BV}=\Vert Du \Vert=\sup \{\int_{\Omega} u \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}$ is also the total mass $|Du|(\Omega)=\int_{\Omega}|Du|$ of the total variation $|Du|$ of the measure $Du$.

Moreover, from classical integration theory, the integral $\int_{\Omega}\phi \,d(Du)$ is well defined for all $Du$ integrable functions $\phi$ from $\Omega$ into $\mathbb{R}^N$, e.g. for functions in $C_b(\Omega, \mathbb{R}^N)$. For the same reasons, $\int_{\Omega}\phi\, d|Du|$ is well defined for all $|Du|$ integrable functions $\phi$, in particular for functions in $C_b(\Omega)$.

Thus, we can say that $|Du_n|\rightharpoonup |Du|$ narrowly in $M(\Omega)$ if $\int_{\Omega}\phi \, d|Du_n|\rightarrow \int_{\Omega}\phi\,d|Du|$, for all $\phi \in C_b(\Omega)$. If we choose $\phi\equiv 1$ on $\Omega$ then $\Vert Du_n \Vert \rightarrow \Vert Du \Vert$ i.e. $|u_n|_{BV}\rightarrow |u|_{BV}$.

Hence, $u_n\rightarrow u$ in $L^1(\Omega)$ and the narrow convergence of measures, $|Du_n|\rightharpoonup |Du|$ in $M(\Omega)$ implies the intermediate convergence, $u_n\rightharpoonup u$ (i.e. $u_n\rightarrow u$ in $L^1(\Omega)$ and $|u_n|_{BV}\rightarrow |u|_{BV}$).

We have the following proposition regarding the intermediate convergence.

The following three assertions are equivalent
(i) $u_n\rightharpoonup u$ in the sense of intermediate convergence.
(ii) $u_n\rightharpoonup u$ in $BV(\Omega)$ and $\vert u_n \vert_{BV}\rightarrow \vert u \vert_{BV}$.
(iii) $u_n\rightarrow u$ strongly in $L^1(\Omega)$ and $\vert Du_n \vert\rightharpoonup \vert Du \vert$ narrowly in $M(\Omega)$.

The equivalence (i) to (ii) is a consequence of a proposition from the previous post. We have just seen above that (i) and (iii) are equivalent. We only need to prove that (ii) implies (iii).

Recall that $u_n\rightharpoonup u$ weakly in $BV(\Omega)$ means that
(a) $u_n\rightarrow u$ strongly in $L^1(\Omega)$ and
(b) the measures $Du_n\rightharpoonup Du$ weakly in $M(\Omega, \mathbb{R}^N)$.

Also, recall that for non-negative Borel measures $\mu_n$ and $\mu$ in $M(\Omega)$ the following statements are equivalent:
(c) $\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu(U)\leq \lim\inf_{n\rightarrow\infty}\mu_n(U)$ for all open subsets $U\subset \Omega$.
(d) $\mu_n\rightharpoonup \mu$ narrowly in $M(\Omega)$.

Let, $\mu_n=|Du_n|$ and $\mu=|Du|$. We have been given that $|Du_n|(\Omega)\rightarrow |Du|(\Omega)$ i.e. we have $\mu_n(\Omega)\rightarrow \mu(\Omega)$. For showing the narrow convergence $\mu_n\rightharpoonup \mu$ we just need to prove the lower-semicontinuity property on $U\subset\Omega$,
i.e. we need to show that for $\mu(U)\leq \lim\inf_{n\rightarrow\infty}\mu_n(U)$ for all open subsets $U\subset \Omega$,
i.e. we need to show that for $|Du|(U)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(U)$ for all open subsets $U\subset \Omega$.

To this effect we use the proposition from the previous blog which says that if $u_n\in BV(\Omega)$ with $|u_n|_{BV(\Omega)}$ bounded, with $u_n\rightarrow u$ in $L^1(\Omega)$, then we have the lower semicontinuity property i.e. $|Du|(\Omega)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(\Omega)$, and $u\in BV(\Omega)$.

Let $U\subset\Omega$ be any open subset. We have $u_n\in BV(\Omega)$, thus as $U\subset\Omega$, we have $u_n\in BV(U)$. Thus, we have $\sup_n |Du_n|(U)\leq \sup_n |Du_n|(\Omega)<\infty$.

The weak convergence $u_n\rightharpoonup u$ in $L^1(\Omega)$ implies the strong convergence $u_n\rightarrow u$ in $L^1(\Omega)$ and thus the strong convergence $u_n\rightarrow u$ in $L^1(U)$ follows as $U\subset \Omega$.

 Now that we have the conditions in the proposition: $u_n\in BV(U)$, $\sup_n |Du_n|(U)<\infty$, and $u_n\rightarrow u$ in $L^1(U)$ we have the lower semicontinuity property: $|Du|(U)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(U)$ for all open subsets $U\subset \Omega$. 

As we have $|Du_n|(\Omega)\rightarrow |Du|(\Omega)$ and $|Du|(U)\leq \lim\inf_{n\rightarrow\infty}|Du_n|(U)$ for all open subsets $U\subset \Omega$, from the equivalence of (c) and (d) we get the narrow convergence: $|Du_n|\rightharpoonup |Du_n|$ narrowly in $M(\Omega). \,\,\hspace{25pt} \square$.

In conclusion, intermediate convergence implies narrow convergence of $|Du_n|$.

Friday, February 24, 2012

Narrow convergence of measures and intermediate convergence of BV functions

Recall By the Riesz-Alexandroff representation theorem the dual of the space $C_0(\Omega,\mathbb{R}^N)$ (and thus of $C_c(\Omega,\mathbb{R}^N)$ can be isometrically identified with $M(\Omega,\mathbb{R}^N)$. i.e. any Borel measure $\mu$ is a bounded linear functional (continuous linear form if you like that) on $C_0(\Omega,\mathbb{R}^N)$ or $C_c(\Omega,\mathbb{R}^N)$. Thus, the weak convergence of a sequence of Borel measures $\mu_n$ is defined as follows.

Weak convergence of Borel measures: We say that a sequence of Borel measures $\mu_n$ converges weakly to $\mu$ i.e. $\mu_n\rightharpoonup \mu$ if $\langle\mu_n, \phi \rangle \rightarrow \langle \mu, \phi\rangle $ for all $\phi \in C_0(\Omega,\mathbb{R}^N)$.

Here, $\langle \mu, \,\phi\rangle\equiv\mu(\phi)\equiv\int_{\Omega} \phi \, d\mu \equiv \sum_{i=1}^N\int_{\Omega} \phi_i d\mu_i$.

Narrow convergence: A sequence $\{\mu_n\}$ in $M(\Omega, \mathbb{R}^N)$ narrowly converges to $\mu$ ($\mu_n\rightharpoonup \mu$ narrowly) in $M(\Omega, \mathbb{R}^N)$ if and only if $$\int_{\Omega} f\, d\mu_n \rightarrow \int_{\Omega} f d\mu,$$ for all $f \in C_b(\Omega, \mathbb{R}^N)$.

Narrow convergence is stronger than weak convergence.
If $\Omega=(0, 1)$ and $\mu_n=\delta_{\frac{1}{n}}$ then $\mu_n\rightharpoonup 0$ weakly. This is because for all $\phi \in C_0(\Omega)$, we have, $\mu_n(\phi)=\phi(\frac{1}{n})\rightarrow \phi(0)=0=\mu(\phi)$.

On the other hand, if $\phi\equiv1$ on $\Omega$, (note that $\phi \not\in C_0(\Omega)$ but $\phi \in C_b(\Omega)$), then we see that $\int_{\Omega} d\mu_n=\mu_n(\Omega)=1$ for all $n$. Essentially what happened with $\mu_n=\delta_{\frac{1}{n}}$ is that it converges weakly to $\mu=0$, but $\mu_n(\Omega)$, the size of $\Omega$ measured in $\mu_n$ does not converge to the size of $\Omega$ in measure $\mu(=0)$, that is $\mu_n\rightharpoonup \mu$ but $\mu_n(\Omega)\nrightarrow \mu(\Omega)$.

We have the following compactness result for the narrow topology.

PROKHOROV's sequential compactness theorem
If for a bounded subset $\mathcal{H}$ of $M^+(\Omega)$ it is true that for all $\epsilon$ there exists a compact subset $K_{\epsilon}\subset \Omega$ such that $\sup\{\mu(\Omega\ K_{\epsilon}):\mu\in \mathcal{H}\}\leq \epsilon$, then $\mathcal{H}$ is sequentially compact for the narrow topology.

The following equivalence proposition says that the convergence $\mu_n(\Omega)\rightarrow \mu(\Omega)$ is precisely what we need to ensure narrow convergence of measures.

Let $\mu_n$ and $\mu$ be in $M^+(\Omega)$, non-negative Borel measures, then the following assertions are equivalent:
(i) $\mu_n\rightharpoonup \mu$ narrowly.
(ii)$\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu \rightharpoonup \mu$ weakly.

Note that as narrow convergence is stronger than weak convergence, it is clear that if $\mu_n\rightarrow \mu$ narrowly then $\mu \rightharpoonup \mu$. Also, $\mu_n(\Omega)\rightarrow \mu(\Omega)$ follows by taking $f\equiv 1$.

So, we need to only prove that if $\mu \rightharpoonup \mu$ weakly and $\mu_n(\Omega)\rightarrow \mu(\Omega)$ then $\mu_n\rightharpoonup \mu$ narrowly. That is, we need to show that for any function $f$ in $C_b(\Omega, \mathbb{R}^N)$ we have $\big| \int_{\Omega} fd\mu_n - \int_{\Omega} fd\mu \big|\rightarrow 0$. To do this we add and subtract $\int_{\Omega} f\,\phi d\mu_n$ and $\int_{\Omega} f\,\phi d\mu$ where $\phi$ is continuous function that is compactly supported in $\Omega$. The result follows as $f$ is bounded i.e. $\Vert f \Vert_{\infty}$ is a finite number and $\int_{\Omega} f\phi d\mu_n \rightarrow \int_{\Omega} f\phi d\mu$ due to compact support of $\phi$ in $\Omega . \hspace{25pt}\square$

More equivalence proposition
Let $\mu_n$ and $\mu$ be in $M^+(\Omega)$, non-negative Borel measures, then the following assertions are equivalent:
(i) $\mu_n\rightharpoonup \mu$ narrowly.
(ii) $\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu(U)\leq \lim\inf_{n\rightarrow \infty} \mu_n(U)$ for all open subsets $U\subset \Omega$.
(iii) $\mu_n(\Omega)\rightarrow \mu(\Omega)$ and $\mu(F)\geq \lim\inf_{n\rightarrow \infty} \mu_n(F)$ for all closed subsets $F\subset \Omega$.
(iv) $\mu_n(B)\rightarrow \mu(B)$ for all Borel subsets $B\subset\Omega.\,\,\hspace{25pt}\square$

Ok, so far so good. But images are not necessarily continuous functions. They might have jump discontinuities, i.e. edges. For this the following result due to Marle (Measure et probabilities) is helpful:

Let $\mu_n$ and $\mu$ be non-negative Borel measures $M^+(\Omega)$, with $\mu_n\rightharpoonup \mu$ narrowly and let $f$ be a $\mu_n$ measurable bounded function for all $n$, such that it is discontinuous only on a set of null $\mu-$ measurable set then
$$\hspace{25pt}\int_{\Omega} f\, d\mu_n \rightarrow \int_{\Omega} f\, d\mu \hspace{25pt}\square$$

Now, that we have seen a notion of convergence for sequence of measures that is stronger than weak convergence, let's look at the a notion of convergence for sequence of functions in $BV$ space that is stronger than weak convergence.

Intermediate convergence
Let $\{u_n\}$ be a sequence in $BV(\Omega)$ and $u\in BV(\Omega)$. we say that $u_n\rightharpoonup u$ intermediately (or in the sense of intermediate convergence) if and only if
$$u_n\rightarrow u \mbox{ in } L^1(\Omega),$$
$$\hspace{25pt}\vert u_n\vert_{BV}\rightarrow \vert u\vert_{BV}\,\,\hspace{25pt}\square$$

Recall, from the previous post that for $\{u_n\}\in BV(\Omega)$ with bounded TV mass and $u_n\rightarrow u$ strongly in $L^1(\Omega)$, then we have $u_n\rightharpoonup u$ in $BV$, but $\vert u \vert_{BV}\leq \lim\inf_{n\rightarrow \infty}\vert u_n \vert_{BV}$ i.e. some of the mass is lost.

Ok, now I am hungry, so more about this tomorrow.

Tuesday, February 21, 2012

There is something about the $BV$ space

I have been putting it off for a while. But now that I can write Latex in the blogger I can talk about $BV$ spaces.
Solutions of some mathematical problems which have discontinuities along one-codimensional manifolds where the first distributional derivatives are measures prompt us to consider the $BV$ space. I will refer to Attouch et al's book: Variational Analysis in Sobolev and BV spaces.

Definition of $BV$ space: We say that a function $u:\Omega\rightarrow \mathbb{R}$ is a function of bounded variations i.e. $u\in BV \,$ if and only if it belongs to $L^1(\Omega)$ and its gradient $Du$ in the distributional sense is in $M(\Omega, \mathbb{R}^N)$.

The following statements are equivalent.
(i) $u\in BV(\Omega)$
(ii) $u \in L^1(\Omega)$ and $u_{x_i}\in M(\Omega)$ for all $i=1, 2, ..., N$.
(iii) $u \in L^1(\Omega)$ and $\vert u \vert_{BV}<\infty$, where $\vert u\vert_{BV}:=\sup \{\langle Du, \,\mathbf{\phi}\rangle: \mathbf{\phi} \in C_c(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}.$
(here $\langle Du, \,\mathbf{\phi}\rangle:=\sum_{i=1}^N \int_{\Omega}\, \mathbf{\phi}_i u_{x_i}$.)
(iv) $u \in L^1(\Omega)$ and $\vert u \vert_{BV}=\sup \{\int_{\Omega} u \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}<\infty$.

The implication (ii)$\implies $(iii) follows as $C_c(\Omega, \mathbb{R}^N)$ is dense in $C_0(\Omega, \mathbb{R}^N)$. The implication (ii)$\implies $(iii) follows as $C_c^{\infty}(\Omega, \mathbb{R}^N)$ is dense in $C_0(\Omega, \mathbb{R}^N)$ and $C_c(\Omega, \mathbb{R}^N)$.

Notations and facts:
$\Omega \subset \mathbb{R}^N$.
$C_0(\Omega, \mathbb{R}^N)$ is the space of all continuous functions that vanish at infinity. i.e. for a function $\phi\in C_0(\Omega, \mathbb{R}^N)$ the following is true: Given any $\epsilon > 0 $ there exists a compact set $K_{\epsilon} \subset \Omega$ such that $\sup_{x\in\Omega \backslash K_{\epsilon}}|\phi(x)|\leq \epsilon$.
The functions $\mathbf{\phi}$ in $C_0(\Omega, \mathbb{R}^N)$ are equipped with the uniform norm
$\Vert \phi \Vert_{\infty}:= \sup_{x \in \Omega}\{ |\phi(x)|\}$.
$C_c(\Omega, \mathbb{R}^N)$ is the subspace of $C_0(\Omega, \mathbb{R}^N)$ with a compact support in $\Omega$.
$C_b(\Omega,\mathbb{R}^N)$ is the subset of all bounded continuous functions from $\Omega$ into $\mathbb{R}^N$.

Density results:
$C_c(\Omega, \mathbb{R}^N)$ is dense in $C_0(\Omega, \mathbb{R}^N)$.
The space of infinitely differentiable and compactly supported functions $C_c^{\infty}(\Omega, \mathbb{R}^N)$ is dense is $C_0(\Omega, \mathbb{R}^N)$ and $C_c(\Omega, \mathbb{R}^N)$.

Duality results:
$M(\Omega, \mathbb{R}^N)$ denotes the space of all $\mathbb{R}^N$ valued Borel measures.
$M(\Omega, \mathbb{R}^N)$ is isomorphic to the product space $M^N(\Omega)$.
By the Riesz-Alexandroff representation theorem the dual of the space $C_0(\Omega, \mathbb{R}^N)$ (and thus of $C_c(\Omega, \mathbb{R}^N)$) can be isometrically identified with $M(\Omega, \mathbb{R}^N)$. i.e. any Borel measure $\mu$ is a bounded linear functional (continuous linear form if you like that) on $C_0(\Omega, \mathbb{R}^N)$ or $C_c(\Omega, \mathbb{R}^N)$ and the dual norms $\Vert\cdot \Vert_{C_{0}^{'}(\Omega, \mathbb{R}^N)}$ and $\Vert \cdot \Vert_{C_{c}^{'}(\Omega, \mathbb{R}^N)}$ are equal to the total mass $|\cdot|(\Omega)$ :
$$|\mu|(\Omega)\equiv \int_{\Omega}|\mu|=\sup\{ \langle \mu, \,\mathbf{\phi}\rangle: \mathbf{\phi} \in C_0(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1 \} =\sup\{ \langle \mu, \,\mathbf{\phi}\rangle: \mathbf{\phi} \in C_c(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1 \}.$$ Here, $\langle \mu, \,\phi\rangle\equiv\mu(\phi)\equiv\int_{\Omega} \phi \, d\mu \equiv \sum_{i=1}^N\int_{\Omega} \phi_i d\mu_i.$

The relation between $BV$ and the Sobolev space $W^{1, 1}$:

According to Radon-Nykodym theorem there exists $\nabla u \in L^1(\Omega, \mathbb{R}^N)$ and measure $D_s u$ that is singular with respect to $\mathcal{L}^N|_{\Omega}$, the $N-$ dimensional Lebesgue measure restricted to $\Omega$, such that: $$Du=\nabla u \, \mathcal{L}^N|_{\Omega}+ D_s u.$$ Thus, $W^{1, 1}$ is a subspace of the $BV-$ space and for functions in $W^{1, 1}$ we can write $Du=\nabla u$.

Norm on the $BV$ space:

The $BV$ space is equipped with the norm $\Vert u \Vert_{BV}=\Vert u \Vert_{L^1}+\vert u\vert_{BV}$.
Equipped with this norm the space of $BV$ functions is complete. The completeness of the $BV$ space follows from the completeness of $L^1$ and lower semicontinuity property which is stated below.

Proposition about the lower semicontinuity property of $BV-$ seminorm:
If $\{u_n\}$ is a sequence in $BV(\Omega)$ with $\sup_n |u_n|_{BV}< \infty$ that converges strongly $u_n \rightarrow u$ in $L^1(\Omega)$ then $|u|_{BV}\leq\lim \inf_{n\rightarrow \infty} |u_n|_{BV}$ and $u\in BV(\Omega)$.
We use the following definition of BV seminorm here: $u \in L^1(\Omega)$ and $\vert u \vert_{BV}=\sup \{\int_{\Omega} u \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}<\infty$.
Let $\phi\in C_c^1(\Omega, \mathbb{R}^N)$ with $\Vert \phi \Vert_{\infty}\leq 1$.
We first observe that
$$\lim_{n\rightarrow \infty}\int_{\Omega} u_n\, \mbox{ div } \phi =\int_{\Omega} u\, \mbox{ div } \phi. \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(1)$$
This follows as $u_n\rightarrow u$ in $L^1(\Omega)$ strongly, and that $\phi\in C_c^1(\Omega, \mathbb{R}^N)$. Indeed, $$ \big\vert \int_{\Omega} u_n\, \mbox{ div } \phi - u\, \mbox{ div } \phi\, \big\vert \leq \int_{\Omega} |u_n-u|\cdot |\mbox{ div } \phi | \rightarrow 0,\mbox{ as } n \rightarrow \infty.$$ Note that $ \int_{\Omega}u_n \mbox{ div } \phi \leq \sup\{\int_{\Omega} u_n \,\mbox{ div } \mathbf{\phi}: \mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1\}$, i.e. $$\int_{\Omega}u_n \mbox{ div } \phi \leq |u_n|_{BV}.$$ Taking $\lim\inf$ of both sides, we get $$\lim_{n\rightarrow \infty}\int_{\Omega}u_n \mbox{ div } \phi \leq \lim\inf_{n\rightarrow \infty} |u_n|_{BV}\,.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(2)$$ From (1) and (2) we get
$$\int_{\Omega}u \mbox{ div } \phi \leq \lim\inf_{n\rightarrow \infty} |u_n|_{BV}\,.\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(3)$$
Taking supremum on the left side of (3) over all $\mathbf{\phi} \in C_c^1(\Omega, \mathbb{R}^N) \mbox{ and } \Vert \mathbf{\phi} \Vert_{\infty}\leq 1$, we get $|u|_{BV}\leq\lim \inf_{n\rightarrow \infty} |u_n|_{BV}$. Moreover, if $|u_n|_{BV}<\infty$ for all $n$ we get $|u|_{BV}<\infty$, i.e. $u\in BV$.

The weak convergence of $u_n\rightharpoonup u$ in $BV\,$ :
We say that a sequence $u_n$ in $BV(\Omega)$ converges weakly to some $u$ in $BV(\Omega)$ (i.e. $u_n\rightharpoonup u$ in $BV(\Omega)$) if and only if the following two convergences hold:
(i) $u_n\rightarrow u$ strongly in $L^1(\Omega)$
(ii) $Du_n \rightharpoonup Du$ weakly in $M(\Omega, \mathbb(R)^N)$.

Proposition: If $\{u_n\}$ is a sequence in $BV(\Omega)$ with $\sup_n |u_n|_{BV}< \infty$ that converges strongly $u_n \rightarrow u$ in $L^1(\Omega)$ then $u_n\rightharpoonup u$ in $BV$.
As $u_n\rightarrow u$ in $L^1$ we only have to show the weak convergence $Du_n\rightharpoonup Du$.

For $\phi\in C_c^{\infty}(\Omega, \mathbb{R}^N)$ we have that $\langle Du_n, \phi\rangle =-\int_{\Omega}u_n \mbox{ div }\phi\rightarrow -\int_{\Omega}u \mbox{ div }\phi =\langle Du, \phi\rangle$.

As result of the density of $C_c^{\infty}(\Omega, \mathbb{R}^N)$ in $C_0(\Omega, \mathbb{R}^N)$ and the boundedness of $|u_n|_{BV}$ we conclude that $Du_n\rightharpoonup Du$.

APPENDIX: Basic definitions

Let $X$ be some set, and $2^X$ symbolically represent its power set, the collection of all subsets of $X$.

Measure: A mapping $\mu:2^X\rightarrow [0, \infty]$ is called a measure on $X$ if
(i) $\mu(\emptyset)=0$ and
(ii) $\mu(A)\leq \sum_{k=1}^{\infty} \mu(A_k)$, whenever $A \subset \cup_{k=1}^{\infty} A_k$.

$\mu-$ measurable set: A set $A\subset X$ is $\mu-$ measurable if for each set $B\subset X$,
$\mu(B)=\mu(B\cap A)+\mu(B\setminus A)$.

$\sigma$-algebra: A subset $\mathcal{A} \subset 2^X$ is called a $\sigma$-algebra if it satisfies the following three properties:
(i) $\mathcal{A}$ contains the null set and the set $X$, i.e. $\emptyset, X \in \mathcal{A}$.
(ii) $\mathcal{A}$ is closed under complementation: $A \in \mathcal{A}$ implies $X\setminus A \in \mathcal{A}$.
(iii) $\mathcal{A}$ is closed under countable unions: If $A_k \in \mathcal{A}$ for $k=1, 2, \dots$, then so is the union, $\cup_{k=1}^{\infty}A_k $.

Borel $\sigma$-algebra of $\mathbb{R}^n$ is the smallest $\sigma$-algebra of $\mathbb{R}^n$ containing the open subsets of $\mathbb{R}^n$.

Regular measure: A measure $\mu$ on $X$ is regular if for each set $A\subset X$ there exists a $\mu-$ measurable set $B$ such that $A\subset B$ and $\mu(A)=\mu(B)$.

Borel set: A Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement.

Borel measure: A measure $\mu$ on $\mathbb{R}^n$ is called Borel measure if every Borel set is $\mu-$ measurable.

Borel regular measure: A measure $\mu$ on $\mathbb{R}^n$ is called Borel regular measure if $\mu$ is Borel and for each $A \subset \mathbb{R}^n$ there exists a Borel set $B$ such that $A\subset B$ and $\mu(A)=\mu(B)$.

Radon measure: A measure $\mu$ on $\mathbb{R}^n$ is called Radon measure if $\mu$ is Borel regular and $\mu(K)< \infty$ for each compact set $K \subset \mathbb{R}^n$.

Tuesday, January 24, 2012

Segmentation of Boo's book

Segmentation is one of the most difficult problems in image processing, where the meaning of the problem depends on the context. For example, for the image of Boo, I want to segment only the book that he is reading in the following image.

Boo: the cutest dog in the world! 

Here is the segmentation result. I will talk about the code some other day.

The book that Boo reads