Initialization and Coordinate Optimization for Multi-way Matching

Da Tang, Tony Jebara
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1385-1393, 2017.

Abstract

We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to a misaligned objective. We propose a coordinate update algorithm that directly optimizes the target objective. By using pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees an optimal solution under reasonable noise assumptions. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-tang17a, title = {{Initialization and Coordinate Optimization for Multi-way Matching}}, author = {Tang, Da and Jebara, Tony}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1385--1393}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/tang17a/tang17a.pdf}, url = {https://proceedings.mlr.press/v54/tang17a.html}, abstract = {We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to a misaligned objective. We propose a coordinate update algorithm that directly optimizes the target objective. By using pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees an optimal solution under reasonable noise assumptions. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.} }
Endnote
%0 Conference Paper %T Initialization and Coordinate Optimization for Multi-way Matching %A Da Tang %A Tony Jebara %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-tang17a %I PMLR %P 1385--1393 %U https://proceedings.mlr.press/v54/tang17a.html %V 54 %X We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to a misaligned objective. We propose a coordinate update algorithm that directly optimizes the target objective. By using pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees an optimal solution under reasonable noise assumptions. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.
APA
Tang, D. & Jebara, T.. (2017). Initialization and Coordinate Optimization for Multi-way Matching. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1385-1393 Available from https://proceedings.mlr.press/v54/tang17a.html.

Related Material