%gmChap15.tex

\graphicspath{{./guichard_morel/}}

\chapter{Viscosity Solutions}

This book is about image analysis and PDEs, and one of the main ideas we wish to convey is that the operators we have studied are closely associated with certain differential equations. What is more, we wish to show that whole groups of operators can be associated with essentially the same equation. For example, in Theorem 2.3 we proved that there were many linear operators that converged asymptotically to the heat equation, and in section 8.2 we showed how dilations and erosions are associated with the equations $\partial u/\partial t=\pm|Du|$. There is, however, a gap to fill. As Figures 15.1 and 15.2 illustrate, applying dilations and erosions to smooth functions can produce functions that are no longer $C^1$ and, hence, cannot satisfy $\partial u/\partial t=\pm|Du|$ in the usual, or classical, sense. The notion of viscosity solution, which is a late twentieth-century development, provides a way to close this gap. In this chapter, we introduce viscosity solutions, show that classical solutions are viscosity solutions, and quote a uniqueness theorem. We close the gap in the next chapter by showing that the approximate solutions generated by the iterated filters we have studied do indeed converge to viscosity solutions of their associated PDEs.

\section{Definition and main properties} 

The functions $u:[0,\infty)\times\RR^N$ will always be continuous. If $u$ is $C^2$, then $Du$ and $D^2u$ denote the first and second derivatives of $u$ with respect to $\fxx\in\RR^N$; $Du$ is an $N$-dimensional vector and $D^2u$ is an $N\times N$ matrix. If $\fxx\in\RR^N$ is represented in an orthonormal basis by $\fxx=(x_1,x_2,\ldots,x_N)$, then the elements of $D^2u$ are $u_{ij}=\partial^2u/\partial x_i\partial x_j$, and $D^2u$ is symmetric. Symmetric matrices and their associated quadratic forms play a central role in this chapter because they can be ordered. A real symmetric matrix $A=(a_{ij})_{1\leq i,j\leq N}$ is said to be nonnegative if its associated quadratic form is nonnegative, that is, if
\[
A(\fxz,\fxz)=\sum_{i,j=1}^Na_{ij}\fxz_i\fxz_j\geq0
\]
for all $\fxz\in\RR^N$. This is equivalent to saying that all of the eigenvalues of $A$ are greater than or equal to zero. We say that $A\geq B$ if $A-B\geq0$. The parabolic PDEs that we consider are of the form $\partial u/\partial t=F(D^2u, Du, \fxx, t)$, where $(A,p,\fxx,t)\mapsto F(A,p,\fxx,t)$ is real-valued and continuous on its domain of definition. We also assume that $F$ is nondecreasing with respect to its first argument. What we mean by this is that, for all $A$, $B$, $p$, $\fxx$, and 
$t$ in the domain of definition,
\begin{equation}\label{eq171}
A\geq B \Longrightarrow F(A,p,\fxx,t)\geq F(B,p,\fxx,t).
\end{equation}

The functions $F$ we consider fall into two classes that are characterized by the domains of definition. In one case, $F$ is defined for all real-valued $N\times N$ symmetric matrices $A$, all $p\in\RR^N$, all $\fxx\in\RR$, and all $t\in[0,\infty)$. We denote this domain by $\mathbb D^N$. If we denote the $N(N-1)/2$-dimensional space of symmetric $N\times N$ matrices by ${\mathbb S}^N$, then 
\[
\mathbb D^N={\mathbb S}^N\times\RR^N\times\RR\times[0,\infty).
\]
In the other case, $F$ is defined on 
\[
{\tilde{\mathbb D}}^N={\mathbb S}^N\times(\RR^N\setminus\{0\})\times\RR\times[0,\infty),
\]
where $\RR^N\setminus\{0\}$ is $\RR^N$ with the origin removed. It is important to deal with functions $F$ that are defined on ${\tilde{\mathbb D}}^N$ rather than ${\mathbb D}^N$ because this is the case for one of the most relevant  equations in the book, namely, the curvature equation $\partial u/\partial t=|Du|{\rm curv}(u)$. (Note that we have shifted the notation: In this chapter, $p=Du$ rather than $p=|Du|$ as before.) It is this dichotomy of domains that motivates the following definition.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig15.01.1.eps}
}
\caption[Erosions and dilations can create singularities]{Erosions and dilations can create singularities. Top-left: original $C^\infty$ image.  Below: representation of the intensity along the horizontal axis. Middle: dilation with a circle of 30 pixels. Below: at the central point, the image is no longer $C^\infty$ or even $C^1$. Right: erosion with the same circle. Below: some loss of regularity; the solution is no longer $C^2$.
}
\end{figure}

\begin{definition}We say that a function $F$ is admissible if it is defined and continuous on ${\mathbb D}^N$ or ${\tilde{\mathbb D}}^N$, if it satisfies \eqref{eq171}, and if it satisfies the following conditions: There exists two continuous functions $G^+$ and $G^-$ defined on ${\mathbb D}^N$ such that 
\begin{equation}\label{eq172}
\begin{aligned}
&G^+(0,0,\fxx,t)=G^-(0,0,\fxx,t)=0,\\
&G^+(A,0,\fxx,t)\geq0\quad \text{and}\quad G^-(-A,0,\fxx,t)\leq0\quad \text{for all}\quad A\geq0,\\
&G^-(A,p,\fxx,t)\leq F(A,p,\fxx,t)\leq G^+(A,p,\fxx,t),
\end{aligned}
\end{equation}
for all $(A,p,\fxx,t)$ in the domain of $F$. 
\end{definition}

If $F$ is defined and continuous on ${\mathbb D}^N$, if $F$ satisfies \eqref{eq171}, and if $F(0,0,\fxx,t)=0$, then $F$ is admissible: Just let $G^\pm=F$. Conversely, if $F$ is admissible and defined on ${\mathbb D}^N$, then $F$ is continuous at $(0,0,\fxx,t)$ by definition, and the last line of \eqref{eq172} implies that $F(0,0,\fxx,t)=0$.

We are going to illustrate this definition by describing the functions $F$ that are associated with the PDEs that we have studied and that are of particular interest for image processing. This list will also serve as a reference for this and the next chapter. The analysis will rely on fundamental facts about real symmetric matrices, most of which are listed in section I.4 of the Introduction.

\begin{enumerate}[$\bullet$]\setlength\itemsep{2pt}
\item $F(A,p)=|p|$ or $F(A,p)=-|p|$. These functions are related to dilations and erosions and are associated with the equations $\partial u/\partial t=|Du|$ and $\partial u/\partial t=-|Du|$. They are clearly admissible.
\item $F(A,p)={\rm trace}(A)={\rm Tr}(A)$. This is associated with the heat equation $\partial u/\partial t=\Delta u$. $F$ is defined and continuous on $\mathbb D^N$. Since  ${\rm Tr}(A+B)={\rm Tr}(A)+{\rm Tr}(B)$ and ${\rm Tr}(A)\geq0$ for $A\geq0$, it follows that $F$ satisfies \eqref{eq171}. It satisfies \eqref{eq172} by taking $G^\pm=F$.
\item $F(A,p)={A(p^\perp/|p|,p^\perp/|p|)}$, which in two dimensions is 
\[
F(A,p)=\frac{p_1^2a_{22}-2p_1p_2a_{12}+p_2^2a_{11}}{|p|^2}.
\]
This function is related to the curvature equation $\partial u/\partial t=|Du|{\rm curv(u)}$. It is defined and continuous on $\tilde{\mathbb D}^N$. It clearly satisfies \eqref{eq171}. To see that it satisfies \eqref{eq172}, let $G^+(A)=\text{largest eigenvalue of $A$}$ and $G^-(A)=\text{smallest eigenvalue of $A$}$.
\item $F(A,p)=(A(p^\perp,p^\perp))^{1/3}$. This function is related to affine-invariant smoothing and is associated with the equation
\begin{equation}\label{eq173}
\frac{\partial u}{\partial t}=|Du|({\rm curv}(u))^{1/3}.
\end{equation}
This function is defined and continuous on $\mathbb D^N$ and clearly satisfies \eqref{eq171}. It satisfies \eqref{eq172} by taking $G^\pm=F$.
\item $F(A,p)=((A(p^\perp,p^\perp))^+)^{1/3}$ is associated with ${\partial u}/{\partial t}=|Du|({\rm curv}(u)^+)^{1/3}$. Once we note that the operation $f\mapsto f^+$ preserves continuity and order, the argument in the last item shows that $F$ is admissible.
\item $F(A,p)={\rm Tr}(A)-A(p/|p|,p/|p|)$ is associated with
\[
\frac{\partial u}{\partial t}=|Du|\Big(\sum_{i=1}^{N-1}\kappa_i(u)\Big),
\]
where the $\kappa_i(u)$ are the principal curvatures of $u$ (see Proposition 4.21). In other words, this is the equation for mean curvature motion. $F$ is defined and continuous on $\tilde{\mathbb D}^N$, and it is easy to see that $F(A,p)\geq0$ for $A\geq0$. It follows from this that $F$ satisfies \eqref{eq171}. To satisfy \eqref{eq172}, we can take $G^+(A)=(N-1)(\text{maximum eigenvalue of}\, A)$ and $G^-(A)=(N-1)(\text{minimum eigenvalue of}\, A)$.
\item $F(A,p)=\min_{p}A(p^\perp/|p|,p^\perp/|p|)$ is associated with ${\partial u}/{\partial t}=|Du|\min\{\kappa_1,\kappa_2\}$ in three dimensions. 
\end{enumerate} 



\begin{figure}[!t]
\setkeys{Gin}{width=8cm}
\centerline{
\includegraphics{fig15.02.1.eps}
}
\caption[Erosion and dilation can generate singularities within the level lines]
{Erosion and dilation can generate singularities within
the level lines. Left: original image where the only level-line, corresponding to the boundary of the black shape, is $C^2$. Right: erosion with a circle of radius 10; the resulting level lines have sharp angles.
}
\end{figure}

We are going to define viscosity solution for these and other PDEs, but before doing so it is useful to say a few words about solutions in general. It would be convenient to define solutions to the equations listed above by saying that any $u$ that is $C^2$ on $\RR^N$ and $C^1$ on $[0,\infty)$ and satisfies $\partial u/\partial t=F(D^2u,Du,\fxx,t)$ at all points $(t,\fxx)$ is a solution. Indeed, we call such a $u$ a \textit{classical} solution. This definition works well, for example, for the heat equation, where we have shown the existence of classical solutions. There are, however, among the equations listed above, those for which a $C^2$ solution, or even a $C^1$ solution, cannot be expected. Here is an example where an ostensibly classical solution is not the correct one and violates the comparison principle, which says that $v_0\geq u_0$ implies that $v\geq u$. Let $u_0(\fxx)=-|\fxx|$ be the initial condition. Then one is tempted to take as a solution for the equation $\partial u/\partial t=|Du|$ the function $\tilde{u}(t,\fxx)= t-|\fxx|$. Indeed, for all $t\geq0$ and all $\fxx\not=0$, $\partial\tilde{u}/\partial t=1=|D\tilde{u}|$. However, this ``solution'' violates the comparison principle. This can be checked by comparing it with the $C^{\infty}$ solution of the same equation with initial condition $v_0(\fxx)\equiv0$, which is clearly $v(t,\fxx)\equiv0$. The correct comparison-preserving solution is, in fact, $u(t,\fxx)=\min\{0,t-|\fxx|\}$. One way to work around this difficulty is to use contrast invariance: Let $g:\RR\to\RR$ be a nondecreasing continuous function that is  not $C^1$, and let $u_0(\fxx)$, $\fxx\in\RR^N$, be the initial data. Assume that we have been able to define a classical solution $u$ for a curvature equation like \eqref{eq173} (or, in $\RR^N$, a mean curvature motion equation) that satisfies the initial condition $u(0,\fxx)=u_0(\fxx)$. Then it is reasonable to expect that $g(u)$ will be a solution of the same equation with initial condition $g(u_0)$. Since $g$ is not $C^1$, we cannot expect this solution will be $C^1$. The most we can expect is that it is continuous.

Another way to define an irregular function $u$ as a solution of a PDE is to compare it with classical solutions of the PDE. This idea is made precise in the next definition.

\begin{definition}[viscosity solution]$F$ is assumed to be an admissible function, and $u:[0,\infty)\times\RR^N\to\RR$ is assumed to be continuous. We say that $u$ is a viscosity subsolution of the equation
\begin{equation}\label{eq174}
\frac{\partial u}{\partial t}(t,\fxx)-F(D^2u(t,\fxx),Du(t,\fxx),\fxx,t)=0
\end{equation}
at the point $\fxx_0$ and scale $t_0$ if, for all $\varphi\in C^\infty([0,\infty)\times\RR^N)$ for which $(t_0,\fxx_0)$ is a strict local maximum of $u-\varphi$, the following conditions are true$:$

If $D\varphi(t_0,\fxx_0)\not=0$, then
\begin{equation}\label{eq175}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-F(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\leq0.
\end{equation}

If $D\varphi(t_0,\fxx_0)=0$ and $D^2\varphi(t_0,\fxx_0)=0$, then
\begin{equation}\label{eq176}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)\leq0.
\end{equation}


Similarly, $u$ is a viscosity supersolution at $(t_0,\fxx_0)$ if, for all $\varphi\in C^\infty([0,\infty)\times\RR^N)$ for which $(t_0,\fxx_0)$ is a strict local minimum of $u-\varphi$, the following conditions are true$:$

If $D\varphi(t_0,\fxx_0)\not=0$, then
\begin{equation}\label{eq177}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-F(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\geq0.
\end{equation}

If $D\varphi(t_0,\fxx_0)=0$ and $D^2\varphi(t_0,\fxx_0)=0$, then
\begin{equation}\label{eq178}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)\geq0.
\end{equation}

