Algebraic Operations on Tensor Trains

Technische Samenvatting: Algebraïsche Operaties op Tensor Trains

Probleemstelling
Hoogdimensionale tensoren komen frequent voor in toepassingen zoals kwantumchemie, systeemidentificatie en dynamische programmering. De exponentiële groei van de aantal tensor-elementen ten opzichte van de dimensie (de "vloek van dimensionaliteit") maakt het opslaan en manipuleren van volledige tensoren onpraktisch. Het Tensor Train (TT) formaat, ook bekend als Matrix Product State (MPS), lost dit op door tensoren weer te geven als een reeks laag-rang kernen (wagons) met beheersbare verbondingsdimensies (bond dimensions).

Het uitvoeren van algebraïsche operaties op tensoren die al in TT-formaat staan, brengt echter aanzienlijke uitdagingen met zich mee. Specifiek:

1. Sommatie: Het optellen van meerdere TT's (bijvoorbeeld een Sum of Tensor Trains of SOTT) resulteert vaak in een enkele TT met excessief grote verbondingsdimensies als dit naïef wordt omgezet.
2. Hadamard-product: Het elementgewijze product van twee TT's resulteert theoretisch in een verbondingsdimensie gelijk aan het product van de individuele verbondingsdimensies ($B_{prod} = B_1 B_2$). Voor grote verbondingsdimensies (bijv. $B=1000$), worden de tussenliggende wagons te groot om op te slaan ($10^6$ elementen per kern, wat leidt tot $10^{12}$ totale elementen).
3. Matrix-vector product: Het berekenen van $y = Hx$, waarbij zowel de operator $H$ (Matrix Product Operator, MPO) als de vector $x$ (MPS) in TT-formaat staan, leidt eveneens tot een enorme expansie van de verbondingsdimensies.

Bestaande methoden voor "tensor rounding" (het reduceren van de verbondingsdimensie) kampen vaak met een afweging: traditionele algoritmen (zoals TT-SVD) bieden een hoge nauwkeurigheid maar zijn computationeel duur, terwijl snellere gerandomiseerde of op Khatri-Rao producten (KRP) gebaseerde methoden vaak kampen met verminderde nauwkeurigheid in verlieslatende (lossy) scenario's.

Methodologie
Het artikel stelt een gegeneraliseerde en verbeterde variant voor van het TTSVDTT-algoritme (Tensor Train SVD toegepast op TT). De kernmethodologie berust op het vermijden van de expliciete constructie van grote tussenliggende tensoren. In plaats daarvan opereert het op de producten van deze tensoren met behulp van matrixontbindingen.

1. Strangulatie en SVD: De aanpak maakt gebruik van "strangulatie", waarbij een tensor wordt omgevormd tot een matrix en wordt ontbonden via Singular Value Decomposition (SVD) om de verbondingsdimensie te inkorten.
2. Impliciete Matrixoperaties: Voor het TTSVDTT-algoritme, in plaats van de grote matrix $X_n$ expliciet te vormen (die de volledige product-tensor wagons zou bevatten), berekent het algoritme het product $X_n X_n^T$ impliciet. Het afleidt de linker singuliere vectoren van $X_n$ als eigenvectoren van $X_n X_n^T$.
3. Cholesky-ontbinding en Afgekorte SVD: Een belangrijke innovatie is het ontbinden van de matrix $M_n = X_n X_n^T$ als $S_n S_n^T$ (bijvoorbeeld via Cholesky-ontbinding). Het algoritme berekent vervolgens de gewenste wagon $y_n$ door een afgekorte SVD uit te voeren op een kleinere hulp-tensor $Y_n$ (afgeleid van $z_n$ en $S_n$), in plaats van op de volledige $X_n$.
4. Gespecialiseerde Varianten: Het artikel breidt dit kader uit naar drie specifieke inputformaten zonder de volledige product-tensor expliciet te vormen:
   • SOTT (Sum of TTs): Voor een som van $M$ treinen maakt het algoritme gebruik van de blokdiagonaal structuur van de gecombineerde wagons, waarbij alleen de diagonale blokken worden opgeslagen om een geheugencomplexiteit van $O(M^2)$ te vermijden.
   • Hadamard-product (TTSVDHP): Voor het elementgewijze product van twee TT's vermijdt het algoritme de Kronecker-product van de volledige wagons. Het maakt gebruik van de identiteit $\text{vec}(ABC) = (C^T \otimes A)\text{vec}(B)$ om producten met de grote Kronecker-structuur te berekenen door met de kleinere constituerende matrices ($f_n$ en $g_n$) apart te vermenigvuldigen.
   • MPO-MPS Product (TTSVDHX): Voor het product $y=Hx$ berekent het algoritme hulp-tensoren ($z_n, V_n, Y_n$) die aanzienlijk kleiner zijn dan de volledige product-wagons, wat efficiënte inkorting mogelijk maakt.

