Résumé Technique : Complétion de Matrices Distributionnelles de Bas Rang

Définition du Problème

Cet article traite du problème de la complétion de matrices distributionnelles, une généralisation de la tâche classique de complétion de matrices de bas rang. Dans ce cadre, la matrice cible $\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}$ est composée d'entrées qui sont des distributions de probabilité sur un domaine $\mathcal{X}$, plutôt que des valeurs scalaires.

Le modèle d'observation est caractérisé par deux couches d'incomplétude :

1. Observation Partielle : Seul un sous-ensemble d'entrées de la matrice est observé, indiqué par un masque binaire $T(i,j)$.
2. Observation Indirecte : Même pour les entrées observées, la distribution sous-jacente $\rho^*(i,j)$ n'est pas directement accessible. Au lieu de cela, on observe un ensemble fini d'échantillons i.i.d. $\{X^{(ij)}_1, \dots, X^{(ij)}_{N_{ij}}\}$ tirés de $\rho^*(i,j)$, où la taille de l'échantillon $N_{ij}$ peut varier d'une entrée à l'autre.

L'objectif est de récupérer la matrice complète à valeurs distributionnelles $\rho^*$ (ou sa représentation) à partir de ces observations partielles et indirectes. Ce problème survient dans des applications telles que la modélisation de la variabilité des flux de trafic entre des localisations ou l'analyse de la distribution des prévisions de revenus à travers différents trimestres fiscaux et institutions.

Méthodologie

Plongements Moyens à Noyau (Kernel Mean Embeddings - KME)

Pour gérer la nature de dimension infinie des distributions de probabilité et éviter les contraintes de variétés associées aux fonctions de densité, les auteurs représentent chaque distribution $\rho^*(i,j)$ via son Plongement Moyen à Noyau (KME) dans un espace de Hilbert reproduisant (RKHS) $\mathcal{H}$ :
$$\mu^*(i, j, \cdot) = \mathbb{E}_{X \sim \rho^*(i,j)} [K(X, \cdot)] \in \mathcal{H}$$
Récupérer $\rho^*$ revient à récupérer la matrice de KME $\mu^* \in \mathcal{H}^{m_1 \times m_2}$. La distance entre les distributions est mesurée par la distance de Maximum Mean Discrepancy (MMD).

Modélisation de Bas Rang via le Dépliage Fonctionnel

Les auteurs proposent une structure de rang de Tucker pour la matrice distributionnelle. Ils considèrent $\mu^*$ comme un tenseur à trois modes dans l'espace $\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H}$. Puisque $\mathcal{H}$ est souvent de dimension infinie, les définitions standards du rang de tenseur ne s'appliquent pas directement.

Pour y remédier, l'article introduit des opérateurs de dépliage fonctionnel ($U_1, U_2, U_3$) qui projettent le tenseur dans des produits de deux espaces (par exemple, $U_1: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_1} \otimes (\mathbb{R}^{m_2} \otimes \mathcal{H})$). Ces opérateurs induisent des opérateurs linéaires dont les rangs définissent le rang multilinéaire $(r_1, r_2, r_3)$.

• Implication Structurelle : Un faible rang multilinéaire implique que les composantes fonctionnelles des KME résident dans un sous-espace de faible dimension, et que les matrices de fonctions d'espérance associées (par exemple, les matrices de moyennes) sont de bas rang.

Cadre d'Estimation

Les auteurs proposent un estimateur M régularisé $\hat{\mu}$ défini par la minimisation d'une fonction de perte plus une pénalité de norme nucléaire :
$$\hat{\mu} = \arg\min_{\mu} \left[ \frac{1}{m_1 m_2} \sum_{(i,j): T(i,j)=1} \left\| \mu(i, j, \cdot) - \hat{\mu}_{emp}(i, j, \cdot) \right\|_{\mathcal{H}}^2 + \lambda \Psi(\mu) \right]$$

• Terme de Perte : La MMD au carré entre le KME estimé et le KME empirique dérivé des échantillons observés.
• Régularisation : $\Psi(\mu) = \sum_{j=1}^3 \beta_j \|U_j \mu\|_*$, où $\|\cdot\|_*$ désigne la norme nucléaire de l'opérateur linéaire induit. Cela favorise le bas rang sur les trois modes.

Solution Computationnelle

Malgré la nature de dimension infinie de $\mathcal{H}$, le Théorème du Représentant garantit que la solution $\hat{\mu}$ réside dans l'espace de dimension finie engendré par les fonctions de noyau observées.

