Stochastic Restoration Algorithms

Optimization methods that find the global maximum of the objective function $P ({\bf X} \vert {\bf \tilde x})$ include annealing-based methods [99]. These methods optimize iteratively, starting from an arbitrary initial estimate. Recalling the discussion in Section 2.6.1, where $\tau$ is the temperature parameter of the GRF, consider the parametric family of functions

$$P_{\tau} ({\bf X} \vert {\bf\tilde x}) = \Bigg( \frac { P ({\bf X} ) P ({\bf\tilde x} \vert {\bf X}) } { P ({\bf\tilde x} ) } \Bigg)^{1/\tau}.$$ (88)

• 
  As $\tau \rightarrow \infty$, $P_{\tau} ({\bf X} \vert {\bf\tilde x})$ is a uniform PDF.
  
• 
  For $\tau = 1$, $P_{\tau} ({\bf X} \vert {\bf\tilde x})$ is exactly the same as our objective function $P ({\bf X} \vert {\bf \tilde x})$.
  
• 
  At the other extreme, as $\tau \rightarrow 0$, $P_{\tau} ({\bf X} \vert {\bf\tilde x})$ is concentrated on the peaks of our objective function $P ({\bf X} \vert {\bf \tilde x})$.

The key idea behind annealing-based method is to decrease the temperature parameter $\tau$, starting from a very high value, via a cooling schedule. At sufficiently high temperatures $\tau \gg 1$, the objective-function landscape is smooth with a unique local maximum. Annealing first tries to find this maximum and then, as the temperature $\tau$ reduces, continuously tracks the evolving maximum. Annealing-based methods mimic the physical annealing procedure, based on principles in thermodynamics and material science, where a molten substance is gradually cooled so as to reach the lowest energy state.

The literature presents two kinds of annealing strategies:

• 
  Stochastic strategies such as simulated annealing by Kirkpatrik et al. [89] that typically rely on the sampling procedures including the Metropolis-Hastings algorithm [106,73] and the Gibbs sampler [61]. Direct sampling from the PDFs of all RVs in the random field is intractable. The sampling algorithms can generate samples from any PDF by generating a Markov chain that has the desired PDF as the stationary (steady-state) distribution. Once in the steady state, samples from the Markov chain can be used as samples from the desired PDF. Gibbs sampling entails that all the conditional Markov PDFs associated with the random field are known and can be sampled exactly. Simulated annealing is extremely slow in practice and significantly sensitive to the cooling schedule [99].
  
• 
  Deterministic strategies include graduated nonconvexity, by Blake and Zisserman [20], that is much faster than simulated annealing. The graduated nonconvexity, however, gives no guarantees for convergence to the exact global maximum [99].