Containments of Tensor Network Varieties

Technische Samenvatting: Insluitingen van Tensor Netwerk Variëteiten

Probleemstelling
Het artikel behandelt de fundamentele vraag naar inclusie tussen tensor netwerk variëteiten. Gegeven twee tensorformaten die zijn gecodeerd door binaire bomen, onderzoeken de auteurs of de verzameling van alle tensoren die door één netwerk representeerbaar zijn (de variëteit) ingesloten is in de verzameling die door een ander representeerbaar is. Dit probleem generaliseert de "Hackbusch Conjectuur", die voor specifieke paren bomen (hiërarchische en train track bomen) eerder werd opgelost door Buczyńska et al. [BBM15]. De auteurs streven naar een algemeen kader om willekeurige binaire bomen te vergelijken, waarbij zij de planaire inbeddingen negeren, en om de "kosten" van inclusie te kwantificeren. Specifiek beogen zij te bepalen hoeveel de dimensieparameters (de "boost") van het ene netwerk moeten worden geschaald ten opzichte van het andere om inclusie te waarborgen.

Methodologie
De auteurs hanteren een combinatorische benadering die geworteld is in de structuur van volledige binaire gewortelde bomen en de eigenschappen van de daarmee geassocieerde tensor netwerk toestanden (TNS).

1. Definities en Kader:

   • Tensor Netwerken: Gedefinieerd als een driedubbel $(T, \mathcal{V}, f)$, waarbij $T$ een volledige binaire boom is, $\mathcal{V}$ een familie van vectorruimten bij de bladeren, en $f$ een dimensievector die dimensies toewijst aan deelruimten bij elk knooppunt.
   • Variëteiten: De TNS-variëteit $TNS(T)$ is de locus van tensoren die voldoen aan rangbeperkingen bij elk knooppunt, gedefinieerd via lineaire deelruimten $U_v$ zodanig dat $U_v \subseteq U_{v_1} \otimes U_{v_2}$.
   • Uiterlijke Beschrijving: De auteurs maken gebruik van tensorcontracties om de variëteit te karakteriseren via rangvoorwaarden op "flattening" afbeeldingen. Een tensor behoort tot $TNS(T)$ indien de rang van de contractie over elke split $(\downarrow v | \uparrow v)$ begrensd wordt door $f(v)$.
   • Doad Sets: Een cruciaal combinatorisch instrument dat wordt geïntroduceerd is het "doad set" (afstammeling of anti-afstammeling bladeren), aangeduid met $DOAD(T)$. Dit zijn deelverzamelingen van bladeren $S$ zodanig dat $S = \downarrow v$ of $S = \uparrow v$ voor een bepaald knooppunt $v$.

2. Inclusiecriteria:

   • Triviale Inclusie: Een netwerk $T$ is triviaal ingesloten in $T'$ indien elke doad set van $T'$ gedekt kan worden door doad sets van $T$ zodanig dat het product van de dimensieparameters van de dekkende verzamelingen in $T$ kleiner dan of gelijk is aan de parameter in $T'$.
   • Asymptotische Inclusie (Lemma 2.11): De auteurs stellen vast dat indien elke doad set (of het complement daarvan) van $T'$ gedekt kan worden door maximaal $c_0$ doad sets van $T$, dan voor een voldoende grote schalfactor $r$, $TNS(rT) \subseteq TNS(r^{c_0}T')$ geldt. Dit leidt tot de definitie van de inclusie-exponent.

