abstract—hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as
it allows the use of higher-order geometric information. hypergraph matching can be formulated as a third-order optimization problem
subject to 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.
index terms—hypergraph matching, tensor, multilinear form, block coordinate ascent