Résumé technique : Débruitage de données par auto-cohérence, maximisation de la variance et dominance de Kantorovich

1. Formulation du problème

L'article traite le problème fondamental du débruitage de données (ou de réduction de dimension), défini comme l'inférence d'une distribution de signal inconnue $\mu$ à partir d'une distribution bruitée observée $\nu$. Les auteurs supposent que le signal appartient à un domaine structuré $\mathcal{D}$ de mesures de probabilité de Borel.

Les approches existantes se divisent généralement en deux catégories :

1. Minimisation de la distance : Trouver $\mu \in \mathcal{D}$ le plus proche de $\nu$ selon la métrique de Wasserstein ($W_2$). Cela correspond à un problème « relaxé » (ex: $k$-moyennes, courbes principales).
2. Auto-cohérence : Trouver $\mu \in \mathcal{D}$ tel que l'espérance conditionnelle du bruit soit nulle (c'est-à-dire $\mathbb{E}[Y|X]=X$ pour un couplage entre $\mu$ et $\nu$). Cela équivaut à exiger un couplage martingale, ou que $\mu$ soit dominé par $\nu$ dans l'ordre convexe ($\mu \preceq_C \nu$).

Les auteurs identifient une lacune : bien que l'auto-cohérence soit une propriété souhaitable (apparaissant comme une condition d'optimalité du premier ordre pour la minimisation de la distance dans des cas simples), les solutions dérivées uniquement de l'auto-cohérence ne minimisent généralement pas la distance par rapport aux données. Inversement, la minimisation de la distance n'impose pas l'auto-cohérence. L'article propose un cadre unifié qui cherche la distribution $\mu \in \mathcal{D}$ qui est la plus proche de $\nu$ tout en satisfaisant simultanément l'auto-cohérence.

2. Méthodologie

2.1 Le cadre de l'ordre convexe

Les auteurs formulent le problème de débruitage comme suit :
$$\min_{\mu \in \mathcal{D}} \min_{\pi \in \mathcal{M}(\mu, \nu)} \int |x-y|^2 d\pi(x,y)$$
où $\mathcal{M}(\mu, \nu)$ est l'ensemble des couplages martingaux. Selon le théorème de Strassen, un couplage martingale existe si et seulement si $\mu \preceq_C \nu$. Puisque la distance de Wasserstein sous contraintes martingales se simplifie en la différence de variances ($\text{Var}(\nu) - \text{Var}(\mu)$), le problème est équivalent à la maximisation de la variance de $\mu$ au sein du domaine $\mathcal{D}$ sous la contrainte de l'ordre convexe :
$$\max_{\mu \in \mathcal{D}, \mu \preceq_C \nu} \text{Var}(\mu)$$

Propriétés clés du problème d'ordre convexe :

• Existence : Des solutions existent pour des domaines fermés $\mathcal{D}$ dont l'intersection avec l'ensemble de l'ordre convexe est non vide.
• Robustesse : Si le bruit est faible (c'est-à-dire que $\nu$ est proche d'un signal réel $\rho \in \mathcal{D}$ avec $\rho \preceq_C \nu$), la solution $\mu^*$ est quantifiablement proche de $\rho$.
• Limitations :
  • Difficulté computationnelle : Vérifier la condition d'ordre convexe $\mu \preceq_C \nu$ est non trivial.
  • Instabilité : La solution peut être instable face aux perturbations des données $\nu$.
  • Trivialité : Pour certains domaines, l'ensemble $\{\mu \in \mathcal{D} \mid \mu \preceq_C \nu\}$ peut être vide ou ne contenir que des solutions triviales (ex: des masses de Dirac), rendant le problème non informatif.

2.2 La relation de dominance de Kantorovich (KDR)

Pour remédier aux limites de l'ordre convexe, les auteurs introduisent une relation plus faible appelée dominance de Kantorovich ($\mu \preceq_K \nu$).
$\mu \preceq_K \nu$ s'il existe un couplage $\pi \in \Pi(\mu, \nu)$ tel que :
$$\int \langle x - b_\nu, y - x \rangle d\pi(x,y) = 0$$
où $b_\nu$ est le barycentre de $\nu$. En supposant des mesures centrées, cela équivaut à :
$$\sup_{\pi \in \Pi(\mu, \nu)} \int \langle x, y \rangle d\pi(x,y) \geq \int |x|^2 d\mu(x)$$
Cette condition implique que le « coût de Kantorovich » (corrélation maximale) domine le second moment de $\mu$.

Propriétés de la KDR :

• Relaxation : C'est une relaxation de l'ordre convexe ($\mu \preceq_C \nu \implies \mu \preceq_K \nu$).
• Condition d'optimalité : Pour une classe de domaines appelés cônes (fermés par mise à l'échelle), la condition KDR apparaît naturellement comme une condition d'optimalité pour le problème de minimisation de la distance relaxée.
• Stabilité : Contrairement au problème d'ordre convexe, le débruitage basé sur la KDR est stable par rapport aux perturbations des données $\nu$.
• Compacité : Bien que l'ensemble des mesures dominées par $\nu$ dans l'ordre convexe soit compact, l'ensemble sous la KDR n'est pas nécessairement compact pour la métrique $W_2$, à moins d'être restreint à un support compact $\Omega$.

