Near-optimal joint object matching via convex relaxation

Yuxin Chen, Leonidas Guibas, Qixing Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

50 Scopus citations


Joint object matching aims at aggregating information from a large collection of similar in-stances (e.g. images, graphs, shapes) to improve the correspondences computed between pairs of objects, typically by exploiting global map compatibility. Despite some practical advances on this problem, from the theoretical point of view, the error-correction ability of existing algorithms are limited by a constant barrier - none of them can provably recover the correct solution when more than a constant fraction of input correspondences are corrupted. Moreover, prior approaches focus mostly on fully similar objects, while it is practically more demanding and realistic to match instances that are only partially similar to each other. In this paper, we propose an algorithm to jointly match multiple objects that exhibit only partial similarities, where the provided pairwise fea-ture correspondences can be densely corrupted. By encoding a consistent partial map collection into a 0-1 semidefinite matrix, we attempt recovery via a two-step procedure, that is, a spectral technique followed by a parameter-free convex program called Match Lift. Under a natural randomized model, Match Lift exhibits near- optimal error-correction ability, i.e. it guarantees the recovery of the ground-truth maps even when a dominant fraction of the inputs are randomly corrupted. We evaluate the proposed algorithm on various benchmark data sets including syn-thetic examples and real-world examples, all of which confirm the practical applicability of the proposed algorithm.

Original languageEnglish (US)
Title of host publication31st International Conference on Machine Learning, ICML 2014
PublisherInternational Machine Learning Society (IMLS)
Number of pages9
ISBN (Electronic)9781634393973
StatePublished - Jan 1 2014
Externally publishedYes
Event31st International Conference on Machine Learning, ICML 2014 - Beijing, China
Duration: Jun 21 2014Jun 26 2014

Publication series

Name31st International Conference on Machine Learning, ICML 2014


Other31st International Conference on Machine Learning, ICML 2014

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software


Dive into the research topics of 'Near-optimal joint object matching via convex relaxation'. Together they form a unique fingerprint.

Cite this