Efficient joint object matching via linear programming
Efficient joint object matching via linear programming
复制标题
通过线性规划进行高效的关节对象匹配
DOI：
10.1007/s10107-023-01932-w
复制
发表时间：
2023
影响因子：
2.7
通讯作者：
Khajavirad, Aida
中科院分区：
文献类型：
--
作者：
De Rosa, Antonio;Khajavirad, Aida
联合目标匹配，也称为多图像匹配，即在集合内的所有对目标之间找到一致的部分映射的问题，是计算机视觉的许多领域中的关键任务。这个问题包括二分图匹配和图划分作为特殊情况，是NP-困难的，一般。我们开发了可扩展线性规划（LP）松弛与理论性能保证联合对象匹配。首先，我们提出了一个新的一致的局部映射的特性，这反过来又使我们能够制定联合对象匹配作为一个整数线性规划（ILP）的问题。为了构造强LP松弛，我们研究了这个ILP的可行域的凸船体的表面结构，我们称之为联合匹配多面体。我们提出了一个指数家庭的小面定义的不等式，可以在强多项式时间分离，从而获得了部分特征的联合匹配多面体，这是既紧又便宜的计算。为了分析所提出的LP松弛的理论性能，我们专注于置换群同步，一个重要的特殊情况下，联合对象匹配。我们表明，根据输入地图的随机腐败模型，一个简单的LP松弛，也就是说，一个LP只包含一个非常小的一部分，建议的小面定义的不平等，恢复地面真理的概率很高，如果腐败水平低于40%。最后，通过对合成数据的初步计算研究，我们表明，建议的LP松弛优于一个流行的SDP松弛的恢复和紧密性。
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.
登录
查看更多内容
影响因子：
2.5
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
DOI：
10.1287/moor.2022.1282
发表时间：
2020
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Alberto Del Pia;Aida Khajavirad;Dmitriy Kunisky
通讯作者：
Dmitriy Kunisky
比率切割多面体和 K 均值聚类
影响因子：
3.1
作者：
De Rosa, Antonio;Khajavirad, Aida
通讯作者：
Khajavirad, Aida
SMAC：使用谱分解同时进行映射和聚类。
DOI：
--
发表时间：
2018
期刊：
Proceedings of machine learning research
影响因子：
--
作者：
Bajaj,Chandrajit;Gao,Tingran;He,Zihang;Huang,Qixing;Liang,Zhenxiao
通讯作者：
Liang,Zhenxiao
DOI：
10.1145/2897518.2897573
发表时间：
2015
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Ankur Moitra;William Perry;Alexander S. Wein
通讯作者：
Alexander S. Wein