View in EDS HTML Full Text PDF Full Text

On the Existence of Monge Maps for the Gromov–Wasserstein Problem.

Saved in:
Bibliographic Details
Title: On the Existence of Monge Maps for the Gromov–Wasserstein Problem.
Authors: Dumont, Théo1 (AUTHOR) theo.dumont@univ-eiffel.fr, Lacombe, Théo1 (AUTHOR) theo.lacombe@univ-eiffel.fr, Vialard, François-Xavier1 (AUTHOR) francois-xavier.vialard@univ-eiffel.fr
Source: Foundations of Computational Mathematics. Apr2025, Vol. 25 Issue 2, p463-510. 48p.
Subjects: Absolute continuity, Cost functions, Probability measures, Transportation planning
Abstract: The Gromov–Wasserstein problem is a non-convex optimization problem over the polytope of transportation plans between two probability measures supported on two spaces, each equipped with a cost function evaluating similarities between points. Akin to the standard optimal transportation problem, it is natural to ask for conditions guaranteeing some structure on the optimizers, for instance, if these are induced by a (Monge) map. We study this question in Euclidean spaces when the cost functions are either given by (i) inner products or (ii) squared distances, two standard choices in the literature. We establish the existence of an optimal map in case (i) and of an optimal 2-map (the union of the graphs of two maps) in case (ii), both under an absolute continuity condition on the source measure. Additionally, in case (ii) and in dimension one, we numerically design situations where optimizers of the Gromov–Wasserstein problem are 2-maps but are not maps. This suggests that our result cannot be improved in general for this cost. Still in dimension one, we additionally establish the optimality of monotone maps under some conditions on the measures, thereby giving insight into why such maps often appear to be optimal in numerical experiments. [ABSTRACT FROM AUTHOR]
Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 184167500
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Existence of Monge Maps for the Gromov–Wasserstein Problem.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Dumont%2C+Théo%22">Dumont, Théo</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> theo.dumont@univ-eiffel.fr</i><br /><searchLink fieldCode="AR" term="%22Lacombe%2C+Théo%22">Lacombe, Théo</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> theo.lacombe@univ-eiffel.fr</i><br /><searchLink fieldCode="AR" term="%22Vialard%2C+François-Xavier%22">Vialard, François-Xavier</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> francois-xavier.vialard@univ-eiffel.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Foundations+of+Computational+Mathematics%22">Foundations of Computational Mathematics</searchLink>. Apr2025, Vol. 25 Issue 2, p463-510. 48p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Absolute+continuity%22">Absolute continuity</searchLink><br /><searchLink fieldCode="DE" term="%22Cost+functions%22">Cost functions</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+measures%22">Probability measures</searchLink><br /><searchLink fieldCode="DE" term="%22Transportation+planning%22">Transportation planning</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The Gromov–Wasserstein problem is a non-convex optimization problem over the polytope of transportation plans between two probability measures supported on two spaces, each equipped with a cost function evaluating similarities between points. Akin to the standard optimal transportation problem, it is natural to ask for conditions guaranteeing some structure on the optimizers, for instance, if these are induced by a (Monge) map. We study this question in Euclidean spaces when the cost functions are either given by (i) inner products or (ii) squared distances, two standard choices in the literature. We establish the existence of an optimal map in case (i) and of an optimal 2-map (the union of the graphs of two maps) in case (ii), both under an absolute continuity condition on the source measure. Additionally, in case (ii) and in dimension one, we numerically design situations where optimizers of the Gromov–Wasserstein problem are 2-maps but are not maps. This suggests that our result cannot be improved in general for this cost. Still in dimension one, we additionally establish the optimality of monotone maps under some conditions on the measures, thereby giving insight into why such maps often appear to be optimal in numerical experiments. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=184167500
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10208-024-09643-0
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 48
        StartPage: 463
    Subjects:
      – SubjectFull: Absolute continuity
        Type: general
      – SubjectFull: Cost functions
        Type: general
      – SubjectFull: Probability measures
        Type: general
      – SubjectFull: Transportation planning
        Type: general
    Titles:
      – TitleFull: On the Existence of Monge Maps for the Gromov–Wasserstein Problem.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Dumont, Théo
      – PersonEntity:
          Name:
            NameFull: Lacombe, Théo
      – PersonEntity:
          Name:
            NameFull: Vialard, François-Xavier
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 16153375
          Numbering:
            – Type: volume
              Value: 25
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Foundations of Computational Mathematics
              Type: main
ResultId 1