Approximation theorems in bilipschitz invariant theory

1. Problématique et Contexte

La théorie des invariants bilipschitziens vise à trouver des plongements à faible distorsion des espaces d'orbites $R^d/G$ (où $G$ est un sous-groupe fini de $O(d)$ agissant sur l'espace euclidien) vers un espace euclidien $R^n$. L'objectif est de définir une application $G$-invariante $f: R^d \to R^n$ telle que l'application induite $f_\downarrow: R^d/G \to R^n$ préserve la métrique quotient avec une distorsion minimale.

La distorsion est définie comme le rapport $\text{dist}(f_\downarrow) = \beta(f_\downarrow) / \alpha(f_\downarrow)$, où $\alpha$ et $\beta$ sont respectivement les bornes inférieure et supérieure de l'étirement de la métrique. La distorsion euclidienne $c_2(R^d/G)$ est la distorsion minimale possible.

Bien que des valeurs exactes de $c_2(R^d/G)$ soient connues pour trois cas spécifiques :

1. Rotations planes ($d=2$, $G \subset SO(2)$),
2. Récupération de phase réelle ($G = \{\pm I\}$),
3. Groupes de réflexion finis,

les méthodes existantes pour atteindre ces distorsions optimales sont souvent spécifiques à chaque cas. Les « banques de filtres max » (max filter banks), qui utilisent des filtres de la forme $\langle\langle [x], [y] \rangle\rangle = \max_{g \in G} \langle x, gy \rangle$, offrent une approche universelle mais souffrent d'un écart de distorsion par rapport à l'optimum théorique dans ces cas connus.

Le problème central est de savoir si cet écart peut être comblé universellement en post-composant une banque de filtres max avec une transformation linéaire, et si cela permet d'atteindre la distorsion euclidienne optimale.

2. Méthodologie

Les auteurs proposent une approche en deux étapes pour prouver que la distorsion optimale est atteignable (ou approchée arbitrairement) par une composition d'une banque de filtres max et d'une application linéaire.

A. Réduction à l'inclusion d'espaces de fonctions Lipschitziennes

Le cœur de la preuve repose sur le Lemme 4, qui établit que si les fonctions coordonnées d'un plongement bilipschitzien optimal $h$ résident dans la clôture de Lipschitz de l'espace engendré par les filtres max, alors on peut approximer $h$ avec une distorsion arbitrairement proche de l'optimum.
Cela transforme le problème géométrique en un problème d'analyse fonctionnelle : montrer que les fonctions coordonnées optimales appartiennent à $\overline{\text{span}}(\mathcal{M})$, où $\mathcal{M}$ est l'ensemble des filtres max.

B. Analyse par Cas (Théorème 5)

Les auteurs démontrent cette inclusion pour les trois cas de référence en utilisant des techniques fondamentalement différentes, soulignant l'absence d'une preuve unifiée simple :

1. Cas des rotations planes ($d=2$) :

   • Les fonctions coordonnées optimales sont des polynômes $G$-invariants.
   • Les auteurs utilisent l'analyse harmonique (séries de Fourier) pour exprimer ces polynômes comme des combinaisons intégrales de filtres max.
   • Ils montrent que ces combinaisons intégrales appartiennent à la clôture de Lipschitz des combinaisons linéaires finies de filtres max (Théorème 13 et 14).

2. Cas de la récupération de phase réelle ($G = \{\pm I\}$) :

   • Ici, les filtres max sont de la forme $|\langle x, y \rangle|$.
   • Les fonctions coordonnées optimales sont des polynômes pairs.
   • L'approche utilise la théorie des harmoniques sphériques pour décomposer les polynômes pairs en combinaisons intégrales de filtres max (Théorème 16).
   • Une distinction cruciale est faite : contrairement aux autres cas, l'espace des fonctions linéaires par morceaux homogènes ($PL_h$) est strictement plus grand que l'espace engendré par les filtres max.

