|M. Pawan Kumar|
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 Va taking a label li is shown next to the ith branch of the trellis on top of Va. The pairwise potential for variables Va and Vb taking labels li and lj respectively is shown next to the connection between the ith and jth branches of Va and Vb respectively.
Similarly, the optimization variable corresponding to a random variable Va taking a label li is shown next to the ith branch of the trellis on top of Va. The pairwise optimization variable for variables Va and Vb taking labels li and lj respectively is shown next to the connection between the ith and jth branches of Va and Vb respectively.
Second Order Cone Programming Relaxation
In constrast to the integer program, the variables xa(i) are relaxed to take any value between (and including) -1 and 1. Furthermore, the non-convex 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, xS consists of random variables xa(i) such that Va belongs to the subgraph S. Similarly, XS consists of random variables xab(i,j) such that the edge between Va and Vb belongs to the subgraph S. The resulting optimization problem is convex, with a linear objective function and second-order cone constraints.