Convergence Analysis of Two Alternating Iterative Schemes for Tucker Decomposition

Technische Samenvatting: Convergentieanalyse van Twee Alternerende Iteratieve Schema's voor Tucker-decompositie

Probleemstelling
Het artikel behandelt de berekening van de Tucker-decompositie (TD) voor een $m$-modale tensor $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$. Het doel is om orthonormale factor matrices $P_\ell \in \text{St}(k_\ell, n_\ell)$ (waarbij $\text{St}$ de complexe Stiefel-maandruimte aanduidt) en een kern tensor $\mathcal{T}$ te vinden zodat de benaderingsfout $\|\mathcal{B} - \mathcal{T} \times_1 P_1 \times_2 P_2 \dots \times_m P_m\|_F$ wordt geminimaliseerd. Dit is equivalent aan het maximaliseren van de doelfunctie $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$.

Hoewel er twee populaire alternerende iteratieve schema's bestaan voor dit probleem—de Higher-Order Orthogonal Iteration (HOOI) en de Alternating Subspace Iteration (ASI)—waren hun theoretische convergentie-eigenschappen eerder onvolledig. Specifiek bevatte de analyse van ASI door Kroonenberg en De Leeuw (1980) technische hiaten, en was de analyse van een "gierige" HOOI-variant door Xu (2018) beperkt tot reële tensoren en leunde op geavanceerde semi-algebraïsche functietheorie (Kurdyka–Lojasiewicz), die minder bekend is bij de gemeenschap voor numerieke lineaire algebra.

Methodologie
De auteurs herformuleren de minimalisatie van de benaderingsfout als een maximalisatieprobleem dat $m$ gekoppelde niet-lineaire matrixvergelijkingen omvat. Deze vergelijkingen worden op twee manieren geïnterpreteerd:

1. Als een systeem van gekoppelde Niet-lineaire Eigenwaardeproblemen met eigenvector-afhankelijkheid (NEPv).
2. Als een systeem van gekoppelde Niet-lineaire Polaire Decomposities met orthonormale polaire factor-afhankelijkheid (NPDo).

Het artikel analyseert twee algoritmen gebaseerd op deze formuleringen:

• HOOI (Algoritme 4.1): Een Gauss-Seidel-type schema waarbij, bij elke stap, $P_\ell$ wordt bijgewerkt tot de matrix van de top $k_\ell$ linker singuliere vectoren van een specifieke ontvouwen tensor (of equivalent, de top $k_\ell$ eigenvectoren van een Hermitische matrix $H_\ell$).
• ASI (Algoritme 5.1): Een Gauss-Seidel-type schema waarbij $P_\ell$ wordt bijgewerkt via een één-staps subruimte iteratie (specifiek, de orthonormale polaire factor van $H_\ell P_\ell$), in plaats van het volledige eigenwaardeprobleem op te lossen.

De convergentieanalyse maakt gebruik van instrumenten uit de numerieke lineaire algebra, waaronder canonieke hoeken tussen subruimten, foutgrenzen voor extreme eigenwaarde/singuliere waarde benaderingen via matrixsporen, en eigenschappen van de Grassmann-maandruimte. De analyse wordt uitgevoerd voor complexe tensoren, waarbij reële tensoren worden behandeld als een speciaal geval.

Belangrijkste Bijdragen

1. Rigoureuze Convergentiebewijzen: Het artikel biedt gedetailleerde convergentieanalyses voor zowel HOOI als ASI. Het bewijst dat onder lichte voorwaarden beide methoden sequenties genereren waarbij de doelfunctie monotoon toeneemt en convergeert.
2. Globale Convergentie naar Stationaire Punten: De auteurs demonstreren dat beide algoritmen globaal convergeren naar stationaire punten die voldoen aan de Karush-Kuhn-Tucker (KKT) voorwaarden.
   • Voor HOOI voldoen de limietpunten aan een systeem van gekoppelde NEPv-vergelijkingen waarbij de eigenwaarden corresponderen met de grootste eigenwaarden van de bijbehorende Hermitische matrices.
   • Voor ASI voldoen de limietpunten aan een systeem van gekoppelde NPDo-vergelijkingen.
