Containments of Tensor Network Varieties

Résumé Technique : Contenances des variétés de réseaux de tenseurs

Énoncé du Problème
L'article traite de la question fondamentale de la contenance entre les variétés de réseaux de tenseurs. Étant donné deux formats de tenseurs encodés par des arbres binaires, les auteurs étudient si l'ensemble de tous les tenseurs représentables par un réseau donné (la variété) est contenu dans l'ensemble représentable par un autre. Ce problème généralise la « Conjecture de Hackbusch », qui a été résolue précédemment pour des paires spécifiques d'arbres (arbres hiérarchiques et arbres de type train track) par Buczyńska et al. [BBM15]. Les auteurs visent à établir un cadre général pour comparer des arbres binaires arbitraires, en faisant abstraction des plongements planaires, et à quantifier le « coût » de la contenance. Plus précisément, ils cherchent à déterminer de combien les paramètres de dimension (le « boost ») d'un réseau doivent être mis à l'échelle par rapport à un autre pour garantir la contenance.

Méthodologie
Les auteurs emploient une approche combinatoire ancrée dans la structure des arbres binaires racines complets et les propriétés de leurs états de réseaux de tenseurs (TNS) associés.

1. Définitions et Cadre :

   • Réseaux de Tenseurs : Définis comme un triplet $(T, \mathcal{V}, f)$, où $T$ est un arbre binaire complet, $\mathcal{V}$ est une famille d'espaces vectoriels aux feuilles, et $f$ est un vecteur de dimension assignant des dimensions aux sous-espaces à chaque sommet.
   • Variétés : La variété $TNS(T)$ est le lieu des tenseurs satisfaisant des contraintes de rang à chaque sommet, défini via des sous-espaces linéaires $U_v$ tels que $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Description Extérieure : Les auteurs utilisent des contractions de tenseurs pour caractériser la variété via des conditions de rang sur les applications de « aplatissement » (flattening). Un tenseur appartient à $TNS(T)$ si le rang de sa contraction à travers toute coupure $(\downarrow v | \uparrow v)$ est borné par $f(v)$.
   • Ensembles DOAD : Un outil combinatoire crucial introduit est l'ensemble « doad » (descendant ou anti-descendant des feuilles), noté $DOAD(T)$. Ce sont des sous-ensembles de feuilles $S$ tels que $S = \downarrow v$ ou $S = \uparrow v$ pour un certain sommet $v$.

2. Critères de Contenance :

   • Contenance Triviale : Un réseau $T$ est trivialement contenu dans $T'$ si tout ensemble doad de $T'$ peut être couvert par des ensembles doad de $T$ de telle sorte que le produit des paramètres de dimension des ensembles de couverture dans $T$ soit inférieur ou égal au paramètre dans $T'$.
   • Contenance Asymptotique (Lemme 2.11) : Les auteurs établissent que si chaque ensemble doad (ou son complément) de $T'$ peut être couvert par au plus $c_0$ ensembles doad de $T$, alors pour un facteur d'échelle $r$ suffisamment grand, $TNS(rT) \subseteq TNS(r^{c_0}T')$. Cela conduit à la définition de l'exposant de contenance.

3. L'Exposant de Contenance :

   • Défini comme le plus petit nombre $E$ tel que pour tous vecteurs de dimension et pour $r$ suffisamment grand, $TNS(rT) \subseteq TNS(r^c T')$ soit vrai pour tout $c > E$.
   • Bornes Combinatoires : Les auteurs dérivent des bornes basées sur la structure de l'ordre partiel (poset) des arbres. Le Théorème 3.3 fournit une formule pour un exposant basé sur le nombre d'éléments maximaux dans des sous-posets spécifiques dérivés des structures d'arbres.
   • Arbres Planaires : Pour les arbres planaires (où les feuilles sont ordonnées), les auteurs exploitent le fait que les ensembles doad correspondent à des intervalles. Ils introduisent la « hauteur » et la « hauteur duale » des sommets pour dériver des bornes spécifiques pour la contenance par rapport à l'arbre train track ($TT_n$) et entre des arbres planaires arbitraires (Théorème 4.4, Corollaire 4.7).

4. Approche Computationnelle :

   • Les auteurs ont implémenté un algorithme pour calculer ces exposants pour de petits nombres de feuilles ($n \le 8$).
   • Ils ont utilisé le package SageMath BinaryTree pour générer tous les arbres binaires complets.
   • Pour des $n$ plus grands, là où la recherche exhaustive de couvertures d'ensembles doad devient infaisable, ils ont formulé un programme linéaire en nombres entiers (ILP) pour minimiser le nombre d'ensembles doad requis pour couvrir les coupures de l'arbre cible.

Contributions Clés et Résultats

• Généralisation de la Conjecture de Hackbusch : L'article étend l'analyse de la contenance des paires spécifiques d'arbres (hiérarchique vs train track) à n'importe quelle paire d'arbres binaires.
• Existence et Définition des Exposants de Contenance : Les auteurs prouvent l'existence d'un exposant de contenance fini pour toute paire d'arbres et le définissent comme une mesure de la mise à l'échelle des paramètres requise pour la contenance.
• Bornes Combinatoires :
  • Une borne supérieure générale de $\lfloor n/2 \rfloor$ est fournie (Proposition 3.2).
  • Une borne plus serrée basée sur la structure de l'ordre partiel des arbres est présentée dans le Théorème 3.3.
  • Des bornes spécifiques pour les arbres planaires sont dérivées en utilisant les hauteurs des sommets, montrant que l'exposant d'un arbre $T$ dans l'arbre train track $TT_n$ est lié au maximum de $\min\{h_\ell, h^*_{\ell+1}\}$ (Corollaire 4.5).
• Implémentation Algorithmique : Les auteurs fournissent un algorithme et une formulation ILP pour calculer ces exposants. Ils font état d'une recherche exhaustive pour des arbres allant jusqu'à $n=8$ feuilles, avec des résultats détaillés collectés dans un ensemble de données distinct [GM25].
• Non-Serrage des Bornes : L'article démontre, par des exemples (par exemple, Figure 6), que les bornes combinatoires dérivées ne sont pas nécessairement serrées. Dans certains cas, l'exposant de contenance réel est nettement inférieur à la borne supérieure théorique fournie par les formules de l'ordre partiel ou de la hauteur.

Signification et Revendications
Les auteurs positionnent ce travail comme une « première étape » vers une meilleure compréhension des contenances de réseaux de tenseurs. Ils affirment avoir :

1. Proposé un cadre général pour la question de la contenance qui s'applique à des arbres binaires de formes arbitraires.
2. Introduit une nouvelle mesure, l'exposant de contenance, qui quantifie la relation entre différents formats de réseaux de tenseurs.
3. Fourni à la fois des bornes théoriques (via des structures d'ordre partiel et de la programmation entière) et des données expérimentales pour de petits $n$.

L'article conclut avec modestie, notant que bien que les bornes soient utiles, elles ne sont pas toujours serrées. Les auteurs identifient des questions ouvertes concernant la possibilité que les bornes supérieures du Lemme 2.11 soient toujours serrées et si les solutions duales de la relaxation linéaire peuvent être utilisées pour construire des tenseurs qui donnent des bornes inférieures pour les exposants. Ils suggèrent que l'exposant de contenance offre une nouvelle mesure de distance non symétrique pour les arbres, méritant une comparaison avec les métriques d'arbres existantes dans la littérature.