A reduced-order model for parametrized Optimal Transport problems

Titel: Een gereduceerd-orde model voor geparametriseerde Optimal Transport-problemen

Auteurs: Elise Bonnet-Weill, Virginie Ehrlacher, Luca Nenna
Datum: 13 april 2026

---

1. Probleemstelling

Het numeriek oplossen van complexe fysische, economische of biologische systemen vereist vaak het herhaaldelijk oplossen van parametrische problemen. In het geval van Optimal Transport (OT) — het vinden van de meest efficiënte manier om een kansmaat naar een andere te verplaatsen — wordt dit computationeel onhaalbaar wanneer state-of-the-art discretisatiemethoden worden gebruikt, vooral bij hoge dimensies.

De specifieke uitdagingen in deze context zijn:

• Parametrische afhankelijkheid: De bron- en doeldistributies (marges) variëren als functie van een parameter $\alpha$. Het doel is om de Kantorovich-potentialen (de oplossingen van het duale OT-probleem) snel te berekenen voor nieuwe parameterwaarden.
• Computationele kosten: Traditionele methoden zoals Lineair Programmeren (LP) of de Sinkhorn-algoritme (met entropische regularisatie) moeten voor elke nieuwe parameterwaarde een nieuw, groot optimalisatieprobleem oplossen. Dit maakt parameterstudies, sensitiviteitsanalyses en real-time toepassingen (zoals kleuroverdracht in beeldverwerking) onuitvoerbaar.
• Wiskundige complexiteit: Kantorovich-potentialen zijn slechts gedefinieerd tot een additieve constante, wat de oplossing multi-waardig maakt en normalisatie vereist voor een goed gesteld reductieprobleem.

2. Methodologie

De auteurs stellen een nieuwe Reduced Basis (RB) strategie voor om een gereduceerd-orde model (ROM) te bouwen dat de familie van Kantorovich-potentialen benadert. De kern van de methode ligt in het beperken van de zoekruimte van de oplossingen tot laag-dimensionale deelruimten.

A. Constructie van het Gereduceerde Model

Het model wordt gebouwd via een offline-online decompositie:

1. Offline Fase (Training):

   • Er wordt een trainingsset van parameters geselecteerd (vaak de uiterste punten van het parameter domein).
   • Voor deze parameters worden de "high-fidelity" (HF) OT-problemen opgelost om snapshots (transportplannen $\pi^*$ en potentialen $\phi^*, \psi^*$) te genereren.
   • Primaire reductie: De transportplannen worden benaderd binnen een niet-negatieve kegel $W^+$, opgespannen door de snapshots van de transportplannen.
   • Duale reductie: De Kantorovich-potentialen worden benaderd binnen lineaire deelruimten $U$ en $V$, opgespannen door de snapshots van de potentialen.
   • De auteurs introduceren een specifieke methode (Gram-Schmidt) om de deelruimten $U$ en $V$ zo te kiezen dat de rangvoorwaarden worden voldaan, waardoor de optimale kosten van het half-gereduceerde en volledig gereduceerde model gelijk blijven.

2. Online Fase (Snelheid):

   • Voor een nieuwe parameter $\alpha$ wordt het OT-probleem opgelost binnen de gereduceerde ruimte.
   • Het resultaat is een Lineair Programmerings (LP) probleem met een zeer klein aantal vrijheidsgraden (variabelen) en constraints, onafhankelijk van de oorspronkelijke grootte van het discretisatierooster ($N_x \times N_y$).

B. A Posteriori Foutenschatting

Om de betrouwbaarheid van de ROM te garanderen, stellen de auteurs twee methoden voor om de fout tussen de HF-oplossing en de ROM-oplossing te schatten zonder het HF-probleem opnieuw op te hoeven lossen:

1. Foutenschatting via c-transformaties:
   • Gebruikmakend van de dualiteit en de eigenschappen van c-transformaties (een concept uit de OT-theorie), wordt een bovengrens voor de fout afgeleid.
   • Omdat deze schatting niet-lineair is in de parameter, wordt de Empirical Interpolation Method (EIM) gebruikt om de berekening efficiënt uit te voeren in de online fase.
