#### Maximum Entropy Relaxation

*Jason K. Johnson, Venkat Chandrasekaran*

*Maximum entropy relaxation* (MER) is a convex optimization
approach for thinning MRF models that was originally formulated as a
method to select cavity models in the context of Jason's RCM
algorithm. The usual approach to model thinning is to select a
tractable approximation to a given MRF, based on a sub-graph of the
original MRF, which involves both selection of a sub-graph and
parameter optimization in the class of MRFs defined on that sub-graph
to minimize relative entropy. Because sub-graph selection is
combinatorial, the MER approach was formulated as a tractable
alternative that simultaneously selects both the sub-graph and
corresponding parameters through solution of a convex optimization
problem. Formally, we seek to maximize entropy subject to a relaxed set
of marginal constraints, which require that the marginals of the
relaxed distribution are close to the corresponding marginals in
the orginal distribution in the sense of relative entropy.

In joint work with Venkat, this idea was formalized in an exponential
family representation for Gaussian and Boltzmann models. An approach
was developed to solve these problems using a modified primal-dual
interior point method, which exploits sparsity of Fisher information
in chordal MRFs, and an incremental method for identifying the
active set of constraints in the MER problem.