Convergence Analysis of Two Alternating Iterative Schemes for Tucker Decomposition

Sintesi Tecnica: Analisi di Convergenza di Due Schemi Iterativi Alternanti per la Decomposizione di Tucker

Enunciato del Problema
Il lavoro affronta il calcolo della decomposizione di Tucker (TD) per un tensore a $m$ modi $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$. L'obiettivo è trovare matrici fattoriali ortonormali $P_\ell \in \text{St}(k_\ell, n_\ell)$ (dove $\text{St}$ denota la varietà di Stiefel complessa) e un tensore core $\mathcal{T}$ tali che l'errore di approssimazione $\|\mathcal{B} - \mathcal{T} \times_1 P_1 \times_2 P_2 \dots \times_m P_m\|_F$ sia minimizzato. Ciò è equivalente alla massimizzazione della funzione obiettivo $f(P_1, \dots, P_m) = \|\mathcal{B} \times_1 P_1^H \times_2 P_2^H \dots \times_m P_m^H\|_F^2$.

Sebbene esistano due popolari schemi iterativi alternanti per questo problema — l'Iterazione Ortogonale di Ordine Superiore (HOOI) e l'Iterazione di Sottospazio Alternante (ASI) — le loro proprietà di convergenza teorica erano precedentemente incomplete. Nello specifico, l'analisi dell'ASI condotta da Kroonenberg e De Leeuw (1980) presentava lacune tecniche, e l'analisi di una variante "greedy" dell'HOOI effettuata da Xu (2018) era limitata a tensori reali e si basava sulla teoria avanzata delle funzioni semi-algebriche (Kurdyka–Lojasiewicz), meno familiare alla comunità dell'algebra lineare numerica.

Metodologia
Gli autori riformulano la minimizzazione dell'errore di approssimazione come un problema di massimizzazione che coinvolge $m$ equazioni matriciali non lineari accoppiate. Queste equazioni sono interpretate in due modi:

1. Come un sistema di Problemi di Autovalori Non Lineari accoppiati con dipendenza dagli autovettori (NEPv).
2. Come un sistema di Decomposizioni Polari Non Lineari accoppiate con dipendenza dal fattore polare ortonormale (NPDo).

Il lavoro analizza due algoritmi basati su queste formulazioni:

• HOOI (Algoritmo 4.1): Uno schema di tipo Gauss-Seidel in cui, ad ogni passo, $P_\ell$ viene aggiornata per essere la matrice dei primi $k_\ell$ autovettori a sinistra di un tensore specifico srotolato (o, equivalentemente, dei primi $k_\ell$ autovettori di una matrice hermitiana $H_\ell$).
• ASI (Algoritmo 5.1): Uno schema di tipo Gauss-Seidel in cui $P_\ell$ viene aggiornata tramite un'iterazione di sottospazio a un solo passo (nello specifico, il fattore polare ortonormale di $H_\ell P_\ell$), anziché risolvere il completo problema agli autovalori.

L'analisi di convergenza si avvale di strumenti dell'algebra lineare numerica, inclusi gli angoli canonici tra sottospazi, i limiti di errore per le approssimazioni di autovalori/singolari estremi tramite tracce di matrici e le proprietà della varietà di Grassmann. L'analisi è condotta per tensori complessi, con i tensori reali trattati come caso particolare.

Contributi Chiave

1. Dimostrazioni Rigorose di Convergenza: Il lavoro fornisce analisi dettagliate di convergenza sia per HOOI che per ASI. Dimostra che, sotto condizioni lievi, entrambi i metodi generano sequenze in cui la funzione obiettivo aumenta monotonicamente e converge.
2. Convergenza Globale a Punti Stazionari: Gli autori dimostrano che entrambi gli algoritmi convergono globalmente a punti stazionari che soddisfano le condizioni di Karush-Kuhn-Tucker (KKT).
   • Per HOOI, i punti limite soddisfano un sistema di equazioni NEPv accoppiate in cui gli autovalori corrispondono ai maggiori autovalori delle matrici hermitiane associate.
   • Per ASI, i punti limite soddisfano un sistema di equazioni NPDo accoppiate.
