An Efficient Multilinear Optimization Framework for Hypergraph Matching

Abstract

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.

Please cite this work as:

@article{nguyen2017efficient,
  title={An efficient multilinear optimization framework for hypergraph matching},
  author={Nguyen, Quynh and Tudisco, Francesco and Gautier, Antoine and Hein, Matthias},
  journal={IEEE transactions on pattern analysis and machine intelligence},
  volume={39},
  number={6},
  pages={1054--1075},
  year={2017},
  publisher={IEEE}
}

Keywords: Hypergraph Matching nonnegative tensors multilinear form block coordinate ascent hypergraphs