Skip to main content
Browse by:

Until further notice, in-person public events have been canceled. Event listings include how to access online content.
Please check before coming to campus.

Near-Optimal Joint Object Matching via Convex Relaxation

Event Image
Icon calendar
Tuesday, April 01, 2014
Icon time
12:00 pm - 1:00 pm
Icon speaker
Yuxin Chen Electrical Engineering, Stanford University
Icon series
iiD Speaker Series

lunch/talk at noonThis talk delivers some encouraging news by transforming this NP-hard combinatorial problem into tractable convex programs. Our approach is inspired by the success of matrix completion and robust PCA, and builds upon a low-rank matrix representation of the global consistency criterion. 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 high-dimensional regime it is guaranteed to work even when a dominant fraction $1¿¿(1 / \sqrt(n))$ of the input maps behave like random outliers. The algorithm and results are well suited for the scenario when the collection of objects exhibit only partial similarity to each other. Furthermore, MatchLift succeeds with minimal input complexity, namely, perfect matching can be achieved as soon as the provided pairwise maps form a connected map graph. On the practical side, 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.

Contact: Kathy Peterson