Moment-SoS methods for optimal transport problems

Olga Mula (Corresponding author), Anthony Nouy

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

5 Downloads (Pure)

Samenvatting

Most common optimal transport (OT) solvers are currently based on an approximation of underlying measures by discrete measures. However, it is sometimes relevant to work only with moments of measures instead of the measure itself, and many common OT problems can be formulated as moment problems (the most relevant examples being Lp-Wasserstein distances, barycenters, and Gromov–Wasserstein discrepancies on Euclidean spaces). We leverage this fact to develop a generalized moment formulation that covers these classes of OT problems. The transport plan is represented through its moments on a given basis, and the marginal constraints are expressed in terms of moment constraints. A practical computation then consists in considering a truncation of the involved moment sequences up to a certain order, and using the polynomial sums-of-squares hierarchy for measures supported on semi-algebraic sets. We prove that the strategy converges to the solution of the OT problem as the order increases. We also show how to approximate linear quantities of interest, and how to estimate the support of the optimal transport map from the computed moments using Christoffel–Darboux kernels. Numerical experiments illustrate the good behavior of the approach.

Originele taal-2Engels
Pagina's (van-tot)1541-1578
Aantal pagina's38
TijdschriftNumerische Mathematik
Volume156
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - aug. 2024

Bibliografische nota

Publisher Copyright:
© The Author(s) 2024.

Vingerafdruk

Duik in de onderzoeksthema's van 'Moment-SoS methods for optimal transport problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit