%gmChap01.tex

\graphicspath{{./figures/}}

\chapter{The Heat Equation}

The heat equation is the prototype of all the PDEs used in image analysis. As such, its mathematics forms an essential background that is used throughout the book. We begin the analysis of the heat equation in this chapter by proving the existence and uniqueness of its solutions, which incidentally  reveals the connection between the Gaussian and the heat equation. A simple example of linear smoothing is used to illustrate the relation between linear smoothing and the Laplacian and to pave the way for a more detailed analysis in the next chapter.

\section{Linear smoothing and the Laplacian}

Consider a function $u_0$, which we interpret to be an image, defined on a domain $\Omega$ of $\mathbb R^2$, and assume that $u_0\in C^2(\Omega)$. If we wish to smooth $u_0$, then the simplest way to do so without favoring a particular direction is to replace $u_0(\fxx)$ with the unweighted average of the values of $u_0$ in a disk $D(\fxx, h)$ of radius $h$ centered at $\fxx$. This means that we replace $u_0(\fxx)$ with
\begin{equation}\label{Mh}
M_hu_0(\fxx)=\frac1{\pi h^2}\int_{D(\fxx, h)}u_0(\fxy)\,\rmd\fxy=\frac1{\pi h^2}\int_{D(0, h)}u_0(\fxx+\fxy)\,\rmd\fxy.
\end{equation}

Although the operator $M_h$ is quite simple, it exhibits important characteristics of a general linear isotropic smoothing operator. For example, it is localizable: As $h$ becomes small, $M_h$ becomes more localized, that is, $M_hu_0(\fxx)$ depends only on the values of $u_0(\fxx)$ in a small neighborhood of $\fxx$. Other characteristic properties will be mentioned as we proceed. Smoothing an image by averaging over a small symmetric area is illustrated in Figure \ref{smoothing}.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig01.01.1.eps}
}
\caption[Local averaging algorithm]{\label{smoothing} Local averaging algorithm.  Left to right: original image; result of replacing the grey level at each pixel by  the average of the grey levels over the neighboring pixels. The shape of the neighborhood is shown by the black spot displayed in the upper right-hand corner.}
\end{figure}

Our objective is to show the relation between the action of $M_h$ and the action of the Laplacian, or the heat equation. We begin by expanding $u_0$ around the point $\fxx$ using Taylor's formula:
\begin{equation}\label{taylor}
u_0(\fxx+\fxy)=u_0(\fxx)+Du_0(\fxx)\cdot\fxy+\frac1{2}D^2u_0(\fxx)(\fxy,\fxy)+o(|\fxy|^2).
\end{equation}
Now apply $M_h$ to both sides of this expansion. On the left-hand side we have, by definition
\[
\frac1{\pi h^2}\int_{D(0, h)}u_0(\fxx+\fxy)\,\rmd\fxy=M_hu_0(\fxx).
\]
The first term on the right-hand side is
\[
\frac1{\pi h^2}\int_{D(0, h)}u_0(\fxx)\,\rmd\fxy=u_0(\fxx).
\]
The second (linear) term on the right-hand side vanishes because
\begin{equation}\label{1moment}
\int_{D(0, h)}x\,\rmd\fxy=\int_{D(0, h)}y\,\rmd{\fxy}=0.
\end{equation}
Similarly, the cross term in the third (quadratic) term on the right-hand side vanishes:
\begin{equation}\label{12moment}
\int_{D(0, h)}xy\,\rmd\fxy=0.
\end{equation}
This leaves the problem of computing the other quadratic terms, but since
\begin{equation}\label{11moment}
\int_{D(0, h)}x^2\,\rmd\fxy=\int_{D(0, h)}y^2\,\rmd\fxy,
\end{equation}
we have
\[
\int_{D(0, h)}x^2\,\rmd{\fxy}=\frac1{2}\int_{D(0, h)}(x^2+y^2)\,\rmd{\fxy}=\frac1{2}\int_0^h\int_0^{2\pi r^3}\,\rmd r\,\rmd\theta=\frac{\pi h^4}4.
\]

The last term on the right-hand side of \eqref{taylor} is the error term. As long as the point $\fxx=0$ is fixed, we can say that $\int_{D(0, h)}o(|\fxy|^2)\,\rmd{\fxy}=\pi h^2 o(h^2)=h^4\varepsilon(h)$, where $\varepsilon$ is the generic error function. ``Generic'' means that different appearances of $\varepsilon$ may, and probably do, represent different functions. We will sometimes write $\varepsilon(h)=\varepsilon(\fxx,h)$ to remind the reader of the dependence on $\fxx$.


Putting this all together, we have
\begin{equation}\label{Mhx}
M_hu_0(\fxx)=u_0(\fxx)+\frac{h^2}8\Delta u_0(\fxx)+h^2\varepsilon(\fxx,h).
\end{equation}

Equation \eqref{Mhx} says that averaging the image $u_0$ over a small circular area reproduces $u_0$ (which we expected) plus a small amount of the Laplacian of $u_0$ and an error term. Equation \eqref{Mhx} provides the theoretical basis for deblurring an image by subtracting a small amount of its Laplacian.

Notice that there are no linear derivatives and no mixed derivatives on the right-hand side of equation \eqref{Mhx}; only the Laplacian remains. This happened because of the relations \eqref{1moment}, \eqref{12moment}, and \eqref{11moment}. These three properties of $M_h$ will appear as assumptions in the next chapter when we treat general linear smoothing operators.