The function $u$ is said to be a viscosity solution at the point $\fxx_0$ and scale $t_0$ if it is both a viscosity subsolution and supersolution. If $u$ is a viscosity solution of \eqref{eq174} at every point of $[0,\infty)\times\RR^N$ and if $u(0,\fxx)=u_0(\fxx)$, we say that $u$ is a viscosity solution of \eqref{eq174} with initial condition $u_0$.
\end{definition}

One of the first things we must do is show that a classical solution of \eqref{eq174} is a viscosity solution. This will be done in Proposition 15.10, but before tackling this issue, we present several lemmas that significantly simplify the task of showing that a function is a viscosity solution. We will prove these lemmas for subsolutions; all of the statements and proofs regarding subsolutions are true for supersolutions with the obvious modifications. The first step is to drop the requirement that the extrema be strict.

\begin{lemma}A continuous function $u:[0,\infty)\times\RR^N\to\RR$ is a viscosity subsolution of \eqref{eq174} at $(t_0,\fxx_0)$ if and only if the following condition is true. If $\varphi$ is in $C^\infty([0,\infty)\times\RR^N)$ and $u-\varphi$ has a local maximum $($not necessarily strict$)$ at $(t_0,\fxx_0)$, then \eqref{eq175} and \eqref{eq176} hold. A similar statement is true for viscosity supersolutions.
\end{lemma} 
\begin{proof}Assume that $u$ is a viscosity subsolution and that $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$. Replace $\varphi$ with $\psi$, where $\psi(t,\fxx)=\varphi(t,\fxx)+(t-t_0)^4+|\fxx-\fxx_0|^4$. Then $u-\psi$ has a strict local maximum at $(t_0,\fxx_0)$, and  $\psi$ satisfies \eqref{eq175} and \eqref{eq176} by definition. Since the first and second derivatives of $\varphi$ and $\psi$ agree at $(t_0,\fxx_0)$, $\varphi$ satisfies \eqref{eq175} and \eqref{eq176}. The implication in the other direction is just a matter of noting that ``local maximum'' includes ``strict local maximum.'' A dual argument proves the statement for supersolutions.
\end{proof}

The relations \eqref{eq175}-\eqref{eq178} do not provide a bound for $\partial\varphi/\partial t$ in case $D\varphi=0$ and $D^2\varphi\not=0$. This due to the possibility that $F$ is defined on ${\tilde{\mathbb D}}^N$ and cannot be continued continuously at $p=0$. The next lemma provides an equivalent definition of viscosity solution that cover this case by using the fact that $F$ is admissible.

\begin{lemma}Assume that $F$ is admissible and that $G^+$ and $G^-$ are any two continuous functions that satisfy the conditions of \eqref{eq172}. A continuous function $u$ is a viscosity subsolution of \eqref{eq174} at a point $(t_0,\fxx_0)$ if and only if, for all $\varphi\in C^\infty([0,\infty)\times\RR^N)$ for which $(t_0,\fxx_0)$ is a strict local maximum of $u-\varphi$, $\varphi$ satisfies \eqref{eq175} and 
\begin{equation}\label{eq179}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-G^+(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\leq0.
\end{equation}
Similarly, $u$ is a viscosity supersolution of \eqref{eq174} at a point $(t_0,\fxx_0)$ if and only if, for all $\varphi$ for which $(t_0,\fxx_0)$ is a strict local minimum of $u-\varphi$, $\varphi$ satisfies \eqref{eq177} and 
\begin{equation}\label{eq1710}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-G^-(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\geq0.
\end{equation}
In particular, if $F$ is continuous, then \eqref{eq175} and \eqref{eq177} are true even if $D\varphi(t_0,\fxx_0)=0$.
\end{lemma}
\begin{proof}The last statement is an immediate consequence of the other parts of the lemma.

We will prove only the ``subsolution'' half of the lemma. In one direction, we assume \eqref{eq175} and \eqref{eq179}. Then to show that the lemma implies the definition, we need only show that \eqref{eq176} holds. But this follows immediately from \eqref{eq179} and the fact that $G^+(0,0,\fxx,t)=0$.

To prove the converse, assume that $u$ is a viscosity subsolution in the sense of Definition 17.2, that is, it ``satisfies'' \eqref{eq175} and \eqref{eq176}, and assume that $\varphi$ is a $C^\infty$ function such that $u-\varphi$ has a strict maximum at $(t_0,\fxx_0)$. We must prove that \eqref{eq179} is true for any continuous $G^+$ that satisfies conditions \eqref{eq172}. We assume that $D\varphi(t_0,\fxx_0)=0$ and $D^2(t_0,\fxx_0)\not=0$, since the other cases follow immediately. 

Consider the function $\psi_\ve$ defined by
\[
\psi_\ve(t,\fxx,\fxy)=u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve},\quad\ve>0.
\]
Since $u-\varphi$ has a strict maximum at $(t_0,\fxx_0)$, it is possible to show that, for every sufficiently small $\ve$, there is a $(t_{\ve},\fxx_{\ve},\fxy_{\ve})$ where the function $\psi_\ve$ has a local maximum (Exercise 15.1). Furthermore, $(t_{\ve},\fxx_{\ve},\fxy_{\ve})\to(t_0,\fxx_0,\fxx_0)$ as $\ve\to0$. (The points $(t_{\ve},\fxx_{\ve},\fxy_{\ve})$ may not be unique, so assume, using the axiom of choice, that we have selected one for each sufficiently small $\ve$.) 


If we fix $\fxx=\fxx_{\ve}$, then the function $\psi_{\ve,\fxx_{\ve}}:(t,\fxx_{\ve},\fxy)\mapsto \psi_{\ve}(t,\fxx_{\ve},\fxy)$ is $C^\infty$ with respect to $\fxy$ and has a local maximum at the point $(t_{\ve},\fxy_{\ve})$. 

This implies that $D\psi_{\ve,\fxx_{\ve}}(t_{\ve},\fxx_{\ve},\fxy_{\ve})=0$ and that $D^2\psi_{\ve,\fxx_{\ve}}(t_{\ve},\fxx_{\ve},\fxy_{\ve})\leq0$.  By computing $D\psi_{\ve,\fxx_{\ve}}$ and $D^2\psi_{\ve,\fxx_{\ve}}$ and using these relations, we see that 
\[
D\varphi(t_\ve,\fxy_\ve)=\frac{4(\fxx_\ve-\fxy_\ve)|\fxx_\ve-\fxy_\ve|^2}{\ve}
\]
and
\[
D^2\varphi(t_\ve,\fxy_\ve)\geq-\frac1{\ve}(4|\fxx_\ve-\fxy_\ve|^2{I}+8A),
\]
where ${I}$ is the identity matrix and $A=(\fxx_\ve-\fxy_\ve)\otimes(\fxx_\ve-\fxy_\ve)$. (If we write $A=(a_{ij})$, then  $a_{ij}=(\fxx_{\ve i}-\fxy_{\ve i})(\fxx_{\ve j}-\fxy_{\ve j})$.) We now consider two cases.

\medskip 

\noindent {\bf Case (1):} $D\varphi(t_\ve,\fxy_\ve)=0$.
\medskip 

This means that $\fxx_\ve=\fxy_\ve$, which in turn implies that $D^2\varphi(t_\ve,\fxy_\ve)\geq0$. Thus, for any $G^+$ that satisfies \eqref{eq172}, 
$G^+(D^2\varphi(t_\ve,\fxy_\ve),0,\fxy_\ve,t_\ve)\geq0$.

We now take another point of view: Fix $\fxy=\fxy_\ve$ and consider the function
\[
\psi_{\ve,\fxy_\ve}(t,\fxx,\fxy_\ve)=u(t,\fxx)-\varphi(t,\fxy_\ve)-\frac{|\fxx-\fxy_\ve|^4}{\ve}=u(t,\fxx)-\varphi_\ve(t,\fxx).
\]
This function has a local maximum at $(t_\ve,\fxx_\ve)$. Furthermore, $D\varphi_\ve(t_\ve,\fxx_\ve)=D\varphi(t_\ve,\fxx_\ve)=0$, and $D^2\varphi_\ve(t_\ve,\fxx_\ve)=0$. Thus, Lemma 15.3 applies, and \eqref{eq176} holds:
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxx_\ve)\leq0.
\]
Since $\fxx_\ve=\fxy_\ve$ and $G^+(D^2\varphi(t_\ve,\fxy_\ve),0,\fxy_\ve,t_\ve)\geq0$, it follows that
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxy_\ve)\leq G^+(D^2\varphi(t_\ve,\fxy_\ve),0,\fxy_\ve,t_\ve).
\]
Both ${\partial\varphi}/{\partial t}$ and $G^+$ are continuous in all of their variables, so by letting $\ve$ tend to zero we arrive at the inequality \eqref{eq179}.

