  Hypergraph matching has recently become a popular approach for solving
correspondence problems in computer vision as it allows to integrate
higher-order geometric information. Hypergraph matching can be formulated as a
third-order optimization problem subject to the assignment constraints which
turns out to be NP-hard. In recent work, we have proposed an algorithm for
hypergraph matching which first lifts the third-order problem to a fourth-order
problem and then solves the fourth-order problem via optimization of the
corresponding multilinear form. This leads to a tensor block coordinate ascent
scheme which has the guarantee of providing monotonic ascent in the original
matching score function and leads to state-of-the-art performance both in terms
of achieved matching score and accuracy. In this paper we show that the lifting
step to a fourth-order problem can be avoided yielding a third-order scheme
with the same guarantees and performance but being two times faster. Moreover,
we introduce a homotopy type method which further improves the performance.

Computer Vision and Pattern Recognition;Data Structures and Algorithms;Optimization and Control