\documentclass[11pt,twocolumn]{article}
\usepackage{times,amsmath,amsfonts}
\usepackage[dvips]{graphicx,graphics}



\setlength{\textheight}{10in} \setlength{\textwidth}{7.1in}
\setlength{\columnsep}{0.3in} \setlength{\topmargin}{0in}
\setlength{\headheight}{-0.3in} \setlength{\headsep}{0in}
\setlength{\oddsidemargin}{-0.6in}  % Centers text.


% Add the period after section numbers.  Adjust spacing.
%\newcommand{\Section}[1]{\vspace{-5pt}\section{\hskip -1em.~~#1}\vspace{-3pt}}
%\newcommand{\SubSection}[1]{\vspace{-2pt}\subsection{\hskip -1em.~~#1}
%        \vspace{-3pt}}
\newcommand{\bqn}{\begin{eqnarray*}}
\newcommand{\eqn}{\end{eqnarray*}}
\newcommand{\bq}{\begin{eqnarray}}
\newcommand{\eq}{\end{eqnarray}}

\begin{document}

\title{Stat 992: Lecture 16\\
Diffusion Smoothing II.}
\author{Moo K. Chung \tt{mchung@stat.wisc.edu}}
\maketitle \thispagestyle{empty}

%\begin{figure}
%\centering
%\renewcommand{\baselinestretch}{1}
%\includegraphics[scale=0.8]{homework05-1.eps}
%\end{figure}

\begin{enumerate}


\item {\em Discrete maximum principle.} Since the diffusion
smoothing and kernel smoothing are equivalent, The diffused signal
$f(x_i,t_{j+1})$ must be bounded by the minimum and the maximum of
signal. So \bqn f(x_i,t_{j+1}) &=& f(x,t_j) + \delta t
\widehat{\frac{\partial^2 f}{\partial x^2}}(x,t_j)\\
&\leq& \max \big[f(x_{i-1},t_j), f(x_i,t_j),f(x_{i+1},t_j)
\big]\eqn and also we can bound it by below. Hence
$$\delta t \leq \max \Big[ \Big|\frac{f(x_{i-1},t_j) - f(x_i,t_j)}
{\widehat{\frac{\partial^2 f}{\partial
x^2}}}\Big|,\Big|\frac{f(x_{i+1},t_j)-f(x_i,t_j)}{\widehat{\frac{\partial^2
f}{\partial x^2}}}\Big|\Big].$$


\item  {\em Iterated weighted averaging} The idea of smoothing
data by directly solving either ordinary differential equation
(ODE) or partial differential equation (PDE) originates from
signal and image processing. In the previous lecture, the finite
difference is given by \bqn f(x_i,t_{j+1}) = \lambda
f(x_{i-1},t_j) + (1 - 2\lambda)f(x_i,t_j)\\ + \lambda
f(x_{i+1},t_j) \label{eq:ima16-1}\eqn where $\lambda = \delta t
/\delta x^2$. Hence diffusion smoothing can be considered as an
iterative weighted averaging. Obviously  $0 \leq \lambda \leq
1/3$. Depending on the value of $\lambda$, the property of
smoothing changes. When $\lambda=0$, we are not smoothing while
when $\lambda=1/3$, we are assigning equal weights to three
neighboring observations.

\item {\em Random walk.} Suppose there is a particle at $x_i$ at
time $t_j$. Suppose we have a symmetric random walk such that the
probability of jumping either left or right is $r$ and the
probability of staying is $1-r$. Interpret $f(x_i,t_j)$ as the
probability of the particle staying at position $x_i$ at time
$t_j$.

{\bf Problem 26.} Assuming we have grid system $x_i = i\delta x, i
\in \mathbb{Z}$ and particle was at rest at $x_0=0$ at time
$t_0=0$. Suppose the transition probability of random walk is
given by
$$P(x_{i-1}|x_i) = r, P(x_i|x_i) = 1-2r, P(x_{i+1}|x_i) = r.$$
Find the probability of finding particle at $x_m$ at time $t_p$.
What happens when $\delta x \to 0$ ?

\begin{figure}[t]
\centering
\renewcommand{\baselinestretch}{1}
%\includegraphics[scale=0.5]{ima15-3.eps}
%\caption{Corpus callosum boundary. See Problem 25.}
\end{figure}

\item {\em Bivariate diffusion smoothing.}  Solving diffusion
equation in $\mathbb{Z}^2$ depends on estimating 2-dimensional
Laplacian. Using the finite difference scheme twice, we have
\bqn \Delta f(x,t) = f(x+\delta x,y, t) + f(x,y+\delta y, t) +\\
f(x-\delta x,y, t) + f(x,y-\delta y, t) - 4 f(x,y,t).\eqn

This uses 4 closest neighbors of pixel position $(x,y)$ to set up
an iteration. It is also possible to incorporate 4 corners $(x \pm
\delta x, y \pm \delta y)$.
\begin{figure}[t]
\centering
\renewcommand{\baselinestretch}{1}
\includegraphics[scale=0.3]{ima15-2.eps}
\caption{It is shown that the diffusion smoothing (dotted lines)
converges to kernel smoothing as the number of iterations increase
(5, 25 and 50 iterations respectively).}
\end{figure}
\end{enumerate}
{\bf Problem 27.} Estimate 2-dimensional Laplacian using 8 pixel
positions around $(x,y)$ so that the Laplican at $(x,y)$ is
expressed as the weighted average of nine terms. Based on both 4
and 8 neighbor Laplacian, implement diffusion smoothing in {\tt
MATLAB} with $t=10$ and $t=20$ and compare your results. For data,
use {\tt sagittal.data}. Which Laplacian gives faster convergence
and why?

\end{document}
Since the random walk is a Markov chain, we have