8.1

Classical Minimization with Continuous Labels

Let be a continuous label set. Consider the prototypical problem of (piecewise) continuous restoration in which the energy takes the following form

where indicates the presence or absence of the data and is the potential function. Because a minimum is necessarily a stationary point, the gradient must be a zero vector at the point. Therefore, the following system of equations must be satisfied by :

where is assumed ( cf. (3.24)). The system is nonlinear if is a nonlinear function. Higher order derivatives have to be examined in order to determine whether such a stationary point is a local minimum, maximum or a saddle point. We assume that it is a local minimum.

Solving the system of equations (8.6) is a classical problem [Dahlquist and Bjorck 1974]. When h is a linear function, the system is linear and f can be solved for by using matrix operations. For a nonlinear system, a numerical iterative method is generally utilized. In a simple gradient based algorithm, for example, a stationary point satisfying (8.6) is computed by iteratively updating f using the following rule

where is a small constant.

The fixed-point iteration   method provides another method for solving the problem. Rearrange (8.6) into the following form

which is composed of m fixed-point equations ().   The following is called fixed-point iteration

Let be the Jacobian matrix of and be a region in . Suppose (1) is a continuous mapping, , and (2) is a contraction mapping, that is, for all where is a norm and L is a constant. Then the fixed-point iteration   (8.8) converges to a unique fixed-point for every . The way to construct is not unique; some lead to fast convergence and some diverge. The rate of convergence depends linearly on L.

To solve (8.6) using fixed-point iteration,   we may construct a mapping as the following

where C is a constant. It is not difficult to verify that is equivalent to (8.6). It can be shown that (8.10) is a contraction mapping when and (). In this case, the fixed-point iteration   (8.9) converges to a unique fixed-point for which where .