1. Le problème est re-paramétré en un problème d'optimisation de tenseur de dimension finie sur un tenseur de coefficients $B \in \mathbb{R}^{m_1 \times m_2 \times \tilde{N}}$.
2. Pour gérer de grands ensembles d'échantillons, les auteurs suggèrent d'approximer la matrice de Gram à l'aide de techniques d'approximation de noyau (par exemple, la méthode de Nyström ou les caractéristiques de Fourier aléatoires).
3. L'optimisation est résolue à l'aide d'une méthode de méthode d'alternance de direction de multiplicateur (ADMM) accélérée.

Contributions Clés

1. Nouvelle Formulation du Problème : L'article formalise la complétion de matrices pour des entrées à valeurs distributionnelles, abordant le défi de la récupération de distributions à partir de données d'échantillonnage partielles et bruitées.
2. Cadre Théorique : Il introduit une définition du rang de Tucker pour les tenseurs à valeurs distributionnelles via des opérateurs de dépliage fonctionnel, comblant le fossé entre les données fonctionnelles de dimension infinie et l'analyse de tenseurs de dimension finie.
3. Innovation Algorithmique : L'estimateur proposé utilise une régularisation par norme nucléaire sur les opérateurs linéaires induits. Crucialement, les auteurs prouvent que la solution admet une représentation de dimension finie, rendant le problème calculablement traitable via l'optimisation convexe.
4. Garanties Statistiques : L'article établit des bornes d'erreur non asymptotiques pour la MMD au carré agrégée.
   • Le taux de convergence correspond à celui de la complétion de matrices classique régularisée par la norme nucléaire pour les matrices scalaires.
   • Contrairement aux approches de voisinage proches existantes (par exemple, Feitelberg et al., 2024), la cohérence de la méthode proposée ne nécessite pas que le nombre d'échantillons par entrée ($N_{ij}$) diverge. Au lieu de cela, la cohérence est obtenue à mesure que les dimensions de la matrice ($m_1, m_2$) augmentent, exploitant la structure de bas rang globale pour le partage d'informations.

Résultats Expérimentaux

Données Synthétiques

• Configuration : Matrices simulées avec des distributions de mélanges gausiens. Les comparaisons ont été faites avec une méthode de plus proche voisin (NN) (Feitelberg et al., 2024) et une complétion de matrice classique (SOFTIMPUTE) appliquée aux moyennes et variances d'échantillons.
• Résultats :
  • La méthode proposée (LRKME) a systématiquement surpassé la méthode NN tant pour les entrées observées que non observées, particulièrement dans l'estimation de la variance et des statistiques d'ordre supérieur.
  • LRKME a également surpassé SOFTIMUTE, démontrant l'avantage d'utiliser l'information distributionnelle complète plutôt que de simples résumés scalaires.
  • Dans les contextes 2D, la méthode NN a été exclue en raison de l'intraitabilité computationnelle des distances de Wasserstein multivariées, tandis que LRKME est restée efficace.

Application au Monde Réel

• Jeu de Données : Données de trajets de taxis de NYC, modélisant la distribution du nombre de trajets quotidiens entre 265 lieux de départ et de destination.
• Défi : Taux de données manquantes élevé (>39 %) et tailles d'échantillons par entrée très variables (de 1 à 3672).
• Résultats : LRKME a obtenu une erreur relative empirique significativement plus faible (0,0015) que la méthode NN (0,0212) sur l'ensemble de test. L'inspection visuelle de cas spécifiques a montré que LRKME capture mieux les distributions à queue lourde et les modèles de concentration par rapport à l'estimateur NN.

Signification et Revendications

L'article affirme fournir la première méthode de complétion de matrices distributionnelles qui :

1. Accueille des schémas d'observation généraux avec des tailles d'échantillons variables.
2. S'étend naturellement aux distributions multidimensionnelles sans les goulots d'étranglement computationnels des méthodes basées sur Wasserstein.
3. Offre des garanties de cohérence globale qui ne dépendent pas de la croissance asymptotique des échantillons par entrée, mais reposent plutôt sur la structure de bas rang de la matrice.
4. Fournit une solution computationnellement efficace via une représentation de dimension finie et l'optimisation convexe.

Les auteurs positionnent leur travail comme une avancée significative par rapport aux approches de voisinage proches existantes, offrant un cadre plus robuste, théoriquement mieux fondé et plus scalable pour imputer des données distributionnelles manquantes.