2. Foutenschatting via continuïteit:
   • Gebruikmakend van de bewezen continuïteit van de optimale kosten ten opzichte van de parameter $\alpha$, wordt de fout geschat op basis van de afstand tot de dichtstbijzijnde trainingsparameter.

C. Existentie en Stabiliteit

De auteurs bewijzen dat het gereduceerde model oplossingen heeft onder specifieke voorwaarden:

• De trainingsset moet de uiterste punten van het parameter domein bevatten om de niet-leegheid van de toelaatbare set te garanderen.
• De deelruimten moeten de eenheidsvector bevatten (of voldoen aan rangvoorwaarden) om de compaciteit van de toelaatbare set te waarborgen.

3. Belangrijkste Bijdragen

1. Nieuwe RB-strategie voor OT: De eerste toepassing van een Reduced Basis methode die specifiek is ontworpen voor het direct oplossen van parametrische Kantorovich-potentialen (in plaats van OT te gebruiken als hulpmiddel voor PDE's).
2. Goed gestelde formulering: Een wiskundig onderbouwde formulering van het duale OT-probleem die geschikt is voor RB-benadering, inclusief normalisatie van de potentialen.
3. Rigoureuze foutenschatting: Afleiding van computabele en strikte a posteriori foutenbovengrenzen, wat essentieel is voor betrouwbare online evaluatie.
4. Efficiënte implementatie: Een methode om het gereduceerde model te bouwen zonder de enorme matrix van transportplannen expliciet te hoeven opslaan, en een techniek om in hoge dimensies toch een transportkaart te reconstrueren.

4. Numerieke Resultaten

De methode werd getest op twee scenario's:

1. 1D Voorbeeld:

   • Een geparametriseerd OT-probleem met Gaussische verdelingen.
   • Resultaat: De ROM bereikte een aanzienlijke tijdsbesparing (orde van grootte) vergeleken met de standaard LP-oplosser (scipy.optimize.linprog) en de Sinkhorn-algoritme. De nauwkeurigheid nam toe met het aantal snapshots, maar bleef zelfs bij kleine basisgroottes acceptabel.
   • De foutenschattingen bleken nuttig, hoewel ze soms conservatief waren; een correctiefactor verbeterde de nauwkeurigheid van de schatting aanzienlijk.

2. Kleuroverdracht (Color Transfer) in Beeldverwerking:

   • Toepassing op 3D OT (kleurhistogrammen) voor het overdragen van kleurenpaletten tussen afbeeldingen.
   • Schaal: $N_x = N_y = 64$ (ongeveer $2.6 \times 10^5$ variabelen).
   • Resultaat: Met slechts 3 snapshots (training) bereikte de ROM een snelheidswinst van factor 333 vergeleken met de high-fidelity Sinkhorn-methode.
   • De visuele resultaten waren zeer vergelijkbaar met de referentie-oplossing, hoewel er subtiele verschillen waren in de levendigheid van bepaalde tinten (bijv. rood).

5. Betekenis en Conclusie

Dit werk markeert een belangrijke stap in het combineren van Model Order Reduction (MOR) en Optimal Transport.

• Efficiëntie: Het maakt real-time toepassingen van parametrische OT mogelijk, wat eerder onmogelijk was door de hoge computationele kosten.
• Toepassingsgebied: De methode is direct toepasbaar op gebieden zoals uncertainty quantification, vormoptimalisatie, en beeldverwerking (kleuroverdracht).
• Innovatie: In tegenstelling tot eerdere werken die OT gebruikten om transport-dominante PDE's te reguleren, behandelt dit werk het OT-probleem zelf als het parametrische doelwit.

De auteurs tonen aan dat het mogelijk is om de complexiteit van OT-problemen drastisch te reduceren zonder in te leveren op de kwaliteit van de oplossing, mits gebruik wordt gemaakt van een zorgvuldig opgebouwde basis van snapshots en rigoureuze foutcontroles.