Skip to yearly menu bar Skip to main content


Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models

Valentin Durante · George Katsirelos · Thomas Schiex

Hall E #714

Keywords: [ OPT: Convex ] [ PM: Graphical Models ] [ OPT: Discrete and Combinatorial Optimization ]


In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches.

Chat is not available.