A Novel Approach for Markov Random Field With Intractable Normalizing Constant on Large Lattices

ABSTRACT

The pseudo likelihood method of Besag (1974) has remained a popular method for estimating Markov random field on a very large lattice, despite various documented deficiencies. This is partly because it remains the only computationally tractable method for large lattices. We introduce a novel method to estimate Markov random fields defined on a regular lattice. The method takes advantage of conditional independence structures and recursively decomposes a large lattice into smaller sublattices. An approximation is made at each decomposition. Doing so completely avoids the need to compute the troublesome normalizing constant. The computational complexity is O(N), where N is the number of pixels in the lattice, making it computationally attractive for very large lattices. We show through simulations, that the proposed method performs well, even when compared with methods using exact likelihoods. Supplementary material for this article is available online.

KEYWORDS:

• Conditional independence
• Decomposition
• Markov chain Monte Carlo
• Normalizing constant
• Potts model

Supplementary Materials

Matlab code: The supplemental files for this article include Matlab files. These files can be used to replicate the simulation studies and the read data analysis. Please see readme.txt for detailed instructions.

Acknowledgments

YF is supported by a UNSW goldstar research grant. WZ and YF are grateful for the support of the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers. The authors are grateful for the AE and two anonymous referees, whose comments have helped improve the manuscript. The authors also thank Liyuan Li for providing the satellite image data in the second application.