3. Gestione della Non-Univocità: L'analisi affronta la non-univocità intrinseca della decomposizione di Tucker (dovuta all'invarianza unitaria). Gli autori mostrano che, sebbene la sequenza di matrici possa non convergere elemento per elemento senza allineamento, la sequenza di sottospazi converge e la funzione obiettivo converge.
4. Generalizzazione ai Tensori Complessi: A differenza di lavori precedenti limitati a tensori reali, questa analisi si applica a tensori complessi, ampliando la portata delle garanzie di convergenza.
5. Chiarificazione dell'Allineamento "Greedy": Il lavoro sostiene che il passo di "allineamento" (regolazione della fase/orientazione di $P_\ell$ ad ogni iterazione per corrispondere al passo precedente), proposto da Xu per l'HOOI greedy, è numericamente non necessario per la qualità dell'approssimazione finale, sebbene possa essere utile per le dimostrazioni teoriche di convergenza.

Risultati

• Risultati Teorici:
  • Monotonia: Entrambi gli algoritmi producono una sequenza di valori obiettivo che aumenta monotonicamente.
  • Stazionarietà: I punti di accumulazione delle sequenze generate soddisfano le condizioni KKT.
  • Tassi di Convergenza: Il lavoro stabilisce che la somma delle distanze quadrate tra iterati consecutivi (pesata dai gap di autovalori o dai valori singolari) è finita, implicando che gli iterati si avvicinano a un punto stazionario.
  • Convergenza Globale: Se il punto stazionario è isolato e sono soddisfatte certe condizioni di gap spettrale (per HOOI) o condizioni di rango completo (per ASI), l'intera sequenza converge a quel punto.
• Esperimenti Numerici:
  • Gli esperimenti sono stati condotti su un "Tensore di Simulazione Scientifica Miranda" e su tensori generati casualmente (sia reali che complessi).
  • HOOI vs ASI: HOOI ha richiesto costantemente meno iterazioni per convergere rispetto ad ASI perché calcola il sottospazio ottimale ad ogni passo, mentre ASI esegue solo un singolo passo di iterazione di potenza.
  • Inizializzazione: L'uso di una HOSVD troncata come ipotesi iniziale ha generalmente ridotto il numero di iterazioni, sebbene non universalmente (in alcuni casi, l'inizializzazione casuale ha converguto più velocemente).
  • Complessità: Sebbene HOOI converga in meno iterazioni, il costo computazionale per iterazione è superiore rispetto ad ASI. Tuttavia, gli autori hanno osservato che il tempo totale di CPU per entrambi i metodi è stato competitivo, poiché i risparmi nel numero di iterazioni per HOOI hanno bilanciato il costo per passo più elevato.
  • Criteri di Arresto: Gli esperimenti hanno evidenziato il rischio di "falsa convergenza", dove la funzione obiettivo si stabilizza temporaneamente prima di risalire, suggerendo che i criteri di arresto basati sul residuo sono più robusti di quelli basati sul valore dell'obiettivo.

Significato e Affermazioni
Il lavoro afferma di fornire un'analisi di convergenza più accessibile e autosufficiente per gli algoritmi di decomposizione di Tucker rispetto ai lavori precedenti. Basandosi interamente su concetti di algebra lineare numerica piuttosto che sulla geometria semi-algebrica, i risultati sono intesi per essere più accessibili alla comunità dell'algebra lineare numerica. Gli autori sottolineano che la loro analisi copre sia tensori reali che complessi e corregge le lacune nell'analisi storica dell'ASI. Concludono che, sebbene HOOI sia teoricamente superiore in termini di numero di iterazioni, entrambi i metodi sono globalmente convergenti ed efficaci per il calcolo delle decomposizioni di Tucker, con la scelta tra di essi che potrebbe dipendere dal compromesso specifico tra numero di iterazioni e costo computazionale per iterazione.