Belangrijkste Bijdragen

1. Gegeneraliseerde TTSVDTT: Het artikel presenteert een generalisatie van het TTSVDTT-algoritme dat in staat is om inputs te verwerken die niet slechts enkele TT's zijn, maar sommen van TT's, Hadamard-producten van TT's, of MPO-MPS producten.
2. Geheugenefficiëntie: De voorgestelde algoritmen (TTSVDHP en TTSVDHX) maken het mogelijk om de producten van tensoren af te ronden zonder ooit de volledige product-tensor te evalueren of de enorme tussenliggende arrays op te slaan die zouden resulteren bij een naïeve expansie.
3. Nauwkeurigheid-Snelheid Afweging: Het artikel introduceert een alternatief voor de "Successive Randomized Compression" (SRC) en KRP-gebaseerde rounding-methoden. Hoewel gerandomiseerde methoden sneller zijn, biedt de voorgestelde TTSVDTT-varianten een betere balans tussen computationele efficiëntie en nauwkeurigheid, vooral in verlieslatende scenario's waar precisie cruciaal is.
4. CPD naar TT Conversie: De methodologie maakt de conversie van tensoren van Canonical Polyadic Decomposition (CPD) formaat naar TT-formaat (en vice versa) mogelijk zonder alle tensor-elementen te evalueren, door CPD te behandelen als een speciaal geval van SOTT met een verbondingsdimensie van 1.

Resultaten
Numerieke experimenten werden uitgevoerd op synthetische data en reële kwantumchemische problemen:

• SOTT/CPD: Bij het converteren van een CP-model (rang 1000) naar TT, was het gespecialiseerde TTSVDCP-algoritme concurrerend in snelheid met de snelste methoden, terwijl het de hoge nauwkeurigheid van traditionele TT-rounding behield.
• Hadamard-product: In experimenten met het elementgewijze product van twee TT's (verbondingsdimensie 20), bereikte het voorgestelde TTSVDHP-algoritme aanpassingsfouten vergelijkbaar met TTSVDTT en traditionele rounding, maar was het aanzienlijk sneller dan traditionele rounding. Het handelde succesvol hogere dimensies af waar andere methoden faalden vanwege geheugenbeperkingen.
• MPO-MPS Product: Bij het berekenen van $y=Hx$ vertoonde het TTSVDHX-algoritme een bijna identieke nauwkeurigheid als traditionele TT-rounding en TTSVDTT, en presteerde het beter dan de SRC- en KRP-methoden op het gebied van nauwkeurigheid. De computationele complexiteit groeide met een lagere snelheid bij toenemende verbondingsdimensies vergeleken met traditionele methoden.
• Toepassing in Kwantumchemie: De algoritmen werden toegepast op het minimaliseren van de kwadratische vorm van een Hamiltoniaan (het vinden van de grondtoestandsenergie) voor cyclische aromatische moleculen (benzeen, [10]annuleen, [18]annuleen). Het TTSVDHX-algoritme berekende succesvol minimale energieën die werden bevestigd door het Density Matrix Renormalization Group (DMRG) algoritme, wat de praktische levensvatbaarheid aantoont.

Betekenis en Claims
Het artikel claimt dat de voorgestelde algoritmen een verbeterde afweging bereiken tussen computationele efficiëntie en nauwkeurigheid vergeleken met de huidige stand van de techniek. Specifiek:

• In tegenstelling tot gerandomiseerde of KRP-gebaseerde algoritmen, die tot wel 50× sneller kunnen zijn maar minder nauwkeurig in verlieslatende scenario's, behouden de voorgestelde TTSVDTT-varianten de hoge nauwkeurigheid van de oorspronkelijke TT-SVD aanpak terwijl ze verbeteringen in snelheid bieden.
• De algoritmen lossen het "geheugenbottleneck"-probleem op dat inherent is aan tensoralgebra (sommen, Hadamard-producten en matrix-vector producten) door te opereren op gecomprimeerde representaties zonder expliciete expansie.
• Het werk levert een robuust instrument voor hoogdimensionale toepassingen, met name in de kwantumchemie, waardoor het oplossen van beperkte kwadratische optimalisatieproblemen (eigenwaardeproblemen) voor grote Hamiltoniaans mogelijk wordt gemaakt die anders onuitvoerbaar zouden zijn vanwege geheugenbeperkingen.