论文标题
基于矩阵平衡的基于点集匹配问题的内点方法
Matrix balancing based interior point methods for point set matching problems
论文作者
论文摘要
可以通过最佳运输来处理匹配问题的点集。其背后的机制是，最佳运输恢复了与最小卷曲变形相关的点对点对应关系。最佳运输是具有密集约束的线性编程的一种特殊形式。线性编程可以通过内点方法来处理，前提是可以准确计算所涉及的条件的Hessians。在这十年中，已经采用了基质平衡来计算熵正规化方法下的最佳运输。内点方法中的溶液质量取决于两种成分：基质平衡的精度和双向矢量的界限。为了达到高准确的矩阵平衡，我们采用牛顿方法来实现沿着一个中心路径的一系列矩阵的矩阵平衡。在这项工作中，我们将稀疏的支持约束应用于基于矩阵平衡的内部点方法，其中稀疏集合满足总支持的迭代更新以截断运输计划的域。总支持条件是一种至关重要的条件，可以保证矩阵平衡以及双重向量的界限。
Point sets matching problems can be handled by optimal transport. The mechanism behind it is that optimal transport recovers the point-to-point correspondence associated with the least curl deformation. Optimal transport is a special form of linear programming with dense constraints. Linear programming can be handled by interior point methods, provided that the involved ill-conditioned Hessians can be computed accurately. During the decade, matrix balancing has been employed to compute optimal transport under entropy regularization approaches. The solution quality in the interior point method relies on two ingredients: the accuracy of matrix balancing and the boundedness of the dual vector. To achieve high accurate matrix balancing, we employ Newton methods to implement matrix balancing of a sequence of matrices along one central path. In this work, we apply sparse support constraints to matrix-balancing based interior point methods, in which the sparse set fulfilling total support is iteratively updated to truncate the domain of the transport plan. Total support condition is one crucial condition, which guarantees the existence of matrix balancing as well as the boundedness of the dual vector.
