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
$1-\Theta\left(\frac{\log^{2}n}{\sqrt{n}}\right)$ 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.

该论文提出了一种基于参数 - free 凸优化程序 MatchLift 的联合匹配算法，该算法在输入地图中的大部分异常值或噪声下仍可以保证接近优化的匹配结果，实现多个只存在部分相似性的对象之间的全局一致性匹配。