Near-Optimal Joint Object Matching via Convex Relaxation

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 $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.

References in corpus (2)

• Robust PCA via Outlier Pursuit
• Breaking the Small Cluster Barrier of Graph Clustering

Cited by in corpus (18)

• A General Multi-Graph Matching Approach via Graduated Consistency-regularized Boosting
• Bispectrum Inversion with Application to Multireference Alignment
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope
• Synchronisation of Partial Multi-Matchings via Non-negative Factorisations
• Partial Functional Correspondence
• Multi-Image Matching via Fast Alternating Minimization
• Information Recovery from Pairwise Measurements
• Multi-Image Semantic Matching by Mining Consistent Features
• Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian
• Low-Rank Modeling and Its Applications in Image Analysis
• Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching
• Learning Transformation Synchronization
• Distributable Consistent Multi-Object Matching
• Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering
• Consistent Multiple Graph Matching with Multi-layer Random Walks Synchronization