M. Pawan Kumar 
HOME

Notation
The above example illustrates our notation. The random variables are shown as unfilled circles. The labels are shown as trellises over the random variables. Each branch of the trellis represents one label. The unary potential of a random variable V_{a} taking a label l_{i} is shown next to the i^{th} branch of the trellis on top of V_{a}. The pairwise potential for variables V_{a} and V_{b} taking labels l_{i} and l_{j} respectively is shown next to the connection between the i^{th} and j^{th} branches of V_{a} and V_{b} respectively. Similarly, the optimization variable corresponding to a random variable V_{a} taking a label l_{i} is shown next to the i^{th} branch of the trellis on top of V_{a}. The pairwise optimization variable for variables V_{a} and V_{b} taking labels l_{i} and l_{j} respectively is shown next to the connection between the i^{th} and j^{th} branches of V_{a} and V_{b} respectively. Second Order Cone Programming Relaxation
In constrast to the integer program, the variables x_{a}(i) are relaxed to take any value between (and including) 1 and 1. Furthermore, the nonconvex quadratic equality constraint is relaxed to a set of second order cone constraints (last constraint in the above problem). The operation (●) represents the Fronebius inner product. Each second order cone is specified using a subset of variables that correspond to a subgraph S of the original MRF. Specifically, x_{S} consists of random variables x_{a}(i) such that V_{a} belongs to the subgraph _{S}. Similarly, X_{S} consists of random variables x_{ab}(i,j) such that the edge between V_{a} and V_{b} belongs to the subgraph _{S}. The resulting optimization problem is convex, with a linear objective function and secondorder cone constraints.
