Approximating faces of marginal polytopes

Given a point in a polytope, what is the smallest face of the polytope that contains this point? Even though this problem can be formulated as a linear program, there are cases in applications where the answer cannot be found efficiently. I present methods to solve this problem approximately. The idea is to describe faces by the vertices that lie on this face. This set of vertices can be approximated by a superset or subset using projections or liftings of the polytope.

Motivation for this work comes from discrete graphical models. For such models, the question whether the MLE exists can be reformulated as the question whether the empirical distribution lies on a proper face. Any information about the face of the empirical distribution can help to determine which of the parameters of the graphical model can be estimated reliably.