
\documentstyle{article}

\begin{document}
\input latex_abbr03.tex
\section*{Regularization of a finite-dimensional problem}

As the most of variational methods, the regularization has a
finite-dimensional analog. It is applicable to the minimization
problem of a convex but not strongly convex function which may
have infinitely many solutions. The idea of regularization is to
slightly perturb the function by small but a strictly convex term;
the perturbed problem has a unique solution to matter how small
the perturbation is. The numerical advantage of the regularization
is the convergence of minimizing sequences.

 Let us illustrate
ideas of regularization by studying a finite dimensional problem.
 Consider a linear system
\begin{equation}
Ax=b \label{lin-prob}
\end{equation}
where $A$ is a square $n \times b$ matrix and $b$ is a known
$n$-vector.

We know from linear algebra that the Fredholm Alternative holds:
\begin{itemize}

    \item If $ \det A \neq 0$, the problem has a unique solution:
     \beq
x= A^{-1} b \quad \mbox{if } \det A \neq 0
    \eeq{2sol}

    \item If
$\det A=0$ and $ A b \neq 0$, the problem has no solutions.

\item If $\det A=0$ and $ A b = 0$, the problem has infinitely
many
  solutions.

  \end{itemize}
In practice, we also deal with an additional difficulty: The
  determinant  $ \det A$ may be a ``very small''
number and one cannot be sure whether its value is a result of
rounding of digits or it has a ``physical
  meaning.'' In any case, the errors of using the formula
  \eq{2sol} can
  be arbitrary large and the norm of the solution is not bounded.

To address this difficulties, it is helpful to
 restate linear problem (\ref{lin-prob}) as an extremal problem:
\beq \min_{x \in R^n}(Ax-b)^2 \eeq{min-prob} This problem does
have at least one solution,
 no matter what the matrix $A$ is.
This solution coincides with the solution of the original problem
\eq{lin-prob} when this problem has a unique solution; in this
case the
 cost of the minimization problem \eq{min-prob} is zero.
 Otherwise, the minimization problem provides
 "the best approximation" of the non-existing solution.


If the problem \eq{lin-prob} has infinitely many solutions,
 so does problem \eq{min-prob}. Corresponding
  minimizing sequences $\{x^s\}$ can be unbounded,
  $\|x^s\| \to \infty$ when $s\to \infty$.

 In this case, we may select a solution with minimal norm.
 We use the {\em regularization}, passing to the perturbed problem
$$\min_{x \in R^n}(Ax-b)^2 + \Ge x^2
$$
The solution of the last problem exists and is unique. Indeed, we
have by differentiation
$$
(A^T A + \Ge I) x- A^T b=0
$$
and
$$
x=(A^TA + \Ge I)^{-1} A^T b
$$
We mention several properties of regularization.
\begin{enumerate}
\item The inverse $(A^TA + \Ge I)^{-1}$ exists since the matrix
$A^TA$ is nonnegative
  defined,
and $\Ge$ is positively defined. The eigenvalues of the matrix
 $(A^TA + \Ge I)^{-1}$ are not smaller than $\Ge^{-1}$
\item Suppose that we are dealing with a well-posed problem
 \eq{lin-prob},
 that is the matrix $A$ is not degenerate. If $\Ge\ll1$, the solution
 approximately is $ x=  A^{-1} b - \Ge (A^2A^T)^{-1}b $
 When $\Ge\to 0$, the solution becomes the solution \eq{2sol}
 of the unperturbed problem, $ x\to A^{-1} b $.
\item If the problem \eq{lin-prob} is ill-posed, the norm of the
 solution of the perturbed problem is still bounded:
$$
\|x\|= \| (A^TA + \Ge I)^{-1} \| \,\|b\|\leq {1 \over \Ge} \|b\|
$$
\end{enumerate}

Instead of the regularizing term $\Ge x^2$, we may use any
positively define quadratic $ \Ge( x^T P x+ p^T x)$ or where
matrix $P$ is positively defined, $P>0$, or $ \Ge( (x-c)^T P
(x-c)$ (the attractor to the target point $c$), or another
strongly convex function of $x$.


\end{document}
