Related papers: Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces

Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces

URL: http://arxiv.org/abs/2307.09057v1
Date: Tue, 18 Jul 2023 08:20:56 GMT
Title: Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces
Authors: Martin Ryner, Jan Kronqvist, Johan Karlsson
Abstract summary: This paper presents a framework for computing the Gromov-Wasserstein problem between two sets of points in low dimensional spaces. It can be used to quantify the similarity between two formations or shapes, a common problem in AI and machine learning.
Score: 5.534626267734822
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper presents a framework for computing the Gromov-Wasserstein problem between two sets of points in low dimensional spaces, where the discrepancy is the squared Euclidean norm. The Gromov-Wasserstein problem is a generalization of the optimal transport problem that finds the assignment between two sets preserving pairwise distances as much as possible. This can be used to quantify the similarity between two formations or shapes, a common problem in AI and machine learning. The problem can be formulated as a Quadratic Assignment Problem (QAP), which is in general computationally intractable even for small problems. Our framework addresses this challenge by reformulating the QAP as an optimization problem with a low-dimensional domain, leveraging the fact that the problem can be expressed as a concave quadratic optimization problem with low rank. The method scales well with the number of points, and it can be used to find the global solution for large-scale problems with thousands of points. We compare the computational complexity of our approach with state-of-the-art methods on synthetic problems and apply it to a near-symmetrical problem which is of particular interest in computational biology.

Related papers

Scalable unsupervised alignment of general metric and non-metric structures [21.29255788365408]
Aligning data from different domains is a fundamental problem in machine learning with broad applications across very different areas. We learn a related well-scalable linear assignment problem (LAP) whose solution is also a minimizer of the quadratic assignment problem (QAP) We evaluate our approach on synthetic and real datasets from single-cell multiomics and neural latent spaces.
arXiv Detail & Related papers (2024-06-19T12:54:03Z)
Sparse Partitioning Around Medoids [0.0]
Partitioning Around Medoids (PAM, k-Medoids) is a popular clustering technique to use with arbitrary distance functions or similarities. FastPAM recently introduced a speedup for large k to make it applicable for larger problems, but the method still has a runtime quadratic in N. We discuss a sparse and asymmetric variant of this problem, to be used for example on graph data such as road networks.
arXiv Detail & Related papers (2023-09-05T19:52:24Z)
Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
arXiv Detail & Related papers (2023-01-16T10:30:04Z)
Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
Book presents several efforts to tackle this challenge with important scientific implications. It provides alternative optimization schemes that scale well in terms of computational complexity. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems.
arXiv Detail & Related papers (2022-08-23T18:56:05Z)
QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z)
Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z)
A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance [36.97843660480747]
The Wasserstein distance has become increasingly important in machine learning and deep learning. A recently proposed approach to alleviate the curse of dimensionality is to project the sampled data onto a lower-dimensional subspace, and then compute the Wasserstein distance between the projected data. However, this approach requires to solve a max-min problem over the Stiefel manifold, which is very challenging in practice. We propose a novel block coordinate descent (RBCD) method to solve this problem, which is based on a novel reformulation of the regularized max-min problem over the Stiefel manifold.
arXiv Detail & Related papers (2020-12-09T17:47:56Z)
A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
arXiv Detail & Related papers (2020-07-10T05:20:02Z)
Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
We propose a robust method to align point sets where there is no prior information about the value of the transformation. Our algorithm does not need regularization on transformation, and thus can handle the situation where there is no prior information about the values of the transformations. Experimental results demonstrate the better robustness of the proposed method over state-of-the-art algorithms.
arXiv Detail & Related papers (2020-07-05T15:23:33Z)
Efficient and Robust Shape Correspondence via Sparsity-Enforced Quadratic Assignment [16.03666555216332]
We introduce a novel local pairwise descriptor and then develop a simple, effective iterative method to solve the resulting quadratic assignment. Our pairwise descriptor is based on the stiffness and mass iteration matrix of finite element approximation of the Laplace-Beltrami differential operator. We use various experiments to show the efficiency, quality, and versatility of our method on large data sets, patches, and point clouds.
arXiv Detail & Related papers (2020-03-19T10:56:16Z)
Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations. Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic. We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
arXiv Detail & Related papers (2020-02-05T03:09:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.