M. Pawan Kumar 
HOME

IMPROVED MOVES FOR TRUNCATED CONVEX MODELS M. Pawan Kumar and P. Torr
Overview We develop a new stMINCUT based move making method for MAP estimation of discrete MRFs with arbitrary unary potentials and truncated convex pairwise potentials. We prove that our method provides the best known multiplicative bounds (same as the bounds obtained by solving the standard linear programming relaxation followed by randomized rounding) for these problems in polynomial time. We demonstrate the efficacy of our approach using synthetic and real data experiments.
Our Method
Given an MRF characterized by arbitrary unary potentials and truncated convex pairwise potentials,
we develop an accurate stMINCUT based algorithm to obtain its MAP labeling. The main steps of
our algorithm are summarized below. Initialization • Choose an initial labeling for the MRF. For example, assign the label l_{i} to all random variables. Iteration
• Set i_{m} = 1.
 Define an interval of labels I_{m} = [i_{m}+1,j_{m}] where j_{m} = min{i_{m} + L, h1} and d(L) ≥ M.
Here L is referred to as the length of the interval. Termination • Stop if the energy does not decrease for any interval I_{m}, otherwise repeat Iteration.
Note that, since we minimize a pairwise submodular function, each iteration of our algorithm only requires a single stMINCUT for which several efficient algorithms exist. Theoretical Properties
Our algorithm provides the best known worstcase multiplicative bounds for truncated convex models in polynomial time.
Specifically, Results The graphs below show the results of various energy minimization algorithms, averaged over 100 randomly generated instances. Our approach, and the related range swap algorithm of [2], provide more accurate results than loopy belief propagation and other move making algorithms such as α expansion and αβ swap, and are more efficient than TRWS, which attempts to solve the dual of the linear programming relaxation. We also note that, unlike our approach, the range swap algorithm does not provide any multiplicative bounds. See our publications for more results.
Related Work
Also see our paper on obtaining the best worstcase multiplicative bounds for the metric labeling
problem using an stMINCUT based move making algorithm. References
[1] C. Chekuri, S. Khanna, J. Naor and L. Zosin. Approximation algorithms for the metric labeling problem
via a new linear programming formulation. In SODA, 2001.