3. De Inclusie-exponent:

   • Gedefinieerd als het kleinste getal $E$ waarvoor voor alle dimensievectoren en voor voldoende grote $r$, $TNS(rT) \subseteq TNS(r^c T')$ geldt voor alle $c > E$.
   • Combinatorische Grenzen: De auteurs leiden grenzen af op basis van de poset-structuur van de bomen. Theorem 3.3 biedt een formule voor een exponent gebaseerd op het aantal maximale elementen in specifieke sub-posets afgeleid van de boomstructuren.
   • Plane Trees: Voor plane bomen (waarbij de bladeren geordend zijn) maken de auteurs gebruik van het feit dat doad sets overeenkomen met intervallen. Zij introduceren "hoogte" en "duale hoogte" van knooppunten om specifieke grenzen af te leiden voor inclusie ten opzichte van de train track boom ($TT_n$) en tussen willekeurige plane bomen (Theorem 4.4, Corollary 4.7).

4. Computationele Benadering:

   • De auteurs hebben een algoritme geïmplementeerd om deze exponenten te berekenen voor een klein aantal bladeren ($n \le 8$).
   • Zij maakten gebruik van de SageMath package BinaryTree om alle volledige binaire bomen te genereren.
   • Voor grotere $n$, waar een uitputtende zoektocht naar doad set dekkingen onhaalbaar wordt, hebben zij een Integer Linear Program (ILP) geformuleerd om het aantal doad sets te minimaliseren dat vereist is om de splits van de doelboom te dekken.

Belangrijkste Bijdragen en Resultaten

• Generalisering van de Hackbusch Conjectuur: Het artikel breidt de inclusie-analyse uit van specifieke boomparen (hiërarchisch versus train track) naar elk paar binaire bomen.
• Bestaan en Definitie van Inclusie-exponenten: De auteurs bewijzen het bestaan van een eindige inclusie-exponent voor elk paar bomen en definiëren deze als een maatstaf voor de parameter-schaling die vereist is voor inclusie.
• Combinatorische Grenzen:
  • Een algemene bovengrens van $\lfloor n/2 \rfloor$ wordt geboden (Proposition 3.2).
  • Een nauwere grens gebaseerd op de poset-structuur van de bomen wordt gepresenteerd in Theorem 3.3.
  • Specifieke grenzen voor plane bomen zijn afgeleid met behulp van vertex-hoogtes, waarbij wordt aangetoond dat de exponent voor een boom $T$ in de train track boom $TT_n$ gerelateerd is aan het maximum van $\min\{h_\ell, h^*_{\ell+1}\}$ (Corollary 4.5).
• Algoritmische Implementatie: De auteurs bieden een algoritme en een ILP-formulering om deze exponenten te berekenen. Zij rapporteren over een uitputtende zoektocht voor bomen met tot $n=8$ bladeren, met gedetailleerde resultaten verzameld in een aparte dataset [GM25].
• Niet-scherpte van Grenzen: Het artikel toont via voorbeelden (bijv. Figuur 6) aan dat de afgeleide combinatorische grenzen niet noodzakelijkerwijs scherp zijn. In sommige gevallen is de werkelijke inclusie-exponent aanzienlijk lager dan de theoretische bovengrens die door de poset of hoogte-gebaseerde formules wordt gegeven.

Significantie en Claims
De auteurs positioneren dit werk als een "eerste stap" naar een beter begrip van tensor netwerk inclusies. Zij claimen dat zij:

1. Een algemeen kader hebben voorgesteld voor de inclusievraag die van toepassing is op willekeurig gevormde binaire bomen.
2. Een nieuwe maatstaf hebben geïntroduceerd, de inclusie-exponent, die de relatie tussen verschillende tensor netwerk formaten kwantificeert.
3. Zowel theoretische grenzen (via poset-structuren en integer programmeren) als experimentele data voor kleine $n$ hebben geleverd.

Het artikel sluit bescheiden af met de opmerking dat hoewel de grenzen nuttig zijn, ze niet altijd nauw aansluiten. De auteurs identificeren open vragen over de vraag of de bovengrenzen uit Lemma 2.11 altijd scherp zijn en of duale oplossingen van de lineaire programmering-relaxatie gebruikt kunnen worden om tensoren te construeren die lagere grenzen voor de exponenten opleveren. Zij suggereren dat de inclusie-exponent een nieuwe, niet-symmetrische afstandsmeter voor bomen biedt, wat verdere vergelijking met bestaande boommetrieken in de literatuur rechtvaardigt.