\medskip 

\noindent {\bf Case (2):} $D\varphi(t_\ve,\fxy_\ve)\not=0$.
\medskip

Note that the function
\[
(t,\fxx)\mapsto u(t,\fxx)-\varphi(t,\fxx-(\fxx_\ve-\fxy_\ve))-\frac{|\fxx-\fxy_\ve|^4}{\ve}=u(t,\fxx)-\vartheta_\ve(t,\fxx)
\]
has a local maximum at $(t_\ve,\fxx_\ve)$. This means that Lemma 15.3 applies to $\vartheta_\ve$. Since $D\varphi_\ve(t_\ve,\fxy_\ve)=D\vartheta_\ve(t_\ve,\fxy_\ve)\not=0$ and $D^2\varphi(t_\ve,\fxy_\ve)=D^2\vartheta_\ve(t_\ve,\fxy_\ve)$, we have
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxy_\ve)\leq F(D^2\varphi(t_\ve,\fxy_\ve),D\varphi(t_\ve,\fxy_\ve),\fxy_\ve,t_\ve)\leq G^+(D^2\varphi(t_\ve,\fxy_\ve),D\varphi(t_\ve,\fxy_\ve),\fxy_\ve,t_\ve),
\]
using \eqref{eq175} and \eqref{eq172}. Again, letting $\ve$ tend to zero gives \eqref{eq179}.
\end{proof}

\begin{exercise}The exercise is to prove the existence of the points $(t_\ve,\fxx_\ve,\fxy_\ve)$ where $\psi_\ve$ has local maxima and that tend to  $(t_0,\fxx_0,\fxy_0)$ as $\ve\to0$. Here is one way to proceed: Since $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$, we can choose an $r$ such that $u(t,\fxx)-\varphi(t,\fxx)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)=\lambda$ for $(t,\fxx)\in\overline{D}((t_0,\fxx_0),r)=\overline{D}$. For any $(t,\fxx),(t,\fxy)\in \overline{D}$ we have
\[
u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve}\leq\sup_{(t,\fxx),(t,\fxy)\in \overline{D}}\Big(u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve}\Big).
\]
Let $\fxx=\fxy=\fxx_0$ on the left-hand side, so
\[
\lambda\leq\sup_{(t,\fxx),(t,\fxy)\in \overline{D}}\Big(u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve}\Big).
\]
For each $\ve>0$, there is some point $(t_\ve,\fxx_\ve,\fxy_\ve)$ where the supremum is attained. Now argue that these points must tend to  $(t_0,\fxx_0,\fxy_0)$ as $\ve\to0$. (This is where the fact that $(t_0,\fxx_0,\fxy_0)$ is ``strict'' is used.) Hence, for small enough $\ve$ the points $(t_\ve,\fxx_\ve,\fxy_\ve)$ must all be in the interior of $\overline{D}$ and are therefore \textit{local} maximum points.  \finex
\end{exercise}

The next lemma provides another simplification for verifying that a function $u$ is a viscosity solution of \eqref{eq174}. It shows that it is possible to use test functions for which the variables are separated. 

\begin{lemma}To show that $u$ is a viscosity subsolution (or supersolution), it suffices to use test functions $\varphi\in C^\infty([0,\infty)\times\RR^N)$ of the form $\varphi(t,\fxx)=f(\fxx)+g(t)$.
\end{lemma}  
\begin{proof} This is the assumption: If a function of the form $\varphi(t,\fxx)=f(\fxx)+g(t)$ is such that $u-\varphi$ attains a local maximum at $(t_0,\fxx_0)$, then \eqref{eq175} and \eqref{eq179} follow. From this assumption, we must prove: If $\varphi$ is any function in $C^\infty([0,\infty)\times\RR^N)$ such that $u-\varphi$ attains a local maximum, then \eqref{eq175} and \eqref{eq179} follow. The technique for doing this is to develop $\varphi$ is a Taylor series and separate the variables. To keep the notation manageable, we will assume that $(t_0,\fxx_0)=(0,0)=0$. (Of course, $t=0$ is topologically a special point, but there will be no loss of generality in our presentation.) With this assumption, the Taylor expansion of $\varphi$ is
\[
\varphi(t,\fxx)= a+bt+\langle p,\fxx\rangle+ct^2+\langle Q\fxx,\fxx\rangle+t\langle q,\fxx\rangle+o(|\fxx|^2+t^2),
\]
where $a=\varphi(0)$, $b=\partial\varphi/\partial t(0)$, $c=(1/2)\partial^2\varphi/\partial t^2(0)$, $Q=(1/2)D^2\varphi(0)$, and
\[
q=\Big(\frac{\partial^2\varphi}{\partial x_1\partial t}(0),\ldots,\frac{\partial^2\varphi}{\partial x_N\partial t}(0)\Big). 
\]
For $\ve>0$, we define
\[
f(\fxx)=a+\langle p,\fxx\rangle+\langle Q\fxx,\fxx\rangle+\ve|\fxx|^2+\ve|q||\fxx|^2
\]
and
\[
g(t)=bt+\frac{|q|}{\ve}t^2+\ve t^2+ct^2.
\]
This means that 
\[
\varphi(t,\fxx)=f(\fxx)+g(t)-\Big(\ve|q||\fxx|^2+\frac{|q|}{\ve}t^2-t\langle q,\fxx\rangle+\ve(|\fxx|^2+t^2)\Big)+o(|\fxx|^2+t^2).
\]
Since, by the Cauchy--Schwartz inequality, $\ve|q||\fxx|^2+(|q|/\ve)t^2-t\langle q,\fxx\rangle\geq0$, we have $\varphi(t,\fxx)\leq f(\fxx)+g(t)$ for all sufficiently small $(t,\fxx)$. Thus, in some neighborhood of $(t_0,\fxx_0)$, $u(t,\fxx)-\varphi(t,\fxx)\geq u(t,\fxx)-f(\fxx)-g(t)$. The assumption is that $u-\varphi$ has a local maximum at $(0,0)$, so this last inequality implies that $u-f-g$ has a local maximum at $(0,0)$. Thus, by assumption, 
\eqref{eq175} and \eqref{eq179} hold for $f+g$. More precisely, we have the following two cases.
\medskip 

