Algebraic Distance Optimization in Polyhedral Norms

1. Problématique et Contexte

Le papier aborde le problème d'optimisation de la distance entre un point observé $v \in \mathbb{R}^n$ et une variété algébrique réelle $X \subseteq \mathbb{R}^n$, mais dans un cadre métrique spécifique : la distance est induite par une norme polyédrique (et non la norme euclidienne usuelle).

• Contexte d'application : Ce type de problème apparaît en statistiques algébriques, vision par ordinateur, apprentissage automatique et phylogénétique. Une motivation principale provient du transport optimal, où la distance de Wasserstein sur le simplexe des probabilités est induite par un polytope convexe (le polytope de Lipschitz).
• Question inverse : Au lieu de chercher le point de $X$ le plus proche d'un point $v$, les auteurs étudient le problème inverse : étant donné un point $p \in X$, quels points de l'espace ambiant $\mathbb{R}^n$ ont $p$ comme point de projection unique (ou optimal) ? L'ensemble de ces points forme la cellule de Voronoï de $p$.
• Objectif central : Caractériser géométriquement et algébriquement les cellules de Voronoï, le diagramme de Voronoï et l'axe médian (l'ensemble des points dont la distance à $X$ est minimisée par au moins deux points distincts de $X$) dans le contexte des normes polyédriques.

2. Méthodologie

Les auteurs combinent la géométrie polyédrique, la topologie différentielle et l'algèbre commutative pour analyser la structure de ces ensembles.

A. Géométrie Polyédrique et Normes

• Norme Polyédrique : Définie par un polytope convexe centré $B$ (la boule unité). La distance entre $x$ et $y$ est $h_L(x-y) = \max_{\ell \in L} \ell(x-y)$.
• Éventail Normal Interne ($\Sigma_B$) : L'analyse repose sur la relation entre l'espace normal de la variété $X$ en un point $p$ et l'éventail normal interne de la boule unité $B$.
• Type d'un point : Pour un point lisse $p \in X$, le « type » est défini comme l'ensemble des faces de $B$ dont les cônes normaux internes intersectent l'espace normal $N_p X$.

B. Cellules de Voronoï et Cônes

• Les auteurs établissent que la cellule de Voronoï d'un point $p$ est contenue dans une union de cônes polyédraux, appelée cône de Voronoï ($VCone(p)$).
• Ce cône est déterminé par l'intersection de l'espace normal $N_p X$ avec l'éventail normal de la boule duale $B^*$. Plus précisément, $VCone(p)$ est l'union des cônes normaux des faces duales correspondant aux faces de $B$ dans le type de $p$.

C. Stratification des Variétés

Pour les variétés de codimension 1 (hypersurfaces), l'espace normal est de dimension 1. Les auteurs utilisent cela pour stratifier la variété $X$ :

• Ils définissent une application $\phi$ de l'espace des normales vers l'espace projectif réel $\mathbb{RP}^{n-1}$.
• Ils stratifient $\mathbb{RP}^{n-1}$ selon la dimension des faces du polytope $B$ (faces de dimension $n-1-i$).
• En tirant en arrière cette stratification via l'application normale de $X$, ils obtiennent une stratification de $X$ où chaque strate $X_i$ contient les points dont les cônes de Voronoï attendus ont une dimension spécifique ($n-i$).
• Ils prouvent que cette décomposition est une stratification au sens topologique (les strates sont des ensembles semi-algébriques, localement fermés, et satisfont la condition de frontière).

D. Axe Médian et Idéal Équidistant

Pour caractériser l'axe médian, les auteurs construisent un idéal algébrique :

• Ils considèrent des paires de faces $(F_1, F_2)$ de la boule unité.
• Ils définissent un idéal $J_{(F_1, F_2)}$ engendré par les équations de la variété, les conditions de distance égale ($h(u-x) = h(u-y) = \lambda$) et les conditions de tangence (minors de matrices de gradients).
• L'idéal équidistant $I_{Eq}$ est l'intersection de tous les idéaux d'élimination associés aux paires de faces. La variété algébrique $V(I_{Eq})$ contient l'axe médian.

3. Résultats Clés

Stratification et Ensembles Semi-Algébriques

• Théorème 4.4 : Pour une variété lisse de codimension 1, la décomposition basée sur la dimension des cônes de Voronoï forme une stratification valide de la variété.
• Théorème 4.8 : Chaque strate de cette décomposition est un ensemble semi-algébrique. Cela permet de décrire explicitement ces ensembles à l'aide de systèmes d'inégalités et d'équations polynomiales.

Description de l'Axe Médian

• Théorème 5.5 : L'axe médian $Med_h(X)$ est contenu dans la clôture algébrique $M_X$, qui elle-même est contenue dans la variété $V(I_{Eq})$. Bien que $V(I_{Eq})$ puisse être plus grand que l'axe médian (car il ne impose pas toujours la minimalité stricte de la distance), il fournit une sur-approximation algébrique exacte.
• Exemples : Les auteurs montrent que l'axe médian peut être vide, de dimension pleine, ou avoir des composantes de dimensions variées, contrairement au cas euclidien où la structure est souvent plus rigide.

Bornes de Degré (Degree Bounds)

Les auteurs établissent des bornes supérieures sur le degré des composantes de l'axe médian en fonction du degré $d$ de la variété $X = V(f)$ :

• Deux sommets (Théorème 5.11) : Si les faces optimisantes sont deux sommets de la boule, le degré de la composante correspondante est borné par $d^2 - d$.
• Un sommet et une facette (Théorème 5.12) : Le degré est borné par $d$ (multiplié par le nombre de points tangents).
• Deux facettes (Théorème 5.13) : Le degré est borné par le produit du nombre de points tangents aux deux facettes ($s \times t$).
• Cas quadratique (Proposition 5.15) : Si $X$ est une quadrique ($d=2$), le degré de toute composante de l'axe médian est au plus 4.

4. Signification et Contributions

• Généralisation des résultats euclidiens : Le papier étend les travaux antérieurs (notamment [1, 7]) qui se concentraient sur la métrique euclidienne, en intégrant la complexité géométrique des normes polyédriques (non lisses, non strictement convexes).
• Lien entre géométrie locale et globale : Il établit un lien clair entre la géométrie locale de la variété (son espace normal) et la géométrie globale du diagramme de Voronoï via l'éventail normal du polytope dual.
• Outils pour le calcul symbolique : En prouvant que les strates sont semi-algébriques et en fournissant des bornes de degré précises, le papier ouvre la voie à des algorithmes de calcul effectif (via des bases de Gröbner ou l'élimination) pour déterminer les régions de stabilité et les axes médians dans des applications pratiques comme le transport optimal ou l'analyse de données.
• Compréhension des singularités : L'analyse montre comment les singularités de la norme (les faces du polytope) interagissent avec les singularités de la variété (points de selle, courbure) pour créer des comportements complexes dans l'axe médian (ex: composantes de dimension pleine).

En résumé, ce travail fournit un cadre théorique rigoureux et des outils algorithmiques pour l'optimisation de distance dans des espaces métriques non-euclidiens définis par des polytopes, avec des applications potentielles majeures dans les domaines où la géométrie des données est intrinsèquement polyédrique.