Algebraic Operations on Tensor Trains

Sintesi Tecnica: Operazioni Algebriche su Tensor Train

Definizione del Problema
I tensori ad alta dimensionalità compaiono frequentemente in applicazioni quali la chimica quantistica, l'identificazione di sistemi e la programmazione dinamica. La crescita esponenziale degli elementi del tensore rispetto alla dimensione (la "maledizione della dimensionalità") rende impraticabile la memorizzazione e la manipolazione di tensori completi. Il formato Tensor Train (TT), noto anche come Matrix Product State (MPS), affronta questo problema rappresentando i tensori come una sequenza di nuclei a basso rango (wagon) con dimensioni di legame (bond dimensions) gestibili.

Tuttavia, eseguire operazioni algebriche su tensori già in formato TT presenta sfide significative. Nello specifico:

1. Sommazione: L'aggiunta di più TT (ad esempio, una Somma di Tensor Train o SOTT) spesso produce un singolo TT con dimensioni di legame eccessivamente grandi se convertito ingenuamente.
2. Prodotto di Hadamard: Il prodotto elemento per elemento di due TT produce teoricamente una dimensione di legame pari al prodotto delle singole dimensioni di legame ($B_{prod} = B_1 B_2$). Per grandi dimensioni di legame (ad esempio, $B=1000$), i wagon intermedi diventano troppo grandi per essere memorizzati ($10^6$ elementi per core, portando a $10^{12}$ elementi totali).
3. Prodotto Matrice-Vettore: Il calcolo di $y = Hx$, dove l'operatore $H$ (Matrix Product Operator, MPO) e il vettore $x$ (MPS) sono in formato TT, porta similmente a una massiccia espansione delle dimensioni di legame.

I metodi esistenti per il "tensor rounding" (riduzione delle dimensioni di legame) affrontano spesso un compromesso: gli algoritmi tradizionali (come il TT-SVD) offrono un'alta accuratezza ma sono computazionalmente costosi, mentre i metodi più veloci basati su prodotti casuali o sul prodotto di Khatri-Rao (KRP) spesso soffrono di una ridotta accuratezza in scenari lossy (con perdita di informazione).

Metodologia
Il documento propone una variante generalizzata e migliorata dell'algoritmo TTSVDTT (SVD applicata al TT per il Tensor Train). La metodologia centrale si basa sull'evitare la costruzione esplicita di grandi tensori intermedi. Invece, opera sui prodotti di questi tensori utilizzando decomposizioni matriciali.

1. Strangolazione e SVD: L'approccio utilizza la "strangolazione", in cui un tensore viene rimodellato in una matrice e decomposto tramite Singolar Value Decomposition (SVD) per troncare la dimensione di legame.
2. Operazioni Matriciali Implicite: Per l'algoritmo TTSVDTT, invece di formare la grande matrice $X_n$ (che conterrebbe i pieni prodotti dei wagon del tensore), l'algoritmo calcola il prodotto $X_n X_n^T$ implicitamente. Deriva i vettori singolari sinistri di $X_n$ come autovettori di $X_n X_n^T$.
3. Decomposizione di Cholesky e SVD Troncata: Un'innovazione chiave consiste nel decomporre la matrice $M_n = X_n X_n^T$ come $S_n S_n^T$ (ad esempio, tramite decomposizione di Cholesky). L'algoritmo calcola poi il wagon desiderato $y_n$ eseguendo una SVD troncata su un tensore ausiliario più piccolo $Y_n$ (derivato da $z_n$ e $S_n$) piuttosto che su $X_n$ completo.
4. Varianti Specializzate: Il documento estende questo framework a tre specifici formati di input senza formare esplicitamente il prodotto completo:
   • SOTT (Somma di TT): Per una somma di $M$ treni, l'algoritmo sfrutta la struttura diagonale a blocchi dei wagon combinati, memorizzando solo i blocchi diagonali per evitare la complessità di memoria $O(M^2)$.
   • Prodotto di Hadamard (TTSVDHP): Per il prodotto elemento per elemento di due TT, l'algoritmo evita il prodotto di Kronecker dei pieni wagon. Utilizza l'identità $\text{vec}(ABC) = (C^T \otimes A)\text{vec}(B)$ per calcolare i prodotti con la grande struttura di Kronecker moltiplicando separatamente con le matrici costituenti più piccole ($f_n$ e $g_n$).
   • Prodotto MPO-MPS (TTSVDHX): Per il prodotto $y=Hx$, l'algoritmo calcola tensori ausiliari ($z_n, V_n, Y_n$) che sono significativamente più piccoli del pieno prodotto dei wagon, permettendo una trancatura efficiente.

Contributi Chiave

1. TTSVDTT Generalizzato: Il documento presenta una generalizzazione dell'algoritmo TTSVDTT capace di gestire input che non sono singoli TT, ma piuttosto somme di TT, prodotti di Hadamard o prodotti MPO-MPS.
2. Efficienza della Memoria: Gli algoritmi proposti (TTSVDHP e TTSVDHX) consentono l'arrotondamento (rounding) dei prodotti tensoriali senza mai valutare il prodotto tensoriale completo o memorizzare i massicci array intermedi che risulterebbero da un'espansione ingenua.
3. Compromesso Accuratezza-Velocità: Il documento introduce un'alternativa alla "Successive Randomized Compression" (SRC) e ai metodi di rounding basati su KRP: mentre i metodi randomizzati sono più veloci, le varianti TTSVDTT proposte offrono un migliore compromesso tra efficienza computazionale e accuratezza, specialmente nei casi di rounding lossy dove la precisione è critica.
4. Conversione da CPD a TT: La metodologia consente la conversione di tensori dal formato Canonical Polyadic Decomposition (CPD) al formato TT (e viceversa) senza valutare tutti gli elementi del tensore, trattando il CPD come un caso speciale di SOTT con dimensione di legame 1.

Risultati
Esperimenti numerici sono stati condotti su dati sintetici e problemi reali di chimica quantistica:

• SOTT/CPD: Nel convertire un modello CP (rango 1000) in TT, l'algoritmo specializzato TTSVDCP è stato competitivo in velocità con i metodi più rapidi pur mantenendo l'alta accuratezza del tradizionale TT rounding.
• Prodotto di Hadamard: In esperimenti riguardanti il prodotto elemento per elemento di due TT (dimensione di legamento 20), l'algoritmo proposto TTSVDHP ha ottenuto errori di fitting comparabili a TTSVDTT e al rounding tradizionale, ma è stato significativamente più veloce del rounding tradizionale. Ha gestito con successo dimensioni più elevate in cui altri metodi fallivano a causa dei vincoli di memoria.
• Prodotto MPO-MPS: Nel calcolo di $y=Hx$, l'algoritmo TTSVDHX ha dimostrato un'accuratezza quasi identica al tradizionale TT rounding e al TTSVDTT, superando i metodi SRC e KRP in termini di accuratezza. La sua complessità computazionale è cresciuta a un tasso inferiore rispetto ai metodi tradizionali all'aumentare delle dimensioni di legamento.
• Applicazione in Chimica Quantistica: Gli algoritmi sono stati applicati per minimizzare la forma quadratica di un Hamiltoniano (trovare l'energia dello stato fondamentale) per molecole aromatiche cicliche (benzene, [10]annulene, [18]annulene). L'algoritmo TTSVDHX ha calcolato con successo energie minime che sono state confermate dall'algoritmo Density Matrix Renormalization Group (DMRG), dimostrando la sua praticità.

Significato e Rivendicazioni
Il documento afferma che gli algoritmi proposti raggiungono un miglior compromesso tra efficienza computazionale e accuratezza rispetto ai metodi allo stato dell'arte. Nello specifico:

• A differenza degli algoritmi randomizzati o basati su KRP, che possono essere fino a 50 volte più veloci ma meno accurati in scenari lossy, le varianti TTSVDTT proposte mantengono l'alta accuratezza dell'approccio originale TT-SVD offrendo al contempo miglioramenti di velocità.
• Gli algoritmi risolvono il problema del "collo di bottiglia della memoria" inerente all'algebra tensoriale (somme, prodotti di Hadamard e prodotti matrice-vettore) operando su rappresentazioni compresse senza espansione esplicita.
• Il lavoro fornisce uno strumento robusto per applicazioni ad alta dimensionalità, in particolare nella chimica quantistica, consentendo la soluzione di problemi di ottimizzazione quadratica vincolata (problemi di autovalori) per grandi Hamiltoniani che sarebbero altrimenti intrattabili a causa dei limiti di memoria.