\documentclass[11pt]{amsart}
\setlength{\topmargin}    {-0.5cm}
\setlength{\textheight}   {23cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
\setlength{\textwidth}    {14.5cm}
\renewcommand{\baselinestretch}{1.2}

\usepackage{amssymb,amsmath,amsfonts,epsfig}
\usepackage{epsf}


%------------------------------------------
\begin{document}

\title{Besov semi-norm Regularization and Computational Algorithm for Image Restoration}
\author{Dai-Gyoung Kim}
%kim@banach.hanyang.ac.kr\\
%Department of Mathematics, Hanyang University\\
%Ansan, Kyunggi 425-791, Korea

\address{Department of Mathematics\\
  Hanyang University\\ Ansan\\ 425-791 Korea
}
\email{kim@banach.hanyang.ac.kr}

\maketitle

%\thispagestyle{empty}

%\vskip.3truein
%\centerline{{\bf ABSTRACT}}
%\vskip.2truein

 In this  paper, we propose an adaptive iteration algorithm for signal/image 
restoration.   For  digital signals, this algorithm    minimizes   a piecewise
$l_q$, $0<q\leq 1$, functional  defined   on wavelet 
domain  with   single  equality   constraint. This minimization 
algorithm is from a Besov semi-norm penalty method and corresponds  to  a 
restoration process.  In practice,  restoration 
and  enhancement   processes have   many 
applications in information technology areas
such as digital communications, CCD/CCTV 
imaging, medical  imaging,  and astronomy 
telescope imaging. 
  
Observed or  acquired  signal/image data 
through a communication system 
are   usually   blurred   and  noisy.   The 
restoration and enhancement of blurred  and 
noisy data are ill-posed inverse problems in 
theoretical and computational point of 
views. Mathematically, an acquired  signal 
is modeled via an integral equation:
\begin{equation}
g=Af+w
\label{eq:1-1}
\end{equation}
where $g$ is the acquired  signal which  is 
degraded by a blurring  operator $A$ and a random noise $w$ from original signal
$f$. In  signal/image 
processing applications, $A$ is usually modeled as  a convolution 
operator and $w$ a Gaussian  white random process (cf. \cite{BG}, \cite{ROFu}); for  instance,
$A$ is represented by   the    Gaussian   kernel   function
$k(x,y) = \frac 1{\sqrt{\pi} \sigma} e^{- \frac{(x-y)}{\sigma^2}}$
as
$$
Af(x)=\int k(x,y) f(y) \,dy.
$$
In  this case, $A$ is a compact operator 
or  generally   a Fredholm   first   kind 
integral operator, so  that the  problems 
of the form \eqref{eq:1-1}  are ill-posed  problems 
in the sense of Hadamard.

 Many image restoration methods have 
been recently proposed  (cf. \cite{LB}).  One 
basic  approach   is to   formulate   the 
restoration  problem  as  a  constrained 
least squares problem. This approach is 
a regularization method. A general form 
of regularization of  the problem  (1) is 
the  constrained  minimization   problem 
with respect to $f$:
\begin{equation}
\aligned
\min\quad &J(f)\\
\text{subject to}\quad &\|Af - g\|_2 = \sigma
\endaligned
\label{eq:1-2}
\end{equation}
where $J$ is a certain objective functional, $\sigma$ is the standard deviation 
of the noise $w$, and $\|\cdot\|_2$ denotes the $L_2$-norm.  There are 
several possible   choices of  the  objective 
functional $J$, for instance,  the $L_2$-norm of the   gradient  $\nabla f$
or some higher derivatives   of  $f$. 
For signal/image processing  applications,   Rudin  et   al. 
\cite{ROFa}, \cite{ROFu}   have recently   suggested 
the use of  the bounded variation  ({\it BV}) 
semi-norm  $J(f)=|f|_{BV}$.
With    this choice,  a solution of \eqref{eq:1-2} provides an image 
with the least total variation among  all the 
images with the  standard deviation  $\sigma$, so 
that   the   bounded   variation    based restoration   algorithm   has   
a   great success in   the recovery  of  corrupted 
piecewise  constant   images  such   as 
blocky images.

  Rudin et al.'s  {\it BV} based method  has, 
however,   a   disadvantage    for   the 
piecewise  smooth  signals/images.    In 
this paper,   a numerical  simulation  is 
presented to demonstrate the {\it BV}  based 
method fails. In  addition, we   propose    a   Besov   semi-norm 
regularization method   for the  problem 
\eqref{eq:1-2} to overcome  the disadvantage  while 
keeping non-oscillatory (minimal ringing) 
and   non-invasive   (edge    preserving) 
reconstruction.  

The   minimization   problem \eqref{eq:1-2}   with 
$J(f)=|f|_{BV}$ can be solved by finding the 
steady  state  of   the nonlinear   diffusion 
process   driven  by   the  Euler-Lagrange 
equation (cf. \cite{ROFa}, \cite{ROFu}). Because of  the 
complicate  nonlinear  structure   of Besov 
semi-norm(cf. \cite{T}), the minimization 
problem \eqref{eq:1-2}  with Besov semi-norm:
\begin{equation}
\aligned
\min\quad &|f|_{B_q^\alpha} \\
\text{subject to}\quad &\|Af - g\|_2 = \sigma
\endaligned
\label{eq:1-3}
\end{equation}
can not be  handled by  the Euler-Lagrange formulation. 
However, in computation,  the minimization 
problem \eqref{eq:1-3}  can be considered as an $l_q$-norm minimization problem. 
In \cite{K}, \cite{DJP}, the Besov semi-norm is characterized  in terms 
of  a weighted $l_q$-norm of     wavelet 
coefficients. Using   the wavelet  coefficient 
characterization   of  the   signal  $f$, we
reformulate the minimization problem \eqref{eq:1-3} as 
a weighted $l_q$-norm problem  with  single 
equality constraint.

For $0<q\leq1$, the $l_q$-norm problem is a nonlinear piecewise differentiable 
minimization problem with singularity at the 
origin. So, it is difficult to reach  an optimal 
solution to the minimization problem. There 
has recently been  reports \cite{Li}, \cite{CoLi}  for a 
globally  convergent  method   for $l_q$-norm problems. 
In   \cite{LiSn},  the  authors   have 
proposed  a reliable and  efficient 
computational algorithm based  on the  {\it BV} 
semi-norm reguarization   method. This 
algorithm    basically    minimizes     a 
piecewise linear $l_1$ objective functional (a 
measure of bounded variation).  For solving 
this  constrained $l_1$ minimization  problem, 
an   affine  scaling   Newton   method  is 
employed in \cite{Li}, \cite{LiSn}. We adapt the affine 
scaling Newton method for  solving our $l_q$-norm minimization   
problem.  

\bibliographystyle{amsplain}
\begin{thebibliography}{10}

\bibitem{BG}
A. Bakushinsky and A. Goncharsky,
\newblock{\em Ill-Posed    Problems:   Theory   and 
    Applications},
\newblock{MIA   Series,   Kluwer Academic Publ., Norwell, MA 1994.}

\bibitem{CoLi}
T. Coleman and Y. Li,
\newblock{ A Globally and  Quadratically   Convergent Affine 
    Scaling Method for Linear  $l_q$ problem},
\newblock{\em  Mathematical   Programming}, 
{\bf 56}, 189--222 (1992).

\bibitem{DJP}
R.   DeVore,  B. Jawerth, and   V.   Popov, 
\newblock{Compression of Wavelet Decomposition},
\newblock{\em Amer. J. Math.}, 
{\bf 114}, 737--785 (1992).

\bibitem{K}
D.-G. Kim,
\newblock{Littlewood-Paley Type Estimates for Besov spaces on a Cube 
    by  Wavelet Coefficients},
\newblock{\em J.  of Kor. Math. Soc.}, 
{\bf 36}(6), 1075--1090 (1999).

\bibitem{LB}
R.   Lagendijk and   J.   Biemond,
\newblock{\em Iterative Identification  and Restoration 
    of Images}, 
\newblock{ Kluwer Academic  Publ.,  Norwell, MA 1991.}  

\bibitem{Li}
Y. Li,
\newblock{A Globally Convergent Method for $l_q$ Problems},
\newblock{\em  Mathematical Programming}, 
{\bf 3}, 609--629 (1993).

\bibitem{LiSn}
Y. Li and F. Santosa,
\newblock{Computational  Algorithm  for Minimizing Total  Variation in  Image 
    Restoration},
\newblock{\em  IEEE   Trans.  on  Image Processing}, 
(to appear).


\bibitem{ROFa}
L.  Rudin, S.  Osher,  and C.  Fatemi,
\newblock{Nonlinear Total Variation   Based Noise Removal Algorithm},
\newblock{\em Physica D.}, 
{\bf 60}, 259--268 (1992).

\bibitem{ROFu}
L.  Rudin, S.  Osher,  and C.  Fu,
\newblock{Total Variation   Based Restoration  of 
    Noisy  Blurred  Images},
\newblock{\em SIAM J. Numer. Anal.}, (to appear).

\bibitem{T}
H.   Triebel,
\newblock{\em Theory   of Function Spaces  II},
\newblock{Birkhauser Verlag,   Basel, 1992.}

\end{thebibliography}
\end{document}
