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 的联合匹配算法，该算法在输入地图中的大部分异常值或噪声下仍可以保证接近优化的匹配结果，实现多个只存在部分相似性的对象之间的全局一致性匹配。

凸松弛下的近最优联合目标匹配

Near-Optimal Joint Object Matching via Convex Relaxation

This paper re-visits the spectral method for learning latent variable models
defined in terms of observable operators. We give a new perspective on the
method, showing that operators can be recovered by minimizing a loss defined on
a finite subset of the domain. A non-convex optimization similar to the
spectral method is derived. We also propose a regularized convex relaxation of
this optimization. We show that in practice the availabilty of a continuous
regularization parameter (in contrast with the discrete number of states in the
original method) allows a better trade-off between accuracy and model
complexity. We also prove that in general, a randomized strategy for choosing
the local loss will succeed with high probability.

本文重新审视了用于学习拉丁变量模型的谱方法，并给出了新的视角。通过在有限子集上定义目标函数，该方法被推广为一种类谱优化方法，并发现连续正则化参数允许更好地平衡模型的准确性和复杂度，同时证明了随机选择本地损失函数的普遍有效性。

算子模型中局部损失优化：光谱学习的新视角

Local Loss Optimization in Operator Models: A New Insight into Spectral  Learning

The O(d) Synchronization problem consists of estimating a set of unknown
orthogonal transformations O_i from noisy measurements of a subset of the
pairwise ratios O_iO_j^{-1}. We formulate and prove a Cheeger-type inequality
that relates a measure of how well it is possible to solve the O(d)
synchronization problem with the spectra of an operator, the graph Connection
Laplacian. We also show how this inequality provides a worst case performance
guarantee for a spectral method to solve this problem.

本篇论文通过提出 Cheeger 不等式，利用操作符与图连接拉普拉斯的特征值关系来解决 O (d) 同步问题，并为其频谱方法提供最坏情况下的性能保证。