Yuxin Chen sent me the following yesterday:
Dear Igor,
I have been following your blog daily, and have learned a lot from your blog entries. I believe that this definitely has made a significant impact to the community.We have recently published one paper in ICML, which uses ideas motivated by robust PCA / matrix completion to solve joint graph matching, a task particularly important in computer vision and graphics. We have released sample code for the key component of the algorithm for reproducible purpose, which might be of some interest to your blog readers. They can be found on my webpage.Let me know if these could be of interest, thanks much!
Best
Yuxin
Thanks Yuxin ! Here is the paper:
Near-Optimal Joint Object Matching via Convex Relaxation by Yuxin Chen, Leonidas J. Guibas, Qi-Xing Huang
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−Θ(log2nn√) 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.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment