Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization

Résumé Technique : Estimation Robuste de l'Espace Tangent via LEGO

Énoncé du Problème
L'estimation des espaces tangents d'une variété de données est une tâche fondamentale de l'analyse de données géométriques, sous-tendant des applications telles que l'apprentissage de variétés (manifold learning), le débruitage de données, la détection de frontières et l'estimation de la dimension intrinsèque locale. L'approche standard, l'Analyse en Composantes Principales Locale (LPCA), construit une matrice de covariance locale à partir des $k$-plus proches voisins pour identifier la base tangente. Cependant, la LPCA souffre d'un compromis critique concernant la taille du voisinage : les voisinages de petite taille sont très sensibles à la corruption par le bruit, tandis que les voisinages plus larges introduisent un biais dû à la courbure sous-jacente et au rayon de courbure (reach) de la variété. La sélection d'une taille de voisinage optimale nécessite généralement une connaissance préalable des caractéristiques géométriques et du bruit qui sont souvent indisponibles, rendant le problème mal posé dans des contextions à fort bruit.

Méthodologie : LEGO
Les auteurs proposent LEGO (Laplacian Eigenvector Gradient Orthogonalization), une méthode spectrale qui exploite la structure globale des données pour guider l'estimation de l'espace tangent local. Au lieu de s'appuyer uniquement sur des voisinages locaux, LEGO estime l'espace tangent en chaque point de donnée en orthogonalisant les gradients des vecteurs propres de basse fréquence du Laplacien du graphe construit à partir des données bruitées.

L'algorithme procède comme suit :

1. Construction du Graphe : Un Laplacien de graphe $L$ est construit à partir du nuage de points bruité en utilisant des méthodes basées sur des noyaux (ex: marche aléatoire, auto-ajusté ou noyaux doublement stochastiques).
2. Estimation du Gradient : Les gradients des $m$ premiers vecteurs propres de basse fréquence ($\phi_1, \dots, \phi_m$) sont estimés en chaque point de donnée. Pour garantir la fidélité locale et la stabilité numérique, ces gradients sont modélisés comme des vecteurs dans l'espace engendré par les $m_0$ premiers vecteurs propres ($m_0 \gg m$).
3. Régularisation : Un terme de régularisation de Tikhonov est appliqué au processus d'estimation du gradient pour éviter l'explosion numérique dans les configurations à faible bruit ou de rang déficient. Le paramètre de régularisation $\eta_j$ est dérivé de la géométrie du voisinage local, avec un hyperparamètre $\beta$ contrôlant la puissance de la pénalité de distance.
4. Orthogonalisation : En chaque point $j$, les vecteurs de gradient estimés $\hat{\nabla}\phi(X_j)$ sont orthogonalisés (via SVD) pour extraire la base orthonormée $Q_j$ de l'espace tangent de dimension $d$. Si la dimension intrinsèque $d$ est inconnue, elle est déduite des valeurs singulières de la matrice de gradient.

Justifications Théoriques
L'article fournit deux cadres théoriques complémentaires pour justifier la robustesse de LEGO :

1. Perspective de la Géométrie Différentielle :
   Les auteurs modélisent les données bruitées comme des échantillons provenant d'un voisinage tubulaire $T_{\epsilon r}$ entourant une sous-variété propre de dimension $d$ notée $B$. Ils analysent les fonctions propres de Neumann du Laplacien sur ce tube.

   • Résultat Clé : Ils établissent des bornes montrant que la valeur propre $\lambda$ d'une fonction propre évolue comme $\Omega(\epsilon^{-2} E^\perp_B(\phi))$ par rapport à son « énergie verticale » (gradient dans la direction du bruit) et comme $O(E_B(\phi))$ par rapport à son « énergie horizontale » (gradient le long de la variété).
   • Implication : Les fonctions propres présentant des gradients significatifs dans la direction du bruit possèdent des valeurs propres élevées. Inversement, les fonctions propres de basse fréquence ont des gradients concentrés dans l'espace tangent (horizontal), faisant de leurs gradients des estimateurs robustes du fibré tangent.

2. Perspective de la Théorie des Matrices Aléatoires :
   Les auteurs analysent la stabilité des vecteurs propres du Laplacien sous un bruit sub-gaussien en utilisant un modèle « information plus bruit » où la variance proxy du bruit $\epsilon$ évolue comme $O(1/\sqrt{n \log n})$.

   • Résultat Clé : Ils prouvent que le Laplacien du graphe bruité converge vers le Laplacien propre en norme d'opérateur à un taux de $O(n^{-1/2})$. Selon le théorème de Davis-Kahan, à condition que les écarts propres (eigengaps) du Laplacien propre ne décroissent pas trop rapidement, les vecteurs propres du Laplacien bruité restent proches de ceux du Laplacien propre.
   • Implication : Sous ces conditions, les composantes horizontales des gradients estimés à partir des données bruitées convergent vers celles des données propres, garantissant la stabilité des estimations de l'espace tangent.

Contributions Clés

• Proposition Algorithmique : Introduction de LEGO, un algorithme spectral pour l'estimation robuste de l'espace tangent qui évite le compromis de taille de voisinage inhérent à la LPCA.
• Cadre Théorique : Dérivation de lois d'échelle asymptotiques pour les gradients de vecteurs propres sous un modèle de bruit tubulaire et preuve de la stabilité des vecteurs propres sous des perturbations sub-gaussiennes.
• Guidage des Hyperparamètres : Dérivation théorique suggérant $\beta = 1/2$ comme paramètre de régularisation de Tikhonov optimal lorsque les caractéristiques du bruit sont inconnues.
• Validation Empirique : Expériences exhaustives démontrant la supériorité de LEGO par rapport à la LPCA dans des contextes de bruit.

Résultats
Des expériences numériques sur des jeux de données synthétiques (Swiss roll à haut rapport d'aspect, tore tronqué) et des données réelles (jeu de données Puppets) démontrent que :

• Précision : LEGO produit des estimations d'espace tangent nettement plus robustes au bruit que la LPCA. L'écart entre l'espace tangent estimé et la vérité terrain reste faible même lorsque les niveaux de bruit augmentent, alors que les estimations de la LPCA se dégradent rapidement.
• Performance en Aval : L'amélioration des estimations de l'espace tangent conduit à des améliorations marquées des tâches en aval :
  • Apprentissage de Variétés : LEGO produit des plongements 2D précis qui préservent la topologie intrinsèque (ex: révélant la structure toroïdale du jeu de données Puppets), tandis que les plongements basés sur la LPCA s'effondrent ou deviennent non-injectifs.
  • Détection de Frontières : Les points de frontière détectés avec LEGO s'alignent étroitement avec la vérité terrain, tandis que la LPCA échoue à identifier les frontières avec précision en conditions de bruit.
  • Estimation de la Dimension Intrinsèque : LEGO concentre correctement la variance fonctionnelle dans les vraies dimensions intrinsèques, là où la LPCA alloue de manière fallacieuse la variance aux directions de bruit.

Signification
L'article affirme que LEGO offre une alternative fondée sur des principes en utilisant l'information spectrale globale pour filtrer le bruit. En démontrant que les vecteurs propres de basse fréquence du Laplacien du graphe s'alignent naturellement avec le fibré tangent de la variété sous-jacente tout en supprimant les composantes de bruit, les auteurs fournissent une solution robuste au problème de sélection de la taille du voisinage. Cette approche permet une analyse géométrique précise dans des régimes de fort bruit où les méthodes locales standards échouent, facilitant un apprentissage de variétés et une réduction de dimensionnalité plus fiables.