\noindent {\bf Case (1):} $D(f+g)(0)\not=0$.
\medskip 

From \eqref{eq175}, 
\[
\frac{\partial (f+g)}{\partial t}(0)\leq F(D^2(f+g)(0),D(f+g)(0),0,0).
\]
It is easy to see that $D\varphi(0)=D(f+g)(0)\not=0$ and $(\partial\varphi/\partial t)(0)=(\partial (f+g)/\partial t)(0)$, and a short computation shows that $D^2(f+g)(0)=D^2\varphi(0)+2\ve(1+|q|)I)$. Substituting these values in the expression above shows that
\[
\frac{\partial\varphi}{\partial t}(0)\leq F(D^2\varphi(0)+2\ve(1+|q|)I,D\varphi(0),0,0).
\]
We let $\ve\to0$ and use the continuity of $F$ to see that \eqref{eq175} holds for $\varphi$.
\medskip 

\noindent {\bf Case (2):} $D(f+g)(0)=0$.
\medskip 

In this case, \eqref{eq179} is true for $f+g$:
\[
\frac{\partial (f+g)}{\partial t}(0)\leq G^+(D^2(f+g)(0),D(f+g)(0),0,0).
\]
Letting $\ve\to0$ and using the continuity of $G^+$ yields  \eqref{eq179} for $\varphi$.
\end{proof}

\begin{exercise}We have just shown that the test functions in Definition 15.2 can be replaced with functions of the form $\varphi(t,\fxx)=f(\fxx)+g(t)$. This exercise is to show that the requirement can be weakened further by only requiring that $f$ belongs to any class $\mathcal C$ of $C^2$ functions that has the following property: For any $\fxx\in\RR^N$, any $a\in\RR$, any $p\in\RR^N$, and any symmetric $N\times N$ matrix $A$, there exists $f\in\mathcal C$ such that
\[
f(\fxx-\fxy)=a+\langle p,\fxx-\fxy\rangle +\frac1{2}\langle A(\fxx-\fxy),(\fxx-\fxy)\rangle+o(|\fxx-\fxy|^2).
\]
The same techniques used to prove Lemma 15.5 can be used to prove this result. One assumes the following: If a function of the form $\vartheta(t,\fxx)=f(\fxx)+g(t)$, $f\in C$, is such that $u-\vartheta$ attains a local maximum at $(t_0,\fxx_0)$, then \eqref{eq175} and \eqref{eq179} follow. From this assumption, one must prove: If $\varphi=f+g$, $f\in C^\infty(\RR^N)$, is such that $u-\varphi$ attains a local maximum at $(t_0,\fxx_0)$, then \eqref{eq175} and \eqref{eq179} follow. Another part of the exercise is to loosen the requirement on $g$. \finex
\end{exercise}

We are now in position to see how classical and viscosity solutions are related. The next two propositions show that the notion of viscosity solution is indeed a generalization of that of classical solution.

\begin{proposition}Let $F$ be an admissible function that is continuous everywhere, and assume $u:[0,\infty)\times\RR^N\to\RR$ is $C^2$ with respect to $\fxx$ and $C^1$ with respect to $t$. If $u$ is a classical solution of
\[
\frac{\partial u}{\partial t}(t,\fxx)=F(D^2u,Du,\fxx,t)
\]
at $(t_0,\fxx_0)$, then $u$ is a viscosity solution at $(t_0,\fxx_0)$.
\end{proposition}

