  Joint object matching, also known as multi-image matching, namely, the
problem of finding consistent partial maps among all pairs of objects within a
collection, is a crucial task in many areas of computer vision. This problem
subsumes bipartite graph matching and graph partitioning as special cases and
is NP-hard, in general. We develop scalable linear programming (LP) relaxations
with theoretical performance guarantees for joint object matching. We start by
proposing a new characterization of consistent partial maps; this in turn
enables us to formulate joint object matching as an integer linear programming
(ILP) problem. To construct strong LP relaxations, we study the facial
structure of the convex hull of the feasible region of this ILP, which we refer
to as the joint matching polytope. We present an exponential family of
facet-defining inequalities that can be separated in strongly polynomial time,
hence obtaining a partial characterization of the joint matching polytope that
is both tight and cheap to compute. To analyze the theoretical performance of
the proposed LP relaxations, we focus on permutation group synchronization, an
important special case of joint object matching. We show that under the random
corruption model for the input maps, a simple LP relaxation, that is, an LP
containing only a very small fraction of the proposed facet-defining
inequalities, recovers the ground truth with high probability if the corruption
level is below $40\%$. Finally, via a preliminary computational study on
synthetic data, we show that the proposed LP relaxations outperform a popular
SDP relaxation both in terms of recovery and tightness.