3. Omgaan met Niet-Uniciteit: De analyse adresseert de inherente niet-uniciteit van de Tucker-decompositie (vanwege unitaire invariantie). De auteurs tonen aan dat hoewel de rij matrices niet per se puntsgewijs convergeert zonder uitlijning, de rij subruimten convergeert en de doelfunctie convergeert.
4. Generalisatie naar Complexe Tensoren: In tegenstelling tot eerdere werken die beperkt waren tot reële tensoren, is deze analyse van toepassing op complexe tensoren, waardoor de toepasbaarheid van de convergentiegaranties wordt verbreed.
5. Verduidelijking van "Gierige" Uitlijning: Het artikel betoogt dat de "uitlijning"-stap (het aanpassen van de fase/oriëntatie van $P_\ell$ bij elke iteratie om te matchen met de vorige stap), voorgesteld door Xu voor gierige HOOI, numeriek onnodig is voor de kwaliteit van de uiteindelijke benadering, hoewel het nuttig kan zijn voor theoretische convergentiebewijzen.

Resultaten

• Theoretische Resultaten:
  • Monotonie: Beide algoritmen produceren een monotoon toenemende rij van doelwaarden.
  • Stationariteit: Accumulatiepunten van de gegenereerde rijen voldoen aan de KKT-voorwaarden.
  • Convergentiesnelheden: Het artikel stelt vast dat de som van de kwadraten van de afstanden tussen opeenvolgende iteraten (gewogen met eigenwaardegaps of singuliere waarden) eindig is, wat impliceert dat de iteraten een stationair punt benaderen.
  • Globale Convergentie: Als het stationaire punt geïsoleerd is en bepaalde spectrale gap-voorwaarden (voor HOOI) of vol-rang voorwaarden (voor ASI) worden voldaan, convergeert de volledige rij naar dat punt.
• Numerieke Experimenten:
  • Experimenten werden uitgevoerd op een "Miranda Scientific Simulation Tensor" en willekeurig gegenereerde tensoren (zowel reëel als complex).
  • HOOI vs. ASI: HOOI vereiste consistent minder iteraties om te convergeren dan ASI, omdat het de optimale subruimte berekent bij elke stap, terwijl ASI slechts één power iteration-stap uitvoert.
  • Initialisatie: Het gebruik van een afgeknotte HOSVD als startpunt verlaagde over het algemeen het aantal iteraties, hoewel niet universeel (in sommige gevallen convergeerde willekeurige initialisatie sneller).
  • Complexiteit: Hoewel HOOI in minder iteraties convergeert, is de rekenkosten per iteratie hoger dan bij ASI. De auteurs observeerden echter dat de totale CPU-tijd voor beide methoden concurrerend was, aangezien de besparing in het aantal iteraties voor HOOI de hogere kosten per stap compenseerde.
  • Stopcriteria: De experimenten benadrukten het risico van "valse convergentie", waarbij de doelfunctie tijdelijk plateauert voordat deze weer stijgt, wat suggereert dat op residu gebaseerde stopcriteria robuuster zijn dan die gebaseerd op doelwaarde.

Betekenis en Aanspraken
Het artikel claimt een meer toegankelijke en zelfstandige convergentieanalyse te bieden voor Tucker-decompositie-algoritmen in vergelijking met eerdere werken. Door volledig te vertrouwen op concepten uit de numerieke lineaire algebra in plaats van semi-algebraïsche meetkunde, zijn de resultaten bedoeld om beter toegankelijk te zijn voor de gemeenschap van numerieke lineaire algebra. De auteurs benadrukken dat hun analyse zowel reële als complexe tensoren bestrijkt en hiaten corrigeert in de historische analyse van ASI. Zij concluderen dat hoewel HOOI theoretisch superieur is wat betreft het aantal iteraties, beide methoden globaal convergent en effectief zijn voor het berekenen van Tucker-decomposities, waarbij de keuze tussen hen mogelijk afhankelijk is van de specifieke afweging tussen het aantal iteraties en de rekenkosten per iteratie.