\begin{proof}We prove this for the case $Du(t_0,\fxx_0)\not=0$. (The other cases follow immediately.) Thus, let $\varphi\in C^\infty([0,\infty)\times\RR^N)$ be such that $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$. This implies that $(\partial u/\partial t, Du)(t_0,\fxx_0)=(\partial\varphi/\partial t, D\varphi)(t_0,\fxx_0)$ and that $D^2(u-\varphi)(t_0,\fxx_0)\leq0$, so
\[
D^2u(t_0,\fxx_0)\leq D^2\varphi(t_0,\fxx_0).
\]
Hence,
\begin{align*}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)=\frac{\partial u}{\partial t}(t_0,\fxx_0)&=F(D^2u(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0)\\
&\leq F(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0).
\end{align*}
This proves that $u$ is a viscosity supersolution. A similar argument shows that it is a viscosity subsolution.
\end{proof}

\begin{proposition}Assume that $F$ is admissible and continuous everywhere. Let $u$ be a $C^2(\RR^+\times\RR^N)$ viscosity solution of $\partial u/\partial t=F(D^2u,Du,\fxx,t)$. Then $u$ is a classical solution of the same equation.
\end{proposition}
\begin{proof}Assume that $u$ is a viscosity solution at the point $(t_0,\fxx_0)$. We write the second-order Taylor expansion of $u$ in the $N+1$ variables near $(t_0,\fxx_0)$ as
\begin{align*}
u(t,\fxx)=&\,u(t_0,\fxx_0)+\langle\tilde{D}u(t_0,\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle\\
&+\langle\tilde{D}^2u(t_0,\fxx_0)(t-t_0,\fxx-\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle+o(|t-t_0|^2+|\fxx-\fxx_0|^2),
\end{align*} 
where the operators $\tilde{D}$ and $\tilde{D}^2$ involve all $N+1$ variables. For $\ve>0$, define $\varphi_\ve$ by
\begin{align*}
\varphi_\ve(t,\fxx)=u(t_0,\fxx_0)&+\langle\tilde{D}u(t_0,\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle\\
&+\langle(\tilde{D}^2u(t_0,\fxx_0)+\ve I)(t-t_0,\fxx-\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle.
\end{align*}
Thus,
\[
u(t,\fxx)-\varphi_\ve(t,\fxx)=-\ve(|t-t_0|^2+|\fxx-\fxx_0|^2)+o(|t-t_0|^2+|\fxx-\fxx_0|^2)
\]
and the point $(t_0,\fxx_0)$ is a local maximum of $u-\varphi_\ve$ for all $\ve>0$. Similarly, $(t_0,\fxx_0)$ is a local minimum of $u-\varphi_{-\ve}$. The test functions $\varphi_\ve$ and $\varphi_{-\ve}$ are $C^\infty$, so we can apply Definition 15.2 directly. Thus,
\begin{align*}
\frac{\partial u}{\partial t}(t_0,\fxx_0)=\frac{\partial\varphi_\ve}{\partial t}(t_0,\fxx_0)&\leq F(D^2\varphi_\ve(t_0,\fxx_0),D\varphi_\ve(t_0,\fxx_0),\fxx_0,t_0)\\
&=F((D^2u+\ve I)(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0),
\end{align*}
and
\begin{align*}
\frac{\partial u}{\partial t}(t_0,\fxx_0)=\frac{\partial\varphi_{-\ve}}{\partial t}(t_0,\fxx_0)&\geq F(D^2\varphi_{-\ve}(t_0,\fxx_0),D\varphi_\ve(t_0,\fxx_0),\fxx_0,t_0)\\
&=F((D^2u-\ve I)(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0).
\end{align*}
Letting $\ve\to0$ and using the continuity of $F$ shows that
\[
\frac{\partial u}{\partial t}(t_0,\fxx_0)=F(D^2u(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0).\qedhere
\]
\end{proof}

\section{An application to mathematical morphology}

In Proposition 8.8, we showed that $u(t,\fxx)=D_tu_0(\fxx)$ is a solution of $\partial u/\partial t=|Du|$ at each point $(t_0,\fxx_0)$ where $u$ is $C^1$. We are now going to prove that $u$ is a viscosity solution of this equation at all points.

\begin{theorem}Assume that $u_0\in C(\RR^N)$. Let $D(0,1)$ be the unit ball in $\RR^N$ and let $u$ be defined by
\[
u(t,\fxx)=D_tu_0(\fxx)=\sup_{\fxy\in tD(0,1)}u_0(\fxx+\fxy).
\]
Then $u$ is a viscosity solution of
\begin{equation}\label{eq1711}
\frac{\partial u}{\partial t}=|Du|,\quad u(0,\fxx)=u_0(\fxx).
\end{equation}
\end{theorem}

\begin{proof}We will use that fact that the dilation $D_t$ is recursive, that is, $D_{s+t}=D_sD_t$ (see Proposition 8.7). In particular, for $t>0$, $D_t=D_hD_{t-h}$, so
\begin{equation}\label{eq1712}
u(t,\fxx)=\sup_{|\fxy|<h}u(t-h,\fxx+\fxy).
\end{equation}

Let $\varphi$ be a $C^\infty$ test function and assume that $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$. To prove that $u$ is a viscosity subsolution of \eqref{eq1711}, we must show that
\[ 
\frac{\partial u}{\partial t}(t_0,\fxx_0)-|Du(t_0,\fxx_0)|\leq0.
\]
Since $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$, we have for sufficiently small $h$ and $|\fxy|$,
\[
u(t_0-h,\fxx_0+\fxy)-\varphi(t_0-h,\fxx_0+\fxy)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)
\]
It follow that
\[
\sup_{|\fxy|<h}u(t_0-h,\fxx_0+\fxy)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)+\sup_{|\fxy|<h}\varphi(t_0-h,\fxx_0+\fxy),
\]
and using \eqref{eq1712} shows that
\[
u(t_0,\fxx_0)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)+\sup_{|\fxy|<h}\varphi(t_0-h,\fxx_0+\fxy).
\]
Thus,
\[
\varphi(t_0,\fxx_0)\leq\sup_{|\fxy|<h}\varphi(t_0-h,\fxx_0+\fxy).
\]
Subtracting $\varphi(t_0-h,\fxx_0)$ from both sides shows that
\[
\varphi(t_0,\fxx_0)-\varphi(t_0-h,\fxx_0)\leq\sup_{|\fxy|<h}\big(\varphi(t_0-h,\fxx_0+\fxy)-\varphi(t_0-h,\fxx_0)\big).
\]
By writing $\varphi(t_0-h,\fxx_0+\fxy)-\varphi(t_0-h,\fxx_0)=\langle\tilde{D}\varphi(t_0,\fxx_0),(0,\fxy)\rangle+o(h+|\fxy|)$, we see that
\[
\varphi(t_0,\fxx_0)-\varphi(t_0-h,\fxx_0)\leq |D\varphi(t_0,\fxx_0)|h+o(h).
\]
Dividing both sides by $h$ and letting $h$ tend to zero shows that 
\[ 
\frac{\partial u}{\partial t}(t_0,\fxx_0)-|Du(t_0,\fxx_0)|\leq0.
\]
We have proven this under the assumption that $t_0>0$ and $h>0$ is sufficiently small. But by continuity, the last inequality is true for $t_0=0$. This proves that $u$ is a subsolution of \eqref{eq1711}; the proof that it is a supersolution is similar. The fact that $u(0,\fxx)=u_0(\fxx)$ is a direct consequence of the assumption that $u_0$ is continuous.
\end{proof}

\section{Approximation theory of viscosity solutions}

For simplicity, we consider slightly less general PDEs, namely, those of the form
\begin{equation}\label{eq1713}
\frac{\partial u}{\partial t}(t,\fxx)-F(D^2u(t,\fxx),Du(t,\fxx),\fxx)=0,
\end{equation}
where $(A,p,\fxx)\mapsto F(A,p,\fxx)$ is admissible, but it is independent of $t$. This is the case for the functions listed at the beginning of the chapter. For these equations, it is reasonable to expect that the operator $S_t:u_0\mapsto u(t,\cdot)$ could be approximated by iterations of an operator $T_h$, by which we mean that $(T_h)^n\to S_t$ in some sense as $h\to0$, $n\to\infty$. We have seen this in Theorem 2.3, where it was shown that a large class of linear operators converge asymptotically to the heat equation, and we have promised to show that whole classes of nonlinear operators converge asymptotically to other PDEs. We are mainly interested in operators that have been shown to be useful for image analysis and that have been studied in previous chapters. To include all of these operators in the theory, we give three definitions that abstract properties about their asymptotic and local behavior. These are properties one expects scaled operators $T_h$ must have if its iterates are to approximate $S_t$. 

\begin{definition}We say that a family of operators $T_h$, $0<h\leq1$, is $\alpha$-uniformly consistent with equation \eqref{eq1713}, if for every $C^3$ Lipschitz function $u$ the following conditions are true for some $\alpha\geq1:$


\medskip

If $Du(\fxx)\not=0$, then
\begin{equation}\label{eq1714}
T_hu(\fxx)-u(\fxx)=h^\alpha F(D^2u,Du,\fxx)+o(\fxx,h^\alpha),
\end{equation}
where $o(\fxx,h^\alpha)/h^\alpha\to0$ uniformly on any compact set $K\subset\{\fxx\mid Du(\fxx)\not=0\}$.

\medskip

There is a continuous function $G:(A,p,\fxx)\mapsto G(A,p,\fxx)$ and an $\epsilon>0$ such that $G(0,0,\fxx)=0$ and 
\begin{equation}\label{eq1715}
|T_hu(\fxx)-u(\fxx)|\leq h^\alpha G(D^2u(\fxx),Du(\fxx),\fxx)+C_Kh^{\alpha +\epsilon}
\end{equation}
for all $\fxx$ in any compact set $K$. The constant $C_K$ is assumed to depend only on $K$.
\end{definition}

\begin{definition}We say that a family of operators $T_h$, $0<h\leq1$, satisfies a $\beta$-uniform local comparison principle if the following is true$:$ Given any $L>0$ and any $L$-Lipschitz functions $u$ and $v$, there exist $\kappa>0$ and $C\geq0$ such that $u(\fxy)\leq v(\fxy)$ for $\fxy\in D(\fxx,r)$ implies that
\begin{equation}\label{eq1716}
T_hu(\fxx)\leq T_hv(\fxx)+Ch^\beta,
\end{equation} 
for all $h<\kappa$. Furthermore, it is assumed that $C$ and $\kappa$ depend only on $L$ and $r$. 
\end{definition}

Notice that if the condition ``$u(\fxy)\leq v(\fxy)$ for $\fxy\in D(\fxx,r)$'' holds uniformly for $\fxx$ in some set $S$, then the conclusion hold uniformly on $S$. If $T$ is an inf-sup operator whose structuring elements are uniformly bounded and $T_h$ is its scaled version, then \eqref{eq1716} is satisfied with $C=0$.

\begin{definition}Let $T_h$, $0<h\leq1$, be a family of operators that is $\alpha$-uniformly consistent with equation \eqref{eq1713}. The approximate solutions of \eqref{eq1713} generated by the $T_h$ with initial condition $u_0$ are the functions $(t,\fxx)\mapsto u_h(t,\fxx)$ defined for $0<h\leq1$ and $n\in \NN$ as follows:

\medskip

 For $t=nh^\alpha$, $u_h(t,\fxx)=T_h^nu_0(\fxx)$.
 
\medskip

 For $nh^\alpha\leq t\leq (n+1)h^\alpha$,
\[
u_h(t,\fxx)={\frac{t-nh^\alpha}{h^\alpha}u_h((n+1)h^\alpha,\fxx)+\frac{(n+1)h^\alpha-t}{h^\alpha}u_h(nh^\alpha,\fxx)}.
\]
\end{definition}

It follows immediately from the definition that $|u_h(t,\fxx)-u_h(t,\fxy)|\leq L|\fxx-\fxy|$ whenever $u_0$ is $L$-Lipschitz and $T$ satisfies the hypotheses of Lemma 6.5. Other properties of the approximate solutions will be developed in section 16.3

Here is a lemma will be useful for proving the next proposition. We leave the proof as an exercise. (Note the similarities of the ideas for the proof of this lemma and those used in Exercise 15.1.)

\begin{lemma} Let $v_k$ be a sequence of continuous functions that converges uniformly on a disk $\overline{D}(\fxx,r)$ to a function $v$. Assume that $\fxx$ is a strict maximum point for $v$ on $\overline{D}(\fxx,r)$, and let $\fxx_k$ be any point at which $v_k$ assumes its maximum on $\overline{D}(\fxx,r)$. Then $\fxx_k\to\fxx$ as $k\to\infty$.
\end{lemma}

The next proposition is known as the Barles--Souganidis principle for the approximation of viscosity solutions.

\begin{proposition}[Barles--Souganidis convergence theorem] Let $T_h$ be a family of operators that is $\alpha$-uniformly consistent with \eqref{eq1713}, that satisfies a $\beta$-uniform comparison principle, and such that the $T_h$ commute with the addition of constants. Assume that a sequence of approximate $L$-Lipschitz solutions $u_{h_k}$ converges uniformly on every compact set to a function $u$ as $h_k\to0$. If $\beta>\alpha$, then $u$ is a viscosity solution of \eqref{eq1713}.
\end{proposition}

\begin{proof}To simplify the notation, we will write $u_h$ rather than $u_{h_k}$. There should be no ambiguity, but one must keep in mind that we are working with a sequence and not a continuum. Let $\varphi$ be a $C^\infty$ test function, and assume that $u-\varphi$ attains a strict maximum at $(t,\fxx)$. Let $D=\overline{D}((t,\fxx),r)$ be a closed disk such that $(u-\varphi)(s,\fxy)<(u-\varphi)(t,\fxx)$ for all $(s,\fxy)\in D$, $(s,\fxy)\not=(t,\fxx)$. Since $u_h-\varphi\to u-\varphi$ uniformly on $D$, we know from Lemma 15.12 that there is a sequence $(t_h,\fxx_h)$ of points where $u_h-\varphi$ takes its maximum value on $D$ and that converges to $(t,\fxx)$. Eventually the points $(t_h,\fxx_h)$ are in the interior of $D$, so $(u_h-\varphi)(t_h,\fxx_h)$ is a {\em local} maximum of $u_h-\varphi$ for sufficiently small $h$ (that is, for large enough $k$).

For each $t_h$ there is an $n_h\in\NN$ such that $n_hh^\alpha\leq t_h<(n_h+1)h^\alpha$. Thus, for small enough $h$, we have
\begin{equation}\label{eq1717}
u_h((n_h-1)h^\alpha,\fxy)-\varphi((n_h-1)h^\alpha,\fxy)\leq u_h(t_h,\fxx_h)-\varphi(t_h,\fxx_h).
\end{equation}
The next step is to replace $t_h$ with $n_hh^\alpha$ in the right-hand side of \eqref{eq1717}. Assume first that $t_h\not=n_hh^\alpha$. Then by Definition 15.11, the function $u_h$ is linear in a neighborhood of $t_h$, and so $u_h-\varphi$ is $C^\infty$. Since $(u_h-\varphi)(t_h,\fxx_h)$ is a local maximum of $u_h-\varphi$, 
\begin{equation}\label{eq1717bis}
\frac{\partial u_h}{\partial t}(t_h,\fxx_h)-\frac{\partial\varphi}{\partial t}(t_h,\fxx_h)=0.
\end{equation} 

Now invoke Lemma 15.5 and assume that $\varphi$ is of the form $\varphi(s,\fxy)=f(\fxy)+g(s)$. By expanding $g$ around the point $s=t_h$, we have 
\[
g(n_hh^\alpha)=g(t_h)+g'(t_h)(t_h-n_hh^\alpha)+o_g(t_h-n_hh^\alpha),
\]
where $|o_g(t_h-n_hh^\alpha)|\leq C(t_h-n_hh^\alpha)^2$ and $C$ depends only on $g$ and $r$. This and \eqref{eq1717bis} imply that 
\begin{equation}\label{eq1718}
g(n_hh^\alpha)-g(t_h)=u_h(n_hh^\alpha,\fxx_h)-u_h(t_h,\fxx_h)+o_g(t_h-n_hh^\alpha).
\end{equation}
This relation is also true if $t_h=n_hh^\alpha$. It follows from inequality \eqref{eq1717} and \eqref{eq1718} that
\[
u_h((n_h-1)h^\alpha,\fxy)-\varphi((n_h-1)h^\alpha,\fxy)\leq u_h(n_hh^\alpha,\fxx_h)-\varphi(n_hh^\alpha,\fxx_h)+o_g(t_h-n_hh^\alpha),
\]
for all $\fxy$ such that $((n_h-1)h^\alpha,\fxy)\in D$. Therefore,
\[
u_h((n_h-1)h^\alpha,\fxy)\leq \varphi((n_h-1)h^\alpha,\fxy)+u_h(n_hh^\alpha,\fxx_h)-\varphi(n_hh^\alpha,\fxx_h)+o_g(t_h-n_hh^\alpha)
\]
for all sufficiently small $h$ and every $\fxy\in D(\fxx,r/2)$. Since $u_h$ is Lipschitz and $\varphi$ is locally Lipschitz, we can apply $T_h$ to both sides and of the last inequality and conclude from Definition 15.10 that, for sufficiently small $h$,  
\[
T_hu_h((n_h-1)h^\alpha,\cdot)(\fxx_h)\leq u_h(n_hh^\alpha,\fxx_h)-\varphi(n_hh^\alpha,\fxx_h)+
T_h(\varphi(n_h-1)h^\alpha,\cdot)(\fxx_h)+R(h),
\]
where the error term is now $R(h)=o_g(t_h-n_hh^\alpha)+Ch^\beta$.
If we write $\varphi$ in terms of $f$ and $g$ and note that  $T_h(u_h(n_h-1)h^\alpha,\cdot)(\fxx)=u_h(n_hh^\alpha,\fxx)$, we have
\[
g(n_hh^\alpha)-g((n_h-1)h^\alpha)\leq T_hf(\fxx_h)-f(\fxx_h)+o_g(t_h-n_hh^\alpha)+Ch^\beta,
\]
where we have again used the commutation of $T_h$ with the addition of constants.

We wish to apply the uniform consistency assumption (Definition 15.9), and for this there are two case. First, assume that $Df(\fxx)\not=0$. Then $Df(\fxx_h)\not=0$ for sufficiently small $h$, and we can apply \eqref{eq1714} to $\varphi=f+g$:
\[
T_hf(\fxx_h)-f(\fxx_h)=h^\alpha F(D^2f(\fxx_h),Df(\fxx_h),\fxx_h)+o(\fxx_h,h^\alpha).
\]
Thus,
\[
g(n_hh^\alpha)-g((n_h-1)h^\alpha)\leq h^\alpha F(D^2f(\fxx_h),Df(\fxx_h),\fxx_h)+o(h^\alpha)+o_g(t_h-n_hh^\alpha)+Ch^\beta.
\]
Divide this expression by $h^\alpha$ and let $h\to0$ and $n_h\to\infty$ so that $(n_hh^\alpha,\fxx_h)\to(t,\fxx)$. Since $\beta>\alpha$, $|o_g(t_h-n_hh^\alpha)|\leq C (t_h-n_hh^\alpha)^2$, and $F$ is continuous, we have
\[
\frac{\partial g}{\partial t}(t,\fxx)\leq F(D^2f(\fxx),Df(\fxx),\fxx).
\]
Since $\partial g/\partial t=\partial\varphi/\partial t$,
\[
\frac{\partial\varphi}{\partial t}(t,\fxx)\leq F(D^2f(\fxx),Df(\fxx),\fxx).
\]

Now assume that $Df(\fxx)=0$ and $D^2f(\fxx)=0$. We know nothing about $Df(\fxx_h)$, but in any case we deduce from the uniform consistency assumption (inequality \eqref{eq1715}), that
\[
|T_hf(\fxx_h)-f(\fxx_h)|\leq h^\alpha G(D^2f(\fxx_h),Df(\fxx_h),\fxx_h))+o(h^\alpha),
\]
where $G$ is continuous and $G(0,0,\fxx)=0$. Again, dividing this by $h^\alpha$ and letting $h\to0$ so that $(n_hh^\alpha,\fxx_h)\to(t,\fxx)$ and using the continuity of $G$ shows that
\[
\frac{\partial\varphi}{\partial t}(t,\fxx)\leq0.
\]
This proves that $u$ is a viscosity subsolution of \eqref{eq1713}. A similar (or dual) proof shows that $u$ is a supersolution.
\end{proof}

At this point it should be clear that the last important step in our program is to show that the approximate solutions converge uniformly on compact sets. It should also be clear that Definitions 15.9 and 15.10 were fashioned to abstract from previous results about inf-sup operators, conditions that are sufficient to prove the Barles--Souganidis theorem. We will see in the next chapter that these conditions are also sufficient to prove that the approximate solutions converge. This then will close the gap and show that the iterated operators converge to viscosity solutions of their associated equations.





\section{A uniqueness result for viscosity solutions}

Proving uniqueness is technically quite difficult, and we are going to fudge by quoting a uniqueness result without proof. Our statement has been simplified to cover only those admissible functions $F$ that are associated with image operators. References where one can find this and more general results are given in the next section. 

\begin{theorem}[Uniqueness] Assume that $(A,p)\mapsto F(A,p)$ is admissible and that $u_0$ and $v_0$ are two continuous functions defined on $\RR^N$. Assume further that these functions are $C$-periodic with respect to the hypercube $C=[-1,1]^N$. If $u$ and $v$ are continuous $C$-periodic viscosity solutions of 
\begin{equation}\label{eq1719}
\frac{\partial\varphi}{\partial t}=F(D^2u,Du)
\end{equation}
with initial conditions $u_0$ and $v_0$, then
\begin{equation}\label{eq1720}
\sup_{t\in R^+,\fxx\in\RR^N}(u(t,\fxx)-v(t,\fxx))\leq \sup_{\fxx\in\RR^N}(u_0(\fxx)-v_0(\fxx)).
\end{equation}
As a consequence, if $u_0=v_0$, then $u(t,\fxx)=v(t,\fxx)$ for all $\fxx$ and $t$.
\end{theorem}

\section{Comments and references}

The simple definition of viscosity solution given in this chapter was originally proposed by Michael G. Crandall and Pierre-Louis Lions in \cite{?} for first-order PDEs associated with control theory. It was then shown to be applicable to second-order equations, in particular the so-called geometric equations like mean curvature motion. The first complete treatise is \textit{User's guide to viscosity solutions of second order partial differential equations} by Crandall, Ishii, and Lions \cite{Crandall:1992:UGV}. First-order equations are treated extensively in Barles \cite{Barles:1994:SVE}. An elementary account for first-order equations is give in the textbook by Evans \cite{Evans:1998:PDE}. Crandall's later presentation of the theory for both first- and second-order equations, published in \cite{?}, is a masterpiece of simplicity and brevity. This book contains a rather complete overview of the techniques, results, and applications, although it does not include applications to image analysis.

The approximation theory for viscosity solutions presented here is based on the seminal paper by Barles and Souganidis \cite{Barles:1991:CAS}.

Proving uniqueness for viscosity solutions of second-order parabolic or elliptic equations is the technically difficult part of the theory. The key step that leads to the uniqueness results was made by Robert Jensen in his 1988 paper \cite{Jensen:1988:MPV}. See also \cite{Changhe:1998:UVS} and \cite{Zhu:1994:EUR} for resent general uniqueness proofs for the parabolic case. Some alternative (or related) existence and uniqueness theories, namely, the nonlinear semigroup theory and De Giorgi's theory of barriers, are discussed in \cite{Evans:1987:NST} and \cite{Bellettini:1998:CRB}.