3. Cas des groupes de réflexion :

   • Pour ces groupes, la distorsion optimale est 1 (isométrie).
   • L'embedding optimal est la projection sur un Weyl chamber.
   • Les auteurs démontrent que dans ce cas, l'espace engendré par les filtres max est fini-dimensionnel et coïncide exactement avec l'espace des fonctions coordonnées optimales. Aucune approximation n'est nécessaire ($\epsilon = 0$).

3. Contributions Clés

• Théorème Principal (Théorème 3) : Pour les trois cas cités ci-dessus, il existe une banque de filtres max $\Phi$ et une application linéaire $L$ telles que la composition $L \circ \Phi$ atteint une distorsion arbitrairement proche de $c_2(R^d/G)$. Dans le cas des groupes de réflexion, la distorsion exacte est atteinte.
• Caractérisation des Espaces Fonctionnels (Théorème 5) : Une analyse fine des relations d'inclusion entre les espaces de fonctions :
  • Espaces des coordonnées optimales ($\text{span}\{h_i\}$),
  • Espaces des combinaisons de filtres max ($\text{span } \mathcal{M}$),
  • Espaces des polynômes invariants ($\text{ext } P_G$),
  • Espaces des fonctions linéaires par morceaux homogènes ($PL_h$).
    Cette analyse révèle que les mécanismes sous-jacents diffèrent radicalement selon le type de groupe (ex: dans le cas des réflexions, les filtres max ne peuvent pas approximer universellement toutes les fonctions Lipschitziennes invariantes car l'espace est fini-dimensionnel).
• Résultats Numériques : Des expériences montrent que l'approche « LMF » (Linear Max Filter), c'est-à-dire l'apprentissage d'une couche linéaire post-composée à une banque de filtres max, surpasse systématiquement les banques de filtres max brutes et les réseaux de neurones standards pour minimiser la distorsion empirique sur divers groupes (y compris des groupes non traités théoriquement comme les groupes de symétrie de formes 2D).

4. Résultats

• Théorétique : La preuve que la distorsion optimale peut être approchée par des architectures de type « Filtres Max + Linéaire » pour les cas fondamentaux de la théorie des invariants.
• Expérimental :
  • Sur des données synthétiques (rotations, réflexions, récupération de phase), la méthode LMF atteint des distorsions très proches de la borne théorique optimale (ex: $\approx 1.41$ pour $R^2/\{\pm I\}$, contre $\approx 1.66$ pour les filtres max seuls).
  • Sur des données réelles (districts congressionnels des États-Unis et base de données de formes 2D), l'approche LMF produit des plongements à faible distorsion qui préservent la structure géométrique des données (convexité, excentricité) mieux que les méthodes de référence.
  • Les résultats suggèrent que cette approche est généralisable à d'autres groupes fermés de $O(d)$.

5. Signification et Impact

Ce travail établit un pont crucial entre la théorie des invariants géométriques et l'apprentissage automatique (machine learning).

1. Validation de l'approche « Max Filter + Linéaire » : Il démontre que l'ajout d'une simple couche linéaire après un filtre invariant (max filter) n'est pas seulement une heuristique pratique, mais qu'elle possède des garanties théoriques fortes pour atteindre la distorsion minimale dans des cas importants.
2. Compréhension des Limites : En montrant que les cas (a), (b) et (c) nécessitent des preuves distinctes et interagissent différemment avec les espaces de fonctions, le papier met en lumière la complexité de l'approximation universelle dans les espaces quotients.
3. Applications en Traitement de Signal et ML : Les résultats ouvrent la voie à la conception de réseaux de neurones invariants plus efficaces pour le traitement de signaux symétriques, où la préservation de la métrique est cruciale (ex: reconnaissance de formes, analyse de données géométriques).
4. Ouverture de Problèmes : Le papier pose des questions ouvertes sur la généralisation de ces résultats à tous les sous-groupes fermés de $O(d)$ et sur l'existence d'une preuve unifiée pour l'inclusion des espaces fonctionnels.

En résumé, ce papier fournit une justification théorique robuste pour l'utilisation de banques de filtres max post-composées à des transformations linéaires comme méthode universelle et quasi-optimale pour l'embedding d'espaces d'orbites, avec des implications directes pour l'ingénierie des caractéristiques (feature engineering) en apprentissage automatique invariant.