Near-optimal joint object matching via convex relaxation. arxiv preprint arXiv:1402.1473

Joint object matching aims at aggregating in-formation 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 com-patibility. 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 corre-spondences are corrupted. Moreover, prior ap-proaches focus mostly on fully similar objects, while it is practically more demanding and re-alistic 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 re-covery via a two-step procedure, that is, a spec-tral technique followed by a parameter-free con-vex program called MatchLift. Under a natu-ral randomized model, MatchLift 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