A reduced-order model for parametrized Optimal Transport problems

1. Problématique et Contexte

Le transport optimal (OT) est une théorie mathématique fondamentale utilisée dans de nombreux domaines (apprentissage automatique, traitement d'images, mécanique des fluides). La résolution numérique de problèmes de transport optimal, notamment sous sa forme discrète (problème de transport linéaire), devient rapidement coûteuse en temps de calcul lorsque la dimension du problème augmente (nombre de points source et cible).

L'article s'intéresse spécifiquement aux problèmes de transport optimal paramétrés. Dans ce contexte, les mesures de probabilité source et cible varient en fonction d'un paramètre $\alpha$ (par exemple, des mélanges convexes de distributions de référence). Résoudre un problème OT complet pour chaque nouvelle valeur de $\alpha$ (nécessaire pour l'analyse de sensibilité, l'optimisation de forme ou l'inférence en temps réel) est prohibitif avec les méthodes classiques (comme l'algorithme de Sinkhorn ou les solveurs de programmation linéaire).

L'objectif est donc de construire un modèle d'ordre réduit (MOR) capable d'approximer efficacement la famille de solutions (potentiels de Kantorovich et plans de transport) pour tout $\alpha$, avec un coût de calcul indépendant de la haute fidélité du maillage initial.

2. Méthodologie Proposée

Les auteurs proposent une approche basée sur la méthode de base réduite (Reduced Basis - RB), adaptée spécifiquement à la structure des problèmes de transport optimal.

A. Formulation Haute Fidélité

Le problème est formulé sous forme de programmation linéaire (PL) :

• Primal : Minimisation du coût de transport sous contraintes de marges.
• Dual : Maximisation de la somme des potentiels de Kantorovich ($\phi, \psi$) sous contraintes de dualité.
  La dépendance en $\alpha$ est linéaire dans les marges $\mu(\alpha)$ et $\nu(\alpha)$, mais la solution elle-même est non linéaire par rapport à $\alpha$.

B. Construction du Modèle Réduit

La méthode repose sur une décomposition Offline-Online :

1. Phase Offline (Apprentissage) :

   • On résout le problème haute fidélité pour un ensemble d'entraînement de paramètres $\mathcal{A}_{train}$.
   • Espace Primal Réduit : On construit un cône convexe $W_+$ de faible dimension engendré par les plans de transport optimaux $\pi^*(\alpha)$ calculés sur l'ensemble d'entraînement. La solution approchée est une combinaison linéaire positive de ces "snapshots".
   • Espaces Duels Réduits : On construit des sous-espaces vectoriels $U$ et $V$ pour les potentiels $\phi$ et $\psi$. Les auteurs proposent une méthode spécifique utilisant l'algorithme de Gram-Schmidt appliqué aux marges de référence pour garantir que les espaces réduits capturent correctement la structure des contraintes. Une condition de rang est établie pour assurer l'équivalence entre le problème semi-réduit et le problème totalement réduit.

2. Phase Online (Résolution) :

   • Pour un nouveau paramètre $\alpha$, on résout un problème d'optimisation de très petite taille (nombre de degrés de liberté réduit de $N_x N_y$ à $R$, où $R \ll N_x N_y$).
   • Le problème réduit reste une programmation linéaire, mais avec un nombre de variables et de contraintes drastiquement réduit.

C. Estimation d'Erreur A Posteriori

Un défi majeur en MOR est de certifier la précision de la solution réduite sans résoudre le problème haute fidélité. L'article propose deux estimateurs d'erreur :

1. Estimateur par Transformées c (c-transforms) :

   • Utilise les solutions duales réduites $(\hat{\phi}, \hat{\psi})$ pour construire des couples admissibles pour le problème dual haute fidélité via les transformées $c$ et $\bar{c}$.
   • Cela fournit une borne supérieure de l'erreur $|I(\alpha) - I_R(\alpha)|$.
   • Optimisation : Le calcul exact de ces transformées est coûteux ($O(N_x N_y)$). Les auteurs utilisent une variante de la Méthode d'Interpolation Empirique (EIM) pour approximer ces termes non linéaires de manière efficace, permettant une évaluation rapide en phase online.

2. Estimateur par Continuité :

   • Exploite la propriété de continuité Lipschitzienne de la valeur optimale par rapport au paramètre $\alpha$ (démontrée dans l'article).
   • L'erreur est bornée par la distance entre $\alpha$ et le point le plus proche dans l'ensemble d'entraînement, pondérée par la norme du coût.

D. Reconstruction de la Carte de Transport

Puisque la solution réduite est une combinaison de plans de transport (et non une carte directe), les auteurs proposent une méthode pour reconstruire une carte de transport approximative $T^*$ à partir de la solution réduite, en pondérant les cartes associées aux snapshots, sans avoir besoin de stocker la matrice complète des plans de transport.

3. Contributions Clés

1. Formulation Well-Posed : Une formulation rigoureuse du problème dual paramétré adaptée à l'approximation par base réduite, incluant des conditions suffisantes pour garantir l'existence et l'unicité (via la compacité et la non-viduité de l'ensemble admissible).
2. Estimateurs d'Erreur Certifiés : Développement d'estimateurs d'erreur a posteriori rigoureux, adaptés au cadre du transport optimal, avec une accélération via la méthode EIM pour gérer les non-linéarités.
3. Décomposition Offline-Online Efficace : La méthode permet de déplacer l'essentiel du coût computationnel vers la phase offline. En phase online, la complexité est indépendante de la dimension haute fidélité ($N_x, N_y$).
4. Application à la Transfert de Couleur : Démonstration pratique sur un problème de transfert de palette de couleurs (OT 3D), montrant une accélération significative par rapport aux méthodes standards.

4. Résultats Numériques

Les auteurs valident leur méthode sur deux types d'expériences :

• Exemple 1D (Toy Problem) :

  • Comparaison avec un solveur de programmation linéaire (scipy.optimize.linprog) et l'algorithme de Sinkhorn.
  • Précision : L'erreur diminue avec le nombre de snapshots (taille de la base réduite).
  • Temps : Le modèle réduit offre un gain de temps significatif par rapport aux méthodes haute fidélité, tout en surpassant ou égalant la précision de Sinkhorn pour des paramètres d'entropie optimaux.
  • Les estimateurs d'erreur sont testés : l'estimateur par continuité nécessite une correction multiplicative pour être précis, tandis que l'estimateur par transformées c (avec EIM) est plus robuste mais nécessite un choix judicieux de la taille de la base EIM.

• Application 3D (Transfert de Couleur) :

  • Problème de transport entre des histogrammes de couleurs d'images (dimensions $N_x^3 \approx 2.6 \times 10^5$).
  • Performance : Avec seulement 3 snapshots (images de référence), le modèle réduit atteint un accélération de facteur 333 par rapport à la méthode Sinkhorn haute fidélité (0.02s contre 6.93s par transfert).
  • Qualité Visuelle : Les images transférées sont visuellement très proches de celles obtenues par la méthode haute fidélité, bien que des différences subtiles (ex: vivacité des tons rouges) puissent apparaître.

5. Signification et Impact

Ce travail comble un vide important dans la littérature sur la réduction de modèle pour le transport optimal. Contrairement aux approches précédentes qui utilisent l'OT comme outil pour réduire des équations aux dérivées partielles (EDP) dominées par l'advection, cette méthode traite le problème de transport lui-même comme le problème paramétrique à réduire.

Les implications sont majeures pour :

• L'optimisation de forme et l'incertitude : Permettant des analyses de sensibilité rapides sur des distributions de probabilité.
• Le traitement d'images en temps réel : Comme démontré par le transfert de couleur, la méthode rend possible l'application de l'OT sur des images haute résolution dans des contraintes de temps strictes.
• La théorie : Elle établit des bases théoriques solides (conditions d'existence, bornes d'erreur) pour l'application des méthodes de base réduite aux problèmes de programmation linéaire paramétrés et aux espaces de Wasserstein.

En résumé, l'article propose un cadre robuste et efficace pour accélérer massivement la résolution de familles de problèmes de transport optimal, rendant ces outils applicables à des scénarios nécessitant de nombreuses requêtes paramétriques.