EUVIMEDEUVIMED entdecken
Crossref

Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem

Hoang Anh Tran, Binh Tuan Nguyen, Yong Sheng Soh

SIAM Journal on Optimization · 30.06.2026 · 36 (2) · 729-759

DOI: 10.1137/25m1736876 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 27.04.2026. Verfasst von Hoang Anh Tran und 2 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Gromov–Wasserstein (GW) problem is a variant of the classical optimal transport problem that allows one to compute meaningful transportation plans between incomparable spaces. At an intuitive level, it seeks plans that minimize the discrepancy between metric evaluations of pairs of points. The GW problem is typically cast as an instance of a nonconvex quadratic program that is, unfortunately, intractable to solve. In this paper, we describe tractable semidefinite relaxations of the GW problem based on the sum-of-squares (SOS) hierarchy. We describe how the Putinar-type and the Schmüdgen-type moment hierarchies can be simplified using marginal constraints, and we prove convergence rates for these hierarchies towards computing global optimal solutions to the GW problem. The proposed SOS hierarchies naturally induce a distance measure analogous to the distortion metrics, and we show that these are genuine distances in that they satisfy the triangle inequality. In particular, the proposed SOS hierarchies provide computationally tractable proxies of the GW distance and the associated distortion distances (over metric measure spaces) that are otherwise intractable to compute.

Zitieren

APA

Tran, H. A., Nguyen, B. T., & Soh, Y. S. (2026). Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem. SIAM Journal on Optimization, 36(2), 729-759. https://doi.org/10.1137/25m1736876

Vancouver

Tran HA, Nguyen BT, Soh YS. Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem. SIAM Journal on Optimization. 2026;36(2):729-759. doi:10.1137/25m1736876

BibTeX
@article{Tran2026,
  author = {Tran, Hoang Anh and Nguyen, Binh Tuan and Soh, Yong Sheng},
  title = {Sum-of-Squares Hierarchy for the Gromov–Wasserstein Problem},
  journal = {SIAM Journal on Optimization},
  year = {2026},
  volume = {36},
  number = {2},
  pages = {729--759},
  doi = {10.1137/25m1736876}
}
Kostenlos starten →