Annealed quantitative estimates for the quadratic 2D-discrete random matching problem

1. Énoncé du problème

L'article traite du problème d'appariement aléatoire quadratique sur une variété riemannienne 2D fermée et compacte $M$ (sans bord).

• Configuration : Deux suites de points aléatoires, $\{X_i\}_{i=1}^n$ et $\{Y_j\}_{j=1}^m$, sont échantillonnées sur $M$. L'objectif est de minimiser la somme des distances riemanniennes au carré entre les paires appariées.
• Formulation mathématique : Cela équivaut à trouver la distance de Wasserstein quadratique $W_2^2(\mu_n, \nu_m)$ entre les mesures empiriques $\mu_n = \frac{1}{n}\sum \delta_{X_i}$ et $\nu_m = \frac{1}{m}\sum \delta_{Y_j}$.
• Contexte : Bien que l'échelle asymptotique du coût soit bien comprise pour des échantillons uniformes indépendants et identiquement distribués (i.i.d.) (s'échelonnant comme $\frac{\log n}{n}$ en 2D), ce travail se concentre sur des estimations quantitatives pour la carte de transport elle-même dans des conditions plus générales :
  1. Densités non uniformes : Les points sont distribués selon une densité $\rho$ (bornée et strictement positive).
  2. Corrélations : Les points ne sont pas nécessairement i.i.d. ; ils peuvent présenter des corrélations (par exemple via un $\alpha$-mélange ou des chaînes de Markov).
  3. Tailles d'échantillon inégales : $n$ et $m$ sont asymptotiquement équivalents mais pas nécessairement égaux.

2. Méthodologie

Les auteurs emploient une hypothèse de linéarisation combinée à une analyse de stabilité quantitative et des inégalités de concentration probabilistes.

A. Linéarisation de l'équation de Monge-Ampère

L'idée centrale, issue de Caracciolo et al. [16] et rigoureusement justifiée par Ambrosio et al. [6], consiste à approximer la carte de transport optimale $T^n$ par une perturbation de l'application identité :
$$T^n \approx \text{Id} + \nabla h_n$$
où $h_n$ est une fonction potentielle. Formellement, l'équation de Monge-Ampère $(\nu_n \circ T^n) \det(\nabla T^n) = \mu_n$ est linéarisée pour aboutir à une équation de type Poisson :
$$\nabla \cdot (\rho \nabla h_n) = \mu_n - \nu_n$$
Cependant, le terme source $\mu_n - \nu_n$ est trop irrégulier (une somme de masses de Dirac) pour que $h_n$ appartienne directement à $H^1$.

B. Stratégie de régularisation

Pour gérer cette irrégularité, les auteurs introduisent une régularisation par semi-groupe de la chaleur au temps $t \sim \frac{\log^\kappa n}{n}$.

1. Mesures lissées : Définir $\mu_{n,t} = P_t \mu_n$ et $\nu_{m,t} = P_t \nu_m$, où $P_t$ est le semi-groupe de la chaleur.
2. EDP régularisée : Résoudre pour $h_{n,t}$ dans l'équation :
   $$\nabla \cdot (\rho \nabla h_{n,t}) = \mu_{n,t} - \nu_{m,t}$$
3. Plan d'approximation : Construire le plan de transport candidat $\gamma_{n,t} = (\text{Id}, \exp(\nabla h_{n,t}))_\# \mu_{n,t}$.

C. Décomposition de l'erreur

La stratégie de preuve divise l'erreur entre le plan optimal $\pi$ et le plan approché $\gamma_{n,t}$ en deux composantes principales :

1. Erreur de régularisation : La distance entre le plan lissé $\gamma_{n,t}$ et le plan dérivé de la solution non lissée (mais à densité régularisée). Cela est contrôlé à l'aide d'estimations d'énergie et d'estimations de Meyers pour les opérateurs elliptiques à coefficients irréguliers.
2. Erreur de stabilité : La distance entre le plan lissé et le plan optimal véritable. Cela repose sur la stabilité quantitative des cartes de transport (Théorème 2.1), qui stipule que si les mesures cibles sont proches en $W_2$, les cartes de transport sont proches en $L^2$.

D. Gestion des corrélations

Un obstacle technique majeur est la prise en compte d'échantillons non i.i.d. Les auteurs supposent :

