In this work, we prove several relations between three different energy minimizing techniques. We show that methods of Ivan Kovtun, which build auxiliary submodular problems, fulfill this sufficient condition. In the case of two labels, LP relaxation provides optimal partial.assignment, known as persistency.

0

0

0

Abstract

In this work, we prove several relations between three different energy
minimization techniques. A recently proposed methods for determining a provably
optimal partial assignment of variables by Ivan Kovtun (IK), the linear
programming relaxation approach (LP) and the popular expansion move algorithm
by Yuri Boykov. We propose a novel sufficient condition of optimal partial
assignment, which is based on LP relaxation and called LP-autarky. We show that
methods of Kovtun, which build auxiliary submodular problems, fulfill this
sufficient condition. The following link is thus established: LP relaxation
cannot be tightened by IK. For non-submodular problems this is a non-trivial
result. In the case of two labels, LP relaxation provides optimal partial
assignment, known as persistency, which, as we show, dominates IK. Relating IK
with expansion move, we show that the set of fixed points of expansion move
with any "truncation" rule for the initial problem and the problem restricted
by one-vs-all method of IK would coincide -- i.e. expansion move cannot be
improved by this method. In the case of two labels, expansion move with a
particular truncation rule coincide with one-vs-all method.