Cutset Based Processing and Compression of Markov Random Fields

This thesis presents results related to the compression a Markov random field (MRF) X defined on a graph G = (V, E) by first losslessly compressing a cutset of sites U and then either losslessly compressing or estimating the remaining sites conditioned on the cutset. We present analytical solutions to the MAP estimate of a block conditioned on the commonly occurring boundaries with two or fewer runs of black, for both 4 pt. and 8 pt. grid graphs. Using these results we empirically demonstrate that Max-Product Loopy Belief Propagation converges to the correct results. We present a simple adaptive Arithmetic Encoding (AC) based method for losslessly compressing a square grid cutset of a binary image and, applying the Ising reconstruction results, show that the resulting lossy image coder is competitive compared to other methods. We present rigorous development of Local Conditioning for MRFs, algorithm for exact inference in cyclic graphs. We prove that the entropy of family of MRFs is monotone increasing in the associated exponential parameters and that the exponential parameters for the moment-matching reduced MRF induced by U for a subset of nodes are component-wise greater than the original exponential parameters within U. We also show that the divergence between an MRF induced by exponential parameter theta and another induced by theta' is monotone increasing in theta'. Furthermore, we prove that the divergence between the marginal distribution for bfX and reduced MRF follows a Pythagorean decomposition, providing reduced MRF analogue to well-known result in information geometry. We present efficient algorithms for optimal AC based lossless compression of acyclic and EASY cyclic MRFs, and use these for suboptimal lossless compression for HARD cyclic MRFs, called em Reduced Cutset Coding. Experiments with RCC on homogeneous Ising models both verify nearly optimal performance and provide estimates of upper and lower bounds to entropy.