[1709.09051] Exact MAP inference in general higher-order graphical models using linear programming

Mathematics > Optimization and Control arXiv:1709.09051 (math) This paper has been withdrawn by Ikhlef Bechar [Submitted on 25 Sep 2017 (v1), last revised 19 Mar 2026 (this version, v2)] Title:Exact MAP inference in general higher-order graphical models using linear programming Authors:Ikhlef Bechar View a PDF of the paper titled Exact MAP inference in general higher-order graphical models using linear programming, by Ikhlef Bechar No PDF available, click to view other formats Abstract:This paper is concerned with the problem of exact MAP inference in general higher-order graphical models by means of a traditional linear programming relaxation approach. In fact, the proof that we have developed in this paper is a rather simple algebraic proof being made straightforward, above all, by the introduction of two novel algebraic tools. Indeed, on the one hand, we introduce the notion of delta-distribution which merely stands for the difference of two arbitrary probability distributions, and which mainly serves to alleviate the sign constraint inherent to a traditional probability distribution. On the other hand, we develop an approximation framework of general discrete functions by means of an orthogonal projection expressing in terms of linear combinations of function margins with respect to a given collection of point subsets, though, we rather exploit the latter approach for the purpose of modeling locally consistent sets of discrete functions from a global perspective. After...