Matrix Balancing Based Interior Point Methods for Point Set Matching Problems

DOI10.1137/22M1479476MaRDI QIDQ6168327zbMATH OpenOpenAlexFDO

Authors Pengwen Chen

Publication date 8 August 2023

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.09763

zbMATH Keywords

interior point methodsmatrix balancingnegative entropyoptimal transportpoint set matching problems

Mathematics Subject Classification ID

Optimal transportation (49Q22) Computing methodologies for image processing (68U10) Linear programming (90C05) Interior-point methods (90C51)

Abstract: 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.

Recommendations

• A perfect match condition for point-set matching problems using the optimal mass transport approach
• Scaling algorithms for unbalanced optimal transport problems
• A multi-objective interpretation of optimal transport
• A fast approach to optimal transport: the back-and-forth method
• Interval-constrained matrix balancing

Cites work

• A distance metric for multidimensional histograms
• A fast algorithm for matrix balancing
• A fast globally linearly convergent algorithm for the computation of Wasserstein barycenters
• A novel kernel correlation model with the correspondence estimation
• A perfect match condition for point-set matching problems using the optimal mass transport approach
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• A Statistical Approach to the Matching of Local Features
• Assignment Problems
• Computational optimal transport. With applications to data sciences
• Computing the Kantorovich distance for images
• Concerning nonnegative matrices and doubly stochastic matrices
• Diagonal Matrix Scaling and Linear Programming
• Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
• Globally optimal joint image segmentation and shape matching based on Wasserstein modes
• scientific article; zbMATH DE number 6378089 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3307153 (Why is no real title available?)
• scientific article; zbMATH DE number 3311499 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Interior point methods 25 years later
• Iterative Bregman projections for regularized transportation problems
• Linear and nonlinear programming
• Modified Cholesky algorithms: A catalog with new approaches
• On the application of the Monge-Kantorovich problem to image registration
• On the complexity of general matrix scaling and entropy minimization via the RAS algorithm
• On the Implementation of a Primal-Dual Interior Point Method
• Optimal Transport
• Scaling algorithms for unbalanced optimal transport problems
• Scaling of matrices to achieve specified row and column sums
• Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
• The earth mover's distance as a metric for image retrieval
• The Sinkhorn–Knopp Algorithm: Convergence and Applications

Cited in

(3)

• A perfect match condition for point-set matching problems using the optimal mass transport approach
• Estimating matching affinity matrices under low-rank constraints
• Randomized methods for computing optimal transport without regularization and their convergence analysis

This page was built for publication: Matrix Balancing Based Interior Point Methods for Point Set Matching Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168327)