2.3 Le problème variationnel KDR

Les auteurs proposent le problème de débruitage suivant utilisant la KDR :
$$\max_{\mu \in \mathcal{D} \cap \mathcal{M}^K_{\nu, \Omega}} \text{Var}(\mu)$$
où $\mathcal{M}^K_{\nu, \Omega}$ est l'ensemble des mesures dans un ensemble compact $\Omega$ dominées par $\nu$ en KDR.

Résultats théoriques clés :

1. Équivalence pour les cônes : Si $\mathcal{D}$ est un cône et est invariant par translation (ou contient des mesures centrées), le problème KDR est équivalent au problème de minimisation de la distance de Wasserstein entièrement relaxé ($\min_{\mu \in \mathcal{D}} W_2^2(\mu, \nu)$).
2. Équivalence pour les optimiseurs faibles : Si $\mathcal{D}$ est fermé sous « optimiseurs faibles » (une condition liée au recentrage barycentrique), la solution KDR satisfait la pleine condition d'auto-cohérence ($\mu \preceq_C \nu$).
3. Récupération de la PCA : Lorsque $\mathcal{D}$ est l'ensemble des mesures supportées sur des sous-espaces de dimension $m$, le problème KDR récupère l'Analyse en Composantes Principales (PCA). Crucialement, contrairement à la formulation de l'ordre convexe, la formulation KDR permet des solutions non triviales même lorsque les données sont discrètes (ex: mesures empiriques), là où la contrainte d'ordre convexe forcerait la solution à être une masse de Dirac.

3. Contributions clés

1. Cadre unifié : L'article introduit un cadre qui unifie la minimisation de la distance et l'auto-cohérence en formulant le débruitage comme un problème de maximisation de la variance sous une contrainte de dominance de distribution.
2. Dominance de Kantorovich : L'introduction d'une nouvelle relation de dominance plus faible qui conserve l'esprit des couplages martingaux (auto-cohérence) mais offre une tractabilité computationnelle et une stabilité supérieures.
3. Garanties théoriques : Preuve de l'existence, de la robustesse et de la stabilité des problèmes proposés. L'article démontre que pour des domaines spécifiques (cônes), l'exigence complexe d'auto-cohérence s'effondre en une minimisation de distance standard, tandis que pour d'autres, elle fournit une solution intermédiaire significative.
4. Lien avec les méthodes classiques : Les auteurs montrent rigoureusement comment l'Analyse en Composantes Principales (PCA), les $k$-moyennes et les courbes principales émergent comme des cas particuliers de leur cadre sous des choix de domaines appropriés.

4. Résultats numériques

Les auteurs fournissent des exemples numériques résolvant le problème KDR en utilisant un algorithme de Lloyd généralisé et l'algorithme de Sinkhorn pour un calcul de couplage efficace.

• Courbes principales : La méthode ajuste avec succès des courbes à des données bruitées, surpassant ou égalant les définitions existantes de courbes principales (Hastie-Stuetzle, Kegl et al., Tibshirani) pour capturer les structures sous-jacentes.
• Comparaison de stabilité : Les expériences numériques illustrent que, tandis que la solution d'auto-cohérence (ordre convexe) peut être instable ou ne pas exister pour des données discrètes, la solution KDR reste stable et informative.
• Scalabilité : L'approche KDR permet de traiter des ensembles de données plus larges (ex: 5000 points) là où la formulation de l'ordre convexe échoue en raison de contraintes de mémoire ou d'absence de solutions réalisables.

5. Signification et affirmations

L'article affirme fournir un « paradigme général pour le débruitage de données » qui capture les caractéristiques clés de la minimisation de la distance et de l'auto-cohérence. Sa principale importance réside dans :

• Résolution de l'instabilité : Il offre une alternative stable à l'approche d'auto-cohérence, qui est sujette à l'instabilité et aux solutions triviales.
• Pont entre théorie et pratique : En introduisant la dominance de Kantorovich, les auteurs créent un pont entre l'élégance théorique du transport optimal de type martingale et les exigences pratiques des algorithmes de débruitage (efficacité computationnelle et stabilité).
• Généralisation de la PCA : Ce travail présente la PCA non pas seulement comme une projection linéaire, mais comme un cas spécifique d'un problème plus large de maximisation de la variance sous dominance de distribution, étendant son applicabilité à des contextes non linéaires et contraints.

Les auteurs restent modestes quant à la stabilité quantitative de la solution KDR, notant que si une stabilité qualitative est prouvée, une version quantitative de la borne de stabilité demeure une direction ouverte et un défi pour la recherche future.