On the convergence of Iterated Conditional Modes (ICM) for MAP inference ICM is very fast but I could not find any references that contain a detailed analysis on its convergence (e.g. rate of convergence).
Any suggestions please?
Thanks a lot for your help!
 A: The speed and accuracy of convergence does depend on the source signal to noise ratio.  I would relate convergence to stability and think about "time to converge" as just "time to propagate".
Have you looked at the Viterbi algorithm?  In the case of a 2-d image, an MRF prior is potentially a very strong constraint on individual pixels - so iid per-pixel noise is not such a hard problem.
Conditional mode is a Bayesian concept and is often non-convex such as Ising, convergence to a local maximum is unlikely a global maximum, the Maximum A-posteriori Probability MAP is what links neighbours.  Updates are only stable if they are performed sequentially.  Updating both neighbours allows oscillations.
The weight function reflects the assumed noise-level, given a well behaved noise distribution (convex log-probabilities) the local-maxima.
In practice I gather a smoothing function or less granular model is used to prime the estimate - this is equivalent to simulated annealing.  It deliberately slows down convergence to have a better chance of ending up at good local maximimum .. i.e. close to the global maximum.
I apologise if my comments are naive, I'm no expert and just flicked through these papers.
http://www.dtic.mil/dtic/tr/fulltext/u2/a196141.pdf
http://www3.stat.sinica.edu.tw/statistica/oldpdf/A3n19.pdf
