This week we’ll be covering Pawan, Kolmogorov, and Torr, “An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs”, JMLR 2009.
A related paper is Kumar, Torr, and Zisserman, “Solving Markov Random Fields using Second Order Cone Programming Relaxations“, CVPR 2006, which may be useful as a quick introduction as well as an example of how to apply these methods to a vision problem (object recognition), but the main focus of the meeting will be on the JMLR paper.
The paper begins by describing the integer programming formulation of MAP estimation, equivalently energy minimization, hence the integer program and all relaxations are minimization problems in the paper. Next, the paper gives three relaxations of the integer program – LP-S, the linear programming relaxation (the main one we dealt with in Wainwright); QP-RL, a quadratic programming relaxation; and SOCP-MS, a second order cone programming relaxation. One of the focuses of the paper is to compare these different relaxations to one another, and describes how to do so in the next section, through the notion of dominance. The paper goes on to prove that LP-S dominates SOCP-MS, and prove that SOCP-MS and QP-RL are equivalent.
The next focus of the paper is to prove that for a class of relaxations (on trees and certain types of cycles) LP-S strictly dominates SOCP-MS (and consequently QP-RL). The paper then gives two additional types of constraints that can be added to the SOCP relaxation, such that the new SOCP relaxation dominates LP-S for some problems and has a feasibility region not a super-set of the LP-S feasibility region.
The majority of the paper is in the proofs, so beyond understanding the basic set-up, I think that’s where we should be spending our time. In particular, if there are any steps that you do not follow, post them in the comments and we can try to work through it during the meeting.
Going from SDP to SOCP relaxation:
One fact that seems to be used without an explicit proof is
First, note that
To go the reverse direction, note that any symmetric positive semidefinite matrix
Recall that in the SDP relaxation, our positive semidefinite constraint was
Finally, note that the final inequality is equivalent to the following SOCP constraint:
At this point, the SOCP relaxation is equivalent to the SDP relaxation. However, the SOCP relaxation is made more tractable (at the cost of removing constraints) by only considering a subset of psd matrices