Citation
Y. Chen, L. Guibas, Q. Huang. "Near-Optimal Joint Object Matching via Convex Relaxation". International Conference on Machine Learning (ICML), 2014.

Abstract
Joint matching over a collection of objects aims at aggregating information from a large collection of similar instances (e.g. images, graphs, shapes) to improve maps between pairs of them. Given multiple matches computed between a few object pairs in isolation, the goal is to recover an entire collection of maps that are (1) globally consistent, and (2) close to the provided maps --- and under certain conditions provably the ground-truth maps. Despite recent advances on this problem, the best-known recovery guarantees are limited to a small constant barrier --- none of the existing methods find theoretical support when more than 50% of input correspondences are corrupted. Moreover, prior approaches focus mostly on fully similar objects, while it is practically more demanding to match instances that are only partially similar to each other. In this paper, we develop an algorithm to jointly match multiple objects that exhibit only partial similarities, given a few pairwise matches that are densely corrupted. Specifically, we propose to recover the ground-truth maps via a parameter-free convex program called MatchLift, following a spectral method that pre-estimates the total number of distinct elements to be matched. Encouragingly, MatchLift exhibits near-optimal error-correction ability, i.e. in the asymptotic regime it is guaranteed to work even when a dominant fraction of the input maps behave like random outliers. Furthermore, MatchLift succeeds with minimal input complexity, namely, perfect matching can be achieved as soon as the provided maps form a connected map graph. We evaluate the proposed algorithm on various benchmark data sets including synthetic examples and real-world examples, all of which confirm the practical applicability of MatchLift.

Electronic downloads

• http://arxiv.org/abs/1402.1473

• HTML

  Y. Chen, L. Guibas, Q. Huang. <a
  href="http://robotics.eecs.berkeley.edu/pubs/20.html"
  >Near-Optimal Joint Object Matching via Convex
  Relaxation</a>, International Conference on Machine
  Learning (ICML), 2014.

• Plain text

  Y. Chen, L. Guibas, Q. Huang. "Near-Optimal Joint
  Object Matching via Convex Relaxation". International
  Conference on Machine Learning (ICML), 2014.

• BibTeX

  @inproceedings{ChenGuibasHuang14_NearOptimalJointObjectMatchingViaConvexRelaxation,
      author = {Y. Chen and L. Guibas and Q. Huang},
      title = {Near-Optimal Joint Object Matching via Convex
                Relaxation},
      booktitle = {International Conference on Machine Learning (ICML)},
      year = {2014},
      abstract = {Joint matching over a collection of objects aims
                at aggregating information from a large collection
                of similar instances (e.g. images, graphs, shapes)
                to improve maps between pairs of them. Given
                multiple matches computed between a few object
                pairs in isolation, the goal is to recover an
                entire collection of maps that are (1) globally
                consistent, and (2) close to the provided maps ---
                and under certain conditions provably the
                ground-truth maps. Despite recent advances on this
                problem, the best-known recovery guarantees are
                limited to a small constant barrier --- none of
                the existing methods find theoretical support when
                more than 50% of input correspondences are
                corrupted. Moreover, prior approaches focus mostly
                on fully similar objects, while it is practically
                more demanding to match instances that are only
                partially similar to each other. In this paper, we
                develop an algorithm to jointly match multiple
                objects that exhibit only partial similarities,
                given a few pairwise matches that are densely
                corrupted. Specifically, we propose to recover the
                ground-truth maps via a parameter-free convex
                program called MatchLift, following a spectral
                method that pre-estimates the total number of
                distinct elements to be matched. Encouragingly,
                MatchLift exhibits near-optimal error-correction
                ability, i.e. in the asymptotic regime it is
                guaranteed to work even when a dominant fraction
                of the input maps behave like random outliers.
                Furthermore, MatchLift succeeds with minimal input
                complexity, namely, perfect matching can be
                achieved as soon as the provided maps form a
                connected map graph. We evaluate the proposed
                algorithm on various benchmark data sets including
                synthetic examples and real-world examples, all of
                which confirm the practical applicability of
                MatchLift.},
      URL = {http://robotics.eecs.berkeley.edu/pubs/20.html}
  }
  

Posted by Ehsan Elhamifar on 7 Jun 2014.
Groups: ehumans
For additional information, see the Publications FAQ or contact webmaster at robotics eecs berkeley edu.