摘要
Point set 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. Matrix balancing has been employed to compute optimal transport under entropy regularization approaches. The solution quality relies on two factors: the accuracy of matrix balancing and the boundedness of the dual vector. High accurate matrix balancing is achieved by the application of Newton methods on a sequence of matrices along a 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. The total support condition is one crucial condition, which guarantees the existence of matrix balancing as well as the boundedness of the dual vector.