An efficient multilinear optimization framework for hypergraph matching

Quynh Nguyen, Francesco Tudisco, Gautier Antoine, Matthias Hein

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)
27 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)1054-1075
Number of pages22
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number6
Early online date31 May 2016
Publication statusPublished - 1 Jun 2016


  • hypergraph matching
  • tensor
  • multilinear form
  • block coordinate ascent


Dive into the research topics of 'An efficient multilinear optimization framework for hypergraph matching'. Together they form a unique fingerprint.

Cite this