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!


1 Answer 1


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.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.