Next, assume that we have established the existence and uniqueness of the solution of the heat equation
\begin{equation}\label{heat}
\frac{\partial u}{\partial t}(t,\fxx)=\frac{1}8\Delta u(t,\fxx)
\end{equation}
with the initial condition $u_0(\fxx)=u(0,\fxx)$ and that $u$ has continuous second derivatives. Then, for fixed $t_0>0$ and $\fxx$, we can apply $M_h$ to $u$, and by \eqref{Mhx} we have
\begin{equation}\label{Mutx}
M_hu(t_0,\fxx)=u(t_0,\fxx)+\frac{h^2}8\Delta u(t_0,\fxx)+h^2\varepsilon(t_0,\fxx,h).
\end{equation}
Since $u$ is a solution of \eqref{heat}, we can also write
\begin{equation}\label{dif}
u(t_0+h^2, \fxx)=u(t_0,\fxx)+\frac{h^2}8\Delta u(t_0,\fxx)+h^2\varepsilon(t_0,\fxx,h).
\end{equation}
Subtracting \eqref{dif} from \eqref{Mutx} shows that
\begin{equation}\label{Mhut}
M_hu(t_0,\fxx)=u(t_0+h^2, \fxx)+h^2\varepsilon(t_0,\fxx,h).
\end{equation}

This last equation says that applying $M_h$ to a solution of the heat equation \eqref{heat} advances time by $h^2$, plus an error term.

We would like to iterate $M_h$, but to do so we need to control the error terms $\varepsilon(t_0,\fxx,h)$, and for this we assume that these terms are bounded uniformly for $\fxx\in\Omega$ and for $t_0\leq t\leq t_1$ by $\delta(h)>0$, where $\delta(h)\to0$ as $h\to0$. (This assumption, and all the other details, will be justified in section 2.1.)  This assumption implies that when we apply $M_h$ to any of the $\varepsilon$ error functions, we get another error term bounded by the same bound, that is,
\[
|M_h\varepsilon(t,\fxx,h)|\leq\frac1{\pi h^2}\int|\varepsilon(t,\fxy,h)|\,\rmd\fxy\leq \frac1{\pi h^2}\int\delta(h)\,\rmd\fxy=\delta(h).
\]

Having assumed a uniform bound on the error functions, we are ostensibly  free to apply $M_h$ successively to \eqref{Mhut}. Doing so yields the equations
\begin{equation}\label{Mhun}
M_h^nu(t_0,\fxx)=u(t_0+nh^2,\fxx) + nh^2\varepsilon(h),
\end{equation}
where $n=1,2,3,\ldots.$ The obvious problem with this is that for a fixed $h$ and fixed $t_0$, $t_0+nh^2$ will soon exceed $t_1$, and we no longer necessarily have a bound on the error terms.

It is here that the asymptotic idea enters the discussion. If we let $n\to+\infty$ and at the same time require that $nh^2\to t$, $t\leq t_1$, then
\begin{equation}
M_h^nu(t_0,\fxx)\to u(t_0+t,\fxx).
\end{equation}
If we take $t_0=0$, which has not been justified, then we would have
\begin{equation}
\lim_{n\to+\infty\atop nh^2\to t}M_h^nu_0(\fxx)=u(t,\fxx).
\end{equation}
This says that the asymptotic limits of $M_h^n$ operate on $u_0$ exactly as the heat equation \eqref{heat} does; it thus establishes a relation between smoothing with $M_h$ and smoothing with the Gaussian. This ``result'' also tells us something about the relation between iterating $M_h$ and localizing $M_h$. Section 2.1 is devoted to establishing a rigorous form of this result under general conditions. Our purpose here has been to use a simple example to introduce all of the essential elements (including \eqref{1moment} and \eqref{12moment}, and \eqref{11moment} ) that appear in the general result, without the burden of technical details. We begin these details by proving that the heat equation has a unique solution for a given initial condition $u_0$, and that this solution at time $t$ is equal to the convolution $G_t*u_0$, where $G_t$ is the Gaussian (Figure \ref{gaussian}). The effect on level lines of smoothing with the Gaussian is shown in Figure \ref{heatlevellines}.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig01.02.1.eps}
}
\caption[The Gaussian]{\label{gaussian}The Gaussian in two dimensions.}
\end{figure}

\section{Existence and uniqueness of solutions of the heat equation}

Until now, we have been vague about the domain of definition of an image. On one hand, a real digital image is defined on a finite grid, and its continuous representations are defined on a finite domain of $\mathbb R^2$. On the other hand, it is convenient for technical reasons to have images defined on all of $\mathbb R^2$, but it is not convenient to extend them by making them zero outside their original domains of definition. We start by showing how to resolve this problem. Since it costs little extra, we will work in $\mathbb R^N$.

Assume that the real-valued image $u$ is originally defined on the hypercube $[0,1]^N$. We first extend $u$ to the hypercube $C=[-1,1]^N$ by symmetry across the coordinate hyperplanes: For each point $\fxx=(x_1,x_2,\ldots,x_N)$ in $C$, define $u(\fxx)$ by
\[
u(\fxx)=u(|x_1|,|x_2|,\ldots,|x_N|).
\]
This extension satisfies the following relation: For each $\fxx=(x_1,x_2,\ldots,x_N)$ in $C$,
\begin{equation}\label{sym}
u(x_1,x_2,\ldots,x_N)=u(\varepsilon_1 x_1,\varepsilon_1 x_2,\ldots,\varepsilon_N x_N),
\end{equation}
where $(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_N)$ is any vector in $\{-1,1\}^N$. Next, we extend $u$ periodically to all of $\mathbb R^N$. Since the period must be two in each of the variables $x_i$,
\begin{equation}\label{period}
u(x_1,x_2,\ldots,x_N)=u(x_1+2n_1,x_2+2n_2,\ldots,x_N+2n_N),
\end{equation}
for all $(x_1,x_2,\ldots,x_N)\in\mathbb R^N$ and all $(n_1,n_2,\ldots,n_N)\in\mathbb Z^N$. Figure \ref{extension} illustrates this kind of extension.

The purpose of these successive extensions of $u$ to all of $\mathbb R^N$ is to facilitate the definition of certain operations on $u$, such as convolution with smoothing kernels, and, at the same time, to preserve the continuity of $u$ if $u$ is continuous on $[0,1]^N$. This method of extending a function is widely used in image processing; in particular, it is used in most compression and transmission standards. It is easy to check that the extension of $u$ is continuous on $\RR^N$ if the original $u$ is continuous on $[0,1]^N$.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig01.03.1.eps}
}
\caption[Image extension]{\label{extension}Image extension by symmetry, followed by periodization.}
\end{figure}