• $\alpha$-mélange : Les corrélations décroissent à un taux exponentiel étiré : $\alpha_\ell \leq a \exp(-b \ell^\eta)$.
• $\beta$-mélange : Contrôlé via la somme des coefficients de mélange.
• Chaînes de Markov : Les résultats s'étendent aux chaînes de Markov sous-géométriquement ergodiques satisfaisant une condition de dérive.
  Les auteurs utilisent des inégalités de concentration (Proposition A.1) adaptées à ces suites corrélées pour borner les fluctuations des mesures empiriques et des solutions aux EDP.

3. Contributions et résultats clés

Théorèmes principaux

L'article établit des estimations quantitatives recuites (bornes en espérance) pour la convergence du plan de transport.

• Théorème 1.2 (Appariement complet) : Pour deux nuages de points satisfaisant les hypothèses de mélange, le plan de transport optimal $\pi$ entre $\mu_n$ et $\nu_m$ est approché quantitativement par $\gamma_{n,t}$.
  $$\inf_{\pi} W_2^2(\pi, \gamma_{n,t}) \leq C_n \frac{\log n}{n} \sqrt{\frac{\log \log n}{\log n}}$$
  où $C_n$ est une variable aléatoire à moments bornés. Si la décroissance du mélange est suffisamment rapide ($\eta > 2$), la borne s'améliore et l'hypothèse sur la somme des coefficients de $\beta$-mélange peut être abandonnée.

• Théorème 1.3 (Appariement semi-discret) : Pour l'appariement entre la mesure continue $\rho dm$ et la mesure empirique $\mu_n$, la carte optimale $T^n$ est approchée par $\exp(\nabla f_{n,t})$ en $L^2$ avec les mêmes taux de convergence.

Innovations techniques

1. Extension aux données corrélées : C'est le premier travail à justifier rigoureusement l'hypothèse de linéarisation pour des points aléatoires corrélés (au-delà des i.i.d.) dans le contexte du transport optimal.
2. Ergodicité sous-géométrique : Les résultats sont étendus à une classe de chaînes de Markov en temps discret qui ne sont pas géométriquement ergodiques mais satisfont une condition de dérive sous-géométrique.
3. Régularisation affinée : Les auteurs optimisent les paramètres de régularisation (temps $t$ et lissage de densité $\delta$) pour équilibrer le compromis entre l'irrégularité du terme source et la stabilité de la carte de transport, atteignant des taux qui correspondent à l'échelle optimale connue pour le coût.
4. Analyse de Fourier et concentration : La preuve repose fortement sur l'analyse de Fourier du noyau de la chaleur et de nouvelles inégalités de concentration pour les sommes corrélées afin de contrôler les normes $L^q$ du gradient du potentiel $h_{n,t}$.

4. Importance

• Justification rigoureuse des heuristiques de physique : L'article fournit une fondation mathématique rigoureuse pour l'"hypothèse de linéarisation" largement utilisée en physique statistique (par exemple par Caracciolo, Lucibello, Parisi, Sicuro) pour dériver les coûts asymptotiques. Il va au-delà du simple coût pour examiner la structure de la carte de transport.
• Robustesse aux dépendances : En traitant des données corrélées et des chaînes de Markov, les résultats sont applicables à une classe beaucoup plus large de systèmes physiques et économiques où l'indépendance est une mauvaise hypothèse (par exemple, systèmes de particules en interaction, données de séries temporelles).
• Précision quantitative : L'article fournit des taux de convergence explicites avec une intégrabilité stochastique précise (par exemple, moments exponentiels pour les constantes d'erreur), ce qui est crucial pour les applications nécessitant des garanties à haute probabilité.
• Problèmes ouverts : Les auteurs discutent de la netteté de ces taux (suggérant qu'une linéarisation du second ordre pourrait être nécessaire pour l'optimalité) et des extensions potentielles aux coûts $p$, aux ensembles de Ginibre et aux gaz de Coulomb.

Conclusion

Clozeau et Mattesini généralisent avec succès la théorie quantitative de l'appariement aléatoire en 2D. Ils démontrent que l'équation de Monge-Ampère linéarisée, lorsqu'elle est correctement régularisée, fournit une approximation hautement précise du plan de transport optimal, même en présence de corrélations complexes et de densités non uniformes, avec des taux de convergence correspondant aux limites théoriques du coût d'appariement.