\begin{definition}
If a function $u$ defined on $\RR^N$ satisfies the periodicity condition \eqref{period}, then we say that $u$ belongs to $L_C$. We also say that $u$ is $C$-periodic. If, in addition, $u$ is bounded, then we say that it belongs to $L_C^{\infty}$. If $u$ is integrable on $C$, that is, if $\int_C|u(\fxx)|\,\rmd\fxx<\infty$, then we say that $u$ belongs to $L_C^1$. We endow these spaces with the following norms:
\begin{align*}
&\text{The $L_C^{\infty}$ norm is}\, \|u\|_{L^{\infty}(C)}=\sup_{\fxx\in C}|u(\fxx)|.\\
&\text{The $L_C^{1}$ norm is}\, \|u\|_{L^1(C)}=\int_C|u(\fxx)|\,\rmd\fxx.
\end{align*}
If, in addition, $u$ satisfies the symmetry conditions \eqref{sym}, then we say that $u$ is symmetric.
\end{definition}

Convergence in the norm of $L_C^{\infty}$ is called uniform convergence, and convergence in the norm of $L_C^{1}$ is called $L_C^{1}$ convergence. When we assume that a function $u\in L_C^{\infty}$ is $C^m$, or has other smoothness properties, we mean that $u$ has these properties on all of $\RR^N$ and not just on $C$. If $u\in L_C^{\infty}$ is continuous, then it is uniformly continuous. Indeed, since $u$ is periodic, $\sup_{\fxx\in\RR^N}|u(\fxx+{\bm h})-u(\fxx)|=\sup_{\fxx\in C}|u(\fxx+{\bm h})-u(\fxx)|$, and since $C$ is compact, $\sup_{\fxx\in C}|u(\fxx+{\bm h})-u(\fxx)|=\varepsilon(|{\bm h}|)$. In the same way, if $u$ is $C^1$, then $\sup_{\fxx\in\RR^N}|Du|(\fxx)=\sup_{\fxx\in C}|Du|(\fxx)$, and so on. Here is a particularly relevant example: If the function $u_0$ in equation \eqref{taylor} belongs to $L_C^{\infty}$ in addition to being $C^2$, then the error term $o(|\fxy|^2)$, which depends on both $\fxx$ and $\fxy$, satisfies
\[
\sup_{\fxx\in\RR^2}|o(\fxx,\fxy)|\leq |\fxy|^2\varepsilon(|\fxy|)
\]
for some $\varepsilon$ function.

The fact that the continuous functions with compact support are dense in $L^1(\RR^N)$ and in $L^1_C$ can be used to prove that translation is continuous in these two spaces. This is the content of the following proposition.

\begin{proposition}
If $u\in L^1_C$, then
\[
\int_C |u(\fxx-\fxy)-u(\fxx)|\,\rmd\fxx=\varepsilon(|\fxy|).
\]
If $u\in L^1(\RR^N)$, then
\[
\int_{\RR^N} |u(\fxx-\fxy)-u(\fxx)|\,\rmd\fxx=\varepsilon(|\fxy|).
\]
\end{proposition}

\begin{proof} Fix $\varepsilon>0$. There exists a continuous function $v\in L_C^\infty$ such that $\|u-v\|_{L^1(C)}\leq\varepsilon$, Since $v$ is uniformly continuous, we have $\sup_{\fxx\in C}|v(\fxx-\fxy)-v(\fxx)|\leq\varepsilon$ if $|\fxy|$ is sufficiently small. Then we have
\begin{align*}
\int_C |u(\fxx-\fxy)-u(\fxx)|\,\rmd\fxx
\leq&\int_C |u(\fxx-\fxy)-v(\fxx-\fxy)|\,\rmd\fxx\\
&+\int_C |v(\fxx-\fxy)-v(\fxx)|\,\rmd\fxx+\int_C |v(\fxx)-u(\fxx)|\,\rmd\fxx\leq3\varepsilon.
\end{align*}
The proof of the second statement is an easy adaptation of this argument.\hfill\end{proof}

%\vspace{-8pt}

\begin{definition}
We say that a function $g$ defined on $\RR^N$ belongs to the Schwartz class $\mathcal S$ if $g\in C^\infty(\RR^N)$  and if for each pair of multi-indices $\alpha,\beta$ there is a constant $C$ such that
\[
|\fxx|^\beta|\partial^\alpha g(\fxx)|\leq C.
\]
\end{definition}

%\vspace{-8pt}

\begin{proposition}
If $g\in\mathcal S$, then $g\in L^1(\RR^N)$. For each pair of multi-indices $\alpha,\beta$, the function $\fxx^\beta\partial^\alpha g$ also belongs to $\mathcal S$, and $\partial^\alpha g$ is uniformly continuous on $\RR^N$.
\end{proposition}
\begin{proof}
The second statement follows from the Leibnitz rule for differentiating a product. (A complete proof by induction is tedious but not profound.) By the  definition of $\mathcal S$, there is a constant $C$ such that $|\fxx|^{N+2}|g(\fxx)|\leq C$. Thus there is another $C$ such that $|g(\fxx)|\leq {C}/({1+|\fxx|^{N+2}})$; since ${C}/({1+|\fxx|^{N+2}})\in L^1(\RR^N)$, $g\in L^1(\RR^N)$. Finally, note that $|\partial^\alpha g(\fxx)|\to0$ as $|\fxx|\to\infty$. But any continuous function on $\RR^N$ that tends to zero at infinity is uniformly continuous.\hfill\end{proof}

\begin{proposition}[The Gaussian and the heat equation]
For all $t>0$, the function $\fxx\mapsto G_t(\fxx)=(1/{(4\pi t)^{N/2}}){\rm e}^{-|\fxx|^2 /4t}$ belongs to $\mathcal S$ and satisfies the heat equation
\[
\frac{\partial G_t}{\partial t}-\Delta G_t=0.
\]
\end{proposition}
\begin{proof}
It is sufficient to prove the first statement for the function $g(\fxx)={\rm e}^{-|\fxx|^2}$. An induction argument shows that $\partial^\alpha g(\fxx)=P_\alpha (\fxx){\rm e}^{-|\fxx|^2}$, where $P_\alpha (\fxx)$ is a polynomial of degree $|\alpha|$ in the variables $x_1, x_2,\ldots,x_N$. The fact that, for every $k\in\mathbb N$, $x^k{\rm e}^{-x^2}\to0$ as $|x|\to+\infty$ finishes the proof. Differentiation shows that $G_t$ satisfies the heat equation.\hfill\end{proof}

Linear image filtering is mainly done by convolving an image $u$ with a positive integrable kernel $g$. This means that the smoothed image is given by the function $g*u$ defined as
\[
g*u(\fxx)=\int_{\RR^N} g(\fxx-\fxy)u(\fxy)\,\rmd\fxy=\int_{\RR^N} g(\fxy)u(\fxx-\fxy)\,\rmd\fxy.
\]
Note that the convolution, when it makes sense, is translation invariant. This means that $g*u(\fxx-\fxz)=g_{\fxz}*u(\fxx)$, where $g_{\fxz}(\fxx)=g(\fxx-\fxz)$. (Linear filtering with the Gaussian at several scales is illustrated in Figure \ref{blurs}.) The next result establishes properties of the convolution that we need for our treatment of the heat equation.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig01.04.1.eps}
}
\caption[Convolution with Gaussian kernels (heat equation)]{\label{blurs}Convolution with Gaussian kernels (heat equation).  Displayed from top-left to bottom-right are the original image and the results of convolutions with Gaussians of increasing variance. A grey level representation of the convolution kernel is put on the right of each convolved image to give an idea of the size of the involved neighborhood.}
\end{figure}

\begin{proposition}
Assume that $u\in L^1_C$ and that $g\in L^1(\RR^N)$. Then $g*u(\fxx)$ exists for almost every $\fxx\in \RR^N$, the function $g*u$ belongs to $L^1_C$, and it satisfies the inequality
\begin{equation}\label{g*u1}
\|g*u\|_{L^1(C)}\leq\|g\|_{L^1(\RR^N)}\|u\|_{L^1(C)}.
\end{equation}
If $u$ is bounded, then $g*u(\fxx)$ exists for every $\fxx\in\RR^N$ and
\begin{equation}\label{g*u2}
\|g*u\|_{L^\infty(C)}\leq\|g\|_{L^1(\RR^N)}\|u\|_{L^\infty(C)}.
\end{equation}
\end{proposition}
\begin{proof}
We start by proving that $g*u$ is well defined, that it belongs to $L^1_C$, and that \eqref{g*u1} holds. For any $\fxx\in\RR^N$, we can always write
\[
|g*u(\fxx)|\leq\int_{\RR^N}|g(\fxy)||u(\fxx-\fxy)|\,\rmd\fxy
\]
and integrate both sides over $C$. Thus,
\[
\int_C|g*u(\fxx)|\,\rmd\fxx\leq\int_C\int_{\RR^N}|g(\fxy)||u(\fxx-\fxy)|\,\rmd\fxy\,\rmd\fxx.
\]
Since everything in sight is positive, we can interchange the order of integration by Fubini's theorem and have
\[
\int_C|g*u(\fxx)|\,\rmd\fxx\leq\int_{\RR^N}\int_C|g(\fxy)||u(\fxx-\fxy)|\,\rmd\fxx\,\rmd\fxy=\int_{\RR^N}|g(\fxy)|\int_C|u(\fxx-\fxy)|\,\rmd\fxx\,\rmd\fxy.
\]
The last term on the right is equal to $\|g\|_{L^1(\RR^N)}\|u\|_{L^1(C)}$. To see this we use the fact that $u$ us $C$-periodic, which implies that  $\int_C|u(\fxx-\fxy)|\,\rmd\fxx=\int_C|u(\fxx)|\,\rmd\fxx$ for any $\fxy\in\RR^N$. Thus the integral on the left-hand side is finite and $g*u(\fxx)$ exists for almost every $\fxx$. It is left as an exercise to show that $g*u$ is $C$-periodic, and thus complete the proof of the first statement. If $u$ is bounded, then
\[
|g*u(\fxx)|\leq\int_{\RR^N}|g(\fxx-\fxy)||u(\fxy)|\,\rmd\fxy\leq\|u\|_{L^{\infty}_C}\int_{\RR^N}|g(\fxx-\fxy)|\,\rmd\fxy=\|u\|_{L^{\infty}_C}\|g\|_{L^1_{\RR^N}},
\]
and we have $\|g*u\|_{L^{\infty}_C}\leq\|g\|_{L^1_{\RR^N}}\|u\|_{L^{\infty}_C}$.\hfill\end{proof}

%\vspace{-12pt}
\begin{exercise}
Verify that $g*u$ is $C$-periodic. Show that if, in addition to the assumptions of Proposition 1.6, $g$ is even ($g(-\fxx)=g(\fxx)$) and $u$ is symmetric ($u$ satisfies \eqref{sym}), then $g*u$ is also symmetric. \finex
\end{exercise}

Inequality \eqref{g*u2} provides a uniform bound on $g*u$ when $u\in L^{\infty}_C$ and $g\in L^1(\RR^N)$. For what follows, we wish to establish an estimate of $\|g*u\|_{L^{\infty}_C}$ when we assume only that $u\in L^1_C$. We can do this by taking advantage of the $C$-periodicity of $u$ and by an additional assumption about $g$.

Let $C_{\bm n}=\{\fxx\mid \fxx=\fxy+2{\bm n}, \fxy\in C,{\bm n}\in{\mathbb Z^N} \}$. $C_{\bm n}$ is just the hypercube $C$ translated so that it is centered at $2{\bm n}$. Using this notation, we have the inequalities
\begin{align*}
|g*u(\fxx)|\leq&\int_{\RR^N}|u(\fxx-\fxy)||g(\fxy)|\,\rmd\fxy=\sum_{\fxn\in\mathbb Z^N}\int_{C_{\fxn}}|u(\fxx-\fxy)||g(\fxy)|\,\rmd\fxy\\
\leq&\sum_{\fxn\in\mathbb Z^N}\sup_{\fxy\in C_{\fxn}}|g(\fxy)|\int_{C_{\fxn}}|u(\fxx-\fxy)|\,\rmd\fxy=\|u\|_{L^1(C)}\sum_{\fxn\in\mathbb Z^N}\sup_{\fxy\in C_{\fxn}}|g(\fxy)|.
\end{align*}
If the last sum on the right-hand side of these inequalities is finite, we have a uniform estimate for $|g*u(\fxx)|$. We state this as a lemma.

\begin{lemma}\label{lemma1}
Assume that $g\in L^1(\RR^N)$ is such that
\begin{equation}\label{condc}
\sum_{\fxn\in\mathbb Z^N}\sup_{\fxy\in C_{\fxn}}|g(\fxy)|<+\infty.
\end{equation}
Then for any $u\in L^1_C$,
\begin{equation}\label{lemma}
\|g*u\|_{L^{\infty}(C)}\leq\Big(\sum_{\fxn\in\mathbb Z^N}\sup_{\fxy\in C_{\fxn}}|g(\fxy)|\Big)\,\|u\|_{L^1(C)}.
\end{equation}
\end{lemma}

Condition \eqref{condc} is true for the Gaussian and, in fact, for all functions $g$ that decay rapidly at infinity, that is, functions for which, given any multi-index $\alpha$, there exists a constant $C=C(\alpha)$ such that
\begin{equation}\label{decay}
|\fxx|^{\alpha}|g(\fxx)|<C
\end{equation}
for all $\fxx\in\RR^N$.\newpage

\begin{exercise}\leavevmode
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Show that if $g$ decays rapidly at infinity, then for some $C>0$,
\[
\sum_{\fxn\in\mathbb Z^N}\sup_{\fxx\in C_n}|g(\fxx)|\leq C\sum_{\fxn\in\mathbb Z^N}\prod_{i=1}^N\frac{1}{1+|n_i|^2}<+\infty.
\]
\item Show that for each $t_0>0$, there exists a $C(t_0)>0$ such that
\[
\sum_{\fxn\in\mathbb Z^N}\sup_{\fxx\in C_n}|G_t(\fxx)|\leq C(t_0)
\]
for all $t\geq t_0$ and that  $C(t_0)\leq\Big(\frac{1}{2\sqrt{\pi t_0}}+1\Big)^N$. \finex
\end{enumerate}
\end{exercise}

This exercise shows, in particular, that condition \eqref{condc} is true for functions $g\in\mathcal S$. We are now going to focus on kernels that, like the Gaussian, belong to $\mathcal S$.

\begin{proposition}
If $u\in L^1_C$ and $g\in\mathcal S$, then $g*u\in C^{\infty}(\RR^N)\cap L^{\infty}(C)$ and
\begin{equation}\label{1.19}
\partial^{\alpha}(g*u)=(\partial^{\alpha}g)*u
\end{equation}
for every multi-index $\alpha$.
\end{proposition}

\begin{proof}
Since $g\in\mathcal S$, $g\in L^1(\RR^N)$, as is $\partial^{\alpha}g$ for any multi-index $\alpha$ (Proposition 1.4). Thus by Proposition 1.6, $g*u$ belongs to $L^1_C$. To prove \eqref{1.19}, it is sufficient to prove it for $\alpha=(1,0,\ldots,0)$. Indeed, we know that $\partial^{\alpha}g$ is in $\mathcal S$ if $g$ is in $S$, so the general case follows from the case $\alpha=(1,0,\ldots,0)$ by induction. Letting ${\bm e}_1=(1,0,\ldots,0)$ and using Taylor's formula with Lagrange's form for the remainder, we can write

\begin{equation}\label{proof18}
\begin{split}
g*u(\fxx+h{\bm e}_1)-g*u(\fxx)=&\int_{\RR^N}(g(\fxx+h{\bm e}_1-\fxy)-g(\fxx-\fxy))u(\fxy)\,\rmd\fxy\\
=&\int_{\RR^N}(g(\fxy+h{\bm e}_1)-g(\fxy))u(\fxx-\fxy)\,\rmd\fxy\\
=&\,\,h\!\!\int_{\RR^N}\frac{\partial g}{\partial x_1}(\fxy)u(\fxx-\fxy)\,\rmd\fxy\\&+\frac{h^2}{2}\int_{\RR^N}\frac{\partial^2 g}{\partial x_1^2}(\fxy+\theta(\fxy) h{\bm e}_1)u(\fxx-\fxy)\,\rmd\fxy,
\end{split}
\end{equation}
where $0\leq\theta(\fxy)\leq 1$. To complete the proof, we wish to have a bound on the last integral that is independent of $\fxx\in C$. This last integral is of the form $f*u$, where $f$ is defined by $f(\fxy)=({\partial^2 g}/{\partial x_1^2})(\fxy+\theta(\fxy) h{\bm e}_1)$. Since $g\in\mathcal S$, ${\partial g}/{\partial x_1}\in\mathcal S$, and from this it is a simple computation to show that $f$ decays rapidly at infinity.
Having done this, Lemma \ref{lemma1} applies, and we deduce that $g*u$ is differentiable in $x_1$ and that ${\partial( g*u)}/{\partial x_1}=({\partial g}/{\partial x_1})*u$.\hfill\end{proof}
%\vspace{-12pt}
\begin{proposition} \label{dirac}
Assume that $g$ decreases rapidly at infinity, that $g(\fxx)\geq 0$ for all $\fxx\in\RR^N$, and that $\int_{\RR^N}g(\fxx)\,\rmd\fxx = 1$, and define $g_t$ for $t>0$ as $g_t(\fxx)=(1/ {t^N})g(\fxx/ t)$. Then we have the following results:

\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item If $u_0\in L^\infty_C$ is continuous, $g_t*u_0$ converges
to $u_0$ uniformly as $t \to 0$. In addition, we have a maximum principle~:
\begin{equation}
\label{meanvalue}
\inf_{\fxx\in C}u_0(\fxx)\leq g_t*
u_0(\fxx)\leq\sup_{\fxx\in C}u_0(\fxx).
\end{equation}
\item If we only know that $u_0\in L^1_C$, then
\[
\int_C |g_t*u_0(\fxx)-u_0(\fxx)|\,\rmd\fxx= \|g_t*u_0-u_0\|_{L^1(C)}\to 0\;\text{ as }\; t\to 0.
\]
\end{enumerate}
\end{proposition}

\begin{proof}
We begin by proving $(i)$. Note first that $g_t$ is normalized so that
\begin{equation}\label{norm}
\int_{\RR^N}g_t(\fxy)\,\rmd\fxy=1.
\end{equation}
Next, since $g$ decreases rapidly at infinity, a quick computation shows that, for any $\eta>0$,
\begin{equation}\label{concentration}
\int_{|\fxy|\geq\eta}g_t(\fxy)\,\rmd\fxy\to0\;\text{ as }\;t\to0.
\end{equation}
Using \eqref{norm}, we have
\begin{equation}\label{diff}
g_t*u_0(\fxx)-u_0(\fxx)=\int_{\RR^N}g_t(\fxy)(u_0(\fxx-\fxy)-u_0(\fxx))\,\rmd\fxy.
\end{equation}
As already mentioned, since $u_0$ is continuous on $C$ and $C$-periodic, it is uniformly continuous on $\RR^N$. Thus, for any $\varepsilon>0$, there is an $\eta=\eta(\varepsilon)>0$ such that $|u_0(\fxx-\fxy)-u_0(\fxx)|\leq\varepsilon$ when $|\fxy|\leq\eta$. Using this inequality, we have
\begin{align*}
|g_t*u_0(\fxx)-u_0(\fxx)|\leq&\int_{|\fxy|<\eta}g_t(\fxy)|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxy\\&+\int_{|\fxy|\geq\eta}g_t(\fxy)|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxy\\
\leq&\varepsilon\int_{|\fxy|<\eta}g_t(\fxy)\,\rmd\fxy+2\|u\|_{L^{\infty}(C)}\int_{|\fxy|\geq\eta}g_t(\fxy)\,\rmd\fxy.
\end{align*}
Since $\int_{|\fxy|<\eta}g_t(\fxy)\,\rmd\fxy\leq1$ and $\int_{|\fxy|\geq\eta}g_t(\fxy)\,\rmd\fxy\to0$ as $t\to0$, we conclude that $g_t*u$ tends to $u_0$ uniformly in $\fxx$ as $t\to0$. Relation \eqref{meanvalue} is an immediate consequence of the assumption that $g_t(\fxx)\geq0$ and equation \eqref{norm}. This completes the proof of $(i)$.

To prove $(ii)$, we must estimate the $L^1_C$ norm of $g*u_0-u_0$. By using \eqref{diff}, taking absolute values, and integrating over $C$, we see that
\[
\int_C|g_t*u_0(\fxx)-u_0(\fxx)|\,\rmd\fxx\leq\int_C\int_{\RR^N}g_t(\fxy)|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxy\,\rmd\fxx.
\]
Once again everything in sight is positive, so we can interchange the order of integration to see that
\[
\|g_t*u_0-u_0\|_{L^1(C)}\leq\int_{\RR^N}g_t(\fxy)\int_C|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxx\,\rmd\fxy.
\]
As before, we break the integral over $\RR^N$ into two parts:
\begin{equation}\label{break}
\begin{aligned}
\|g_t*u_0-u_0\|_{L^1(C)}\leq&\int_{|\fxy|<\eta}g_t(\fxy)\int_C|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxx\,\rmd\fxy\\&+\int_{|\fxy|\geq\eta}g_t(\fxy)\int_C|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxx\,\rmd\fxy,
\end{aligned}
\end{equation}
which is true for any $\eta>0$. We now invoke Proposition 1.2: Given $\varepsilon>0$, there is an $\eta=\eta(\varepsilon)>0$ such that
\[
\int_C |u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxx\leq\varepsilon\;\text{ for }\;|\fxy|\leq\eta.
\]
Then for this $\eta$, we have the following estimate for the first integral on the right-hand side of \eqref{break}:
\[
\int_{|\fxy|<\eta}g_t(\fxy)\int_C|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxx\,\rmd\fxy\leq\varepsilon.
\]
For the second integral in \eqref{break}, we have
\[
\int_{|\fxy|\geq\eta}g_t(\fxy)\int_C|u_0(\fxx-\fxy)-u_0(\fxx)|\,\rmd\fxx\,\rmd\fxy\leq2\|u\|_{L^1(C)}\int_{|\fxy|\geq\eta}g_t(\fxy)\,\rmd\fxy.
\]
The right-hand side of this inequality tends to zero as $t\to0$. Thus, for sufficiently small $t>0$, $\|g_t*u_0-u_0\|_{L^1(C)}\leq\varepsilon$. Since $\varepsilon$ was arbitrary, this completes the proof of $(ii)$.\hfill\end{proof}

Except for a small detail, all of the tools are in place to state and prove the main theorem of this chapter. It remains to be shown that $({\partial G_t}/{\partial t})*u_0={\partial (G_t*u_0)}/{\partial t}$, where $G_t$ is the Gaussian and $u_0\in L^1_C$. Proposition 1.8 does not apply directly. It applies to the spatial partial derivatives of $G_t$ but not to the derivative with respect to $t$. Perhaps the simplest way to prove the result for $t$ in the context of what we have done, is to observe that a slight modification of the proof of Proposition 1.8 does the job: Replace $g$ with $G_t$ and $\fxx_1$ with $t$. Then the crux of the matter is to notice that, given an interval $0<t_0<t_1$, there is a rapidly decreasing function $f$ such that
$
|({\partial^2 G_t}/{\partial t^2})(t+\theta(t)h, \fxy)|\leq f(\fxy)
$
uniformly for $t\in[t_0,t_1]$, where $f$ depends on $t_0$ and $t_1$ but not on $h$. Then Lemma 1.7 applies, and the last integral in equation \eqref{proof18} is uniformly bounded.


\begin{theorem}[Existence and uniqueness of solutions of the heat equation]\label{existenceuniquenessheat}
Assume that $u_0\in L^1_C$. Then we have the following two results:
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item For all $t>0$ and $\fxx\in\RR^N$, $u(t,\cdot)=G_t*u_0$ satisfies the heat equation with initial value $u_0$ in the sense that
\begin{equation}\label{heatsol}
\frac{\partial u}{\partial t}=\Delta u\quad\text{and}\quad\int_C|u(t,\fxx)-u_0(\fxx)|\,\rmd\fxx\to0\;\text{ as }\;t\to0.
\end{equation}
Furthermore, for each $t>0$, $u(t,\cdot)\in C^{\infty}(\RR^N)\cap L^{\infty}_C$, and for any $t_0>0$ it is uniformly bounded for $t\in[t_0,+\infty)$, specifically,
\begin{equation}\label{unibound}
\sup_{\fxx\in\RR^N, t\geq t_0}|u(t,\fxx)|\leq C(t_0)\|u_0\|_{L^1(C)}.
\end{equation}
\item Conversely, given $u_0\in L^1_C$, $G_t*u_0$ is the unique solution $u$ of \eqref{heatsol} that belongs to $L^{\infty}_C$ for each $t>0$, that is uniformly bounded on $[t_0,+\infty)$ for each $t_0>0$, and that is $C^2$ on $(0,+\infty)\times\RR^N$.
\end{enumerate}\unskip
\end{theorem}

\begin{proof} We first prove (i). For each $t>0$, $G_t\in\mathcal S$, so by Proposition 1.8 and the remarks before the statement of the theorem concerning the interchange of integration and differentiation, we know that we can write
\begin{equation}\label{solvesheat}
\frac{\partial u}{\partial t}-\Delta u=u*\bigg(\frac{\partial G_t}{\partial t}-\Delta G_t\bigg).
\end{equation}
Proposition 1.8 also tells us that $u(t,\cdot)\in C^{\infty}(\RR^N)\cap L^{\infty}_C$ for each $t>0$. The right-hand side of \eqref{solvesheat} is zero by Proposition 1.5, and the fact that $\int_C|u(t,\fxx)-u_0(\fxx)|\,\rmd\fxx\to0\;\text{ as }t\to0$ follows from Proposition 1.9(ii). The inequality \eqref{unibound} will follows directly from Lemma \ref{lemma1} and Exercise 1.2(ii). This completes the proof of (i).

We prove (ii) by assuming that there are two solutions of the heat equation \eqref{heatsol} and reaching a contradiction. If both $v$ and $w$ are solutions of the heat equation with the same initial condition $u_0\in L^1_C$, then $u=v-w$ is in $L^1_C$ and satisfies \eqref{heatsol} with the initial condition $u_0(\fxx)=0$ for all $\fxx\in\RR^N$. In particular,
$
\int_C|u(t,\fxy)|\,\rmd\fxy\to0\;\text{ as }\;t\to0.
$
Also, by the assumptions of (ii), $u$ is uniformly bounded on $[t_0,+\infty)\times\RR^N$ for each $t_0>0$ and is $C^2$ on $(0,+\infty)\times\RR^N$. This last condition ensures that it makes sense to say that $u$ satisfies the heat equation; it is also used to justify the interchange of integration and differentiation. We wish to show that $u(t,\fxx)=0$ for all $t>0$ and all $\fxx\in\RR^N$. Assume that this is not the case. Then there is some point $(t,\fxx)$ where $u(t,\fxx)\not=0$. Assume that $u(t,\fxx)>0$, by changing $u$ to $-u$ if necessary. For reasons that become clear as the argument progresses, we introduce the function $u_h$, $h>0$, defined by
\begin{equation}\label{uh}
u_h(t,\fxx)=\int_{\RR^N}G_h(\fxy)u(t,\fxy-\fxx)\,\rmd\fxy
\end{equation}
for all $t>0$ and $\fxx\in\RR^N$. This new function is in $L^{\infty}_C$, and by Lemma \ref{lemma1},
\begin{equation}\label{utoinfty}
\|u_h\|_{L^\infty L(C)}\leq C(G_h)\|u\|_{L^1(C)}\to0\;\text{ as }\;t\to0.
\end{equation}
Take $h$ sufficiently small so that $u_h(t,\fxx)>0$ for some $(t,\fxx)\in(0,+\infty)\times\RR^N$ and fix $h$. This is possible by Proposition 1.9. The function $u_h$ is also a solution of the heat equation. This is clear as soon as we justify interchanging integration and differentiation to write
\[
\frac{\partial u_h}{\partial t}(t,\fxx)=\int_{\RR^N}G_h(\fxy)\frac{\partial u}{\partial t}(t,\fxy-\fxx)\,\rmd\fxy\;\text{ and }\; \Delta u_h(t,\fxx)=\int_{\RR^N}G_h(\fxy)\Delta u(t,\fxy-\fxx)\,\rmd\fxy.
\]
The justification follow from previous arguments and the fact that the derivatives of $u\in L^{\infty}_C$ are assumed to be continuous on $(0,+\infty)\times\RR^N$.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig01.05.1.eps}}
\caption[Level lines and the heat equation]{\label{heatlevellines}Level lines and the heat equation. Top, left to right: original 410$\times$270 grey level image; level lines of original image for levels at multiples of 12. Bottom, left to right: original image smoothed by the heat equation (convolution with the Gaussian). The standard deviation of the Gaussian is 4, which means that its spatial range is comparable to a disk of radius 4.  The image gets blurred by the convolution, which averages grey level values and removes all sharp edges.  This can be appreciated on the right, where we have displayed all level lines for levels at multiples of 12. Note how some level lines on the boundaries of the image have split into parallel level lines that have drifted away from each other. The image has become smooth, but it is losing its structure.}
\end{figure}


Here, in review, are the important facts about $u_h$: It satisfies the heat equation with the initial condition $u_0(\fxx)=0$; $u_h(t,\fxx)\to0$ uniformly in $\fxx$ as $t\to0$; $u_h$ is bounded on $[0,+\infty)\times\RR^N$; and $u_h(t,\fxx)>0$ for some $(t,\fxx)\in(0,+\infty)\times\RR^N$.

We now consider yet another function $u^{\varepsilon}$ defined by $u^{\varepsilon}(t,\fxx)={\rm e}^{-\varepsilon t}u_h(t,\fxx)$. This function is continuous on $[0,+\infty)\times\RR^N$, it is $C$-periodic in $\fxx$, and it tends to zero uniformly in $\fxx$ as $t\to0$ and as $t\to+\infty$. These conditions imply that $u^{\varepsilon}$ attains its supremum at some point $(t_0,\fxx_0)\in(0,+\infty)\times C$, and this means that $\Delta u^{\varepsilon}(t_0,\fxx_0)={\rm e}^{-\varepsilon t}\Delta u_h(t_0,\fxx_0)\leq0$ and $({\partial u^{\varepsilon}}/{\partial t})(t_0,\fxx_0)=0$. Here is the payoff: Using the fact that $u_h$ is a solution of the heat equation, we have the following relations:
\begin{align*}
0=\frac{\partial u^{\varepsilon}}{\partial t}(t_0,\fxx_0)&=-\varepsilon u^{\varepsilon}(t_0,\fxx_0)+{\rm e}^{-\varepsilon t}\frac{\partial u_h}{\partial t}(t_0,\fxx_0)\\
&=-\varepsilon u^{\varepsilon}(t_0,\fxx_0)+{\rm e}^{-\varepsilon t}\Delta u_h(t_0,\fxx_0)\leq -\varepsilon u^{\varepsilon}(t_0,\fxx_0)<0.
\end{align*}
This contradiction completes the uniqueness proof.\hfill\end{proof}

If the original data had been $v_0\in L^1([0,1]^N)$ and $v_0$ had been extended to a symmetric $C$-periodic function $u_0$, then we know from Exercise 1.1 that $u(t,\cdot)=G_t*u_0$ is symmetric for all $t>0$. Theorem 1.10 implies that $\|u(t,\cdot)-v_0\|_{L^1([0,1]^N)}\to0$ as $t\to0$. Note also that $\|u_0\|_{L^1(C)}$ can be replaced with $2^N\|v_0\|_{L^1([0,1]^N)}$ in \eqref{unibound}.




\section{Comments and references}

\paragraph*{The heat equation.}One should not conclude from Theorem \ref{existenceuniquenessheat} that the solutions of the heat equation are always unique. The assumption in (ii) that the solution was bounded is crucial. In fact, without this assumption, there are solutions $u$ that grow so fast that $gu$ is not in $L^1(\RR^N)$ for $g\in\mathcal S$ (see, for example, \cite[page 217]{taylor}). Also, observe that the role of $G_h$ in the proof was only that of a convenient positive kernel satisfying the conditions of Proposition 1.9. It had nothing to do with the fact that $G_t$ is the fundamental solution of the heat equation. The existence and uniqueness proof of Theorem \ref{existenceuniquenessheat} is classic and can found in most textbooks on partial differential equations, such as Evans \cite{Evans:1998:PDE}, Taylor \cite{taylor}, or Brezis \cite{Brezis:1983:AFT}.

\paragraph*{Convolution.}The heat equation---its solutions and their uniqueness---has been the main topic in this chapter, but to approach this, we have studied several aspects of the convolution, such as the continuity properties \eqref{g*u1} and \eqref{g*u2}. We also noted that the convolution commutes with translation. Conversely, under quite certain conditions, a linear operator $T$ defined on a function space that is continuous and translation invariant is a convolution, that is, $Tu=g*u$ for some kernel $g$. Also, if $u\geq0$ ($u(\fxx)\geq0$ for all $\fxx$) implies that $Tu\geq0$, then $g\geq0$. This is one of the fundamental theorems of both mechanics and signal processing, and it has many generalizations that depend on the domain, range, and continuity properties of $T$. For instance, if $T$ is translation invariant and continuous from $L^2(\RR^N)$ into $L^{\infty}(\RR^N)\cap C(\RR^N)$, then the convolution kernel $g$ is in $L^2(\RR^N)$. This is a direct consequence of the fact that every bounded linear functional on $L^2(\RR^N)$ is of the form $f\mapsto \int_{\RR^N}f(\fxx)g(\fxx)\,\rmd\fxx$ for some $g\in L^2(\RR^N)$. This latter result was discovered independently by F. Riesz and M. Fr\'{e}chet in 1907 (see \cite[page 61]{RN}). Since we want smoothing to be translation invariant and continuous in some topology, this means that linear smoothing operators---which are called filters in the context of signal and image processing---are described by their convolution kernels. The Gaussian serves as a model for linear filters because it is the only one whose shape is stable under iteration. Other positive filters change their shape when iterated. Furthermore, we will show in the next chapter that a large class of linear filters tend asymptotically to the Gaussian.

\ifodd\count0
    \clearpage
    \leavevmode
    \thispagestyle{empty}
    \clearpage
\else\relax
\fi
