A Practical Mode-parallel Implementation of the (H-)Tucker Decomposition via Randomization

Titel

Een praktische mode-parallelle implementatie van de (H-)Tucker-decompositie via randomisatie.

1. Probleemstelling

Tensors (meerdimensionale arrays) zijn essentieel geworden voor het compacte en informatieve representeren van multidimensionale data in diverse domeinen zoals deep learning, beeldherkenning en aanbevelingssystemen. Twee veelgebruikte methoden om de structuur van deze data bloot te leggen en te comprimeren zijn de Tucker-decompositie en de Hierarchical Tucker (H-Tucker)-decompositie.

De uitdagingen bij het berekenen van deze decomposities zijn:

• Rekenkracht en Geheugen: Traditionele deterministische algoritmen (zoals HOSVD) vereisen het vormen van volledige "matricisaties" (ontvouwingen) van de tensor. Bij hoge dimensies groeit de grootte van deze matrices exponentieel, wat leidt tot enorme geheugeneisen en rekentijd.
• Parallelisatiebeperkingen: Bestaande parallelle implementaties paralleliseren vaak operaties binnen een mode (bijv. matrix-vector vermenigvuldigingen), maar bezoeken de modes nog steeds sequentieel. Een ware "mode-parallelle" aanpak (waarbij alle modes gelijktijdig worden verwerkt) is vaak onuitvoerbaar omdat elke rekenknoop een volledige kopie van de oorspronkelijke tensor zou moeten kunnen opslaan om de matricisaties te vormen.
• Opslagkosten: Bij de standaard Tucker-decompositie groeit de kern-tensor exponentieel met het aantal modes. De H-Tucker lost dit deels op via een boomstructuur, maar de berekening blijft zwaar.

2. Methodologie

De auteurs stellen een nieuwe, gestochastische (gebaseerd op randomisatie) aanpak voor die zowel de Tucker- als de H-Tucker-decompositie versnelt en mogelijk maakt in een mode-parallelle omgeving. De kern van de methode bestaat uit twee stappen:

1. Fiber Sampling (Steekproeven):
   In plaats van de volledige matricisatie $X^{(k)}$ van de tensor te vormen (wat alle data bevat), worden er willekeurig een beperkt aantal "fibers" (kolommen van de matricisatie) geselecteerd. Dit resulteert in een veel kleinere matrix $Y_k$.

   • Voordeel: Dit elimineert de noodzaak om de volledige oorspronkelijke tensor in het geheugen te kopiëren of te herschikken. Het maakt het mogelijk om op elke rekenknoop slechts een klein deel van de data te verwerken.

2. Randomized Range-Finding:
   Op de geselecteerde steekproef $Y_k$ wordt een randomisatie-algoritme (gebaseerd op de Randomized SVD of RSVD) toegepast. Er wordt een Gaussische "sketch"-matrix gebruikt om een goede benadering van het kolomruimte (range) van de oorspronkelijke matricisatie te vinden.

   • Voordeel: Dit verhoogt de nauwkeurigheid van de benadering zonder de volledige SVD van de grote matrix te hoeven berekenen.

De Algoritmes:

• Sub-R-HOSVD: Een variant van de Truncated HOSVD die fiber sampling en range-finding combineert. Het berekent de factor-matrices $U_k$ parallel voor elke mode $k$.
• Sub-R-RtL-HT: Een uitbreiding naar de H-Tucker-decompositie, specifiek voor het Root-to-Leaves (RtL) algoritme. Hierbij worden de leaf-factoren berekend via Sub-R-HOSVD en worden de interne knopen van de dimension-baam (dimension tree) eveneens via fiber sampling en range-finding verwerkt.

3. Belangrijkste Bijdragen

• Ware Mode-Parallelisme: De auteurs doorbreken de beperking van bestaande methoden. Omdat geen volledige matricisaties nodig zijn, kunnen alle modes gelijktijdig worden verwerkt op verschillende rekenknooppunten zonder dat elke knoop een volledige kopie van de data nodig heeft. Dit verlaagt de communicatiekosten en het lokale geheugengebruik aanzienlijk.
• Theoretische Foutgrenzen: Voor de Sub-R-HOSVD hebben de auteurs wiskundige bovengrenzen afgeleid voor de verwachte fout (in de Frobenius-norm). Deze grenzen tonen aan dat de methode, mits de steekproefgrootte voldoende groot is (afhankelijk van de coherentie van de data), een nauwkeurige benadering garandeert.
• Geen Foutgrenzen voor H-Tucker (nog): Voor de H-Tucker variant (Sub-R-RtL-HT) hebben ze de methode ontworpen en getest, maar de complexe foutanalyse voor de hiërarchische structuur wordt als een toekomstige uitdaging beschouwd.
• Efficiëntie: De methoden vermijden de vorming van grote tussenobjecten, wat leidt tot een drastische reductie in zowel rekencomplexiteit ($O(d \cdot n \cdot s \cdot r)$ in plaats van $O(d \cdot n^{d+1})$) en geheugengebruik.

4. Resultaten

De auteurs hebben hun methoden getest op zowel synthetische data als real-world datasets (COIL-100 beelddataset en meteorologische data van Noord-Italië) op een HPC-systeem (Leonardo bij Cineca).

• Snelheid: De Sub-R-HOSVD is over het algemeen één orde van grootte sneller dan bestaande state-of-the-art methoden (zoals HOSVD, ST-HOSVD en andere randomisatie-methoden zoals R-HOSVD en rHKron).
• Nauwkeurigheid: Ondanks het gebruik van een zeer klein percentage van de data (bijvoorbeeld slechts 0,00005% van de kolommen in synthetische tests), blijft de relatieve fout zeer laag en vergelijkbaar met deterministische methoden.
• Schaling (Scalability):
  • Sterke schaling: De methoden tonen uitstekende sterke schaling bij het verhogen van het aantal processen (tot 8 processen in de tests).
  • Parallelle implementatie: De mode-parallelle aanpak werkt effectief. De enige seriële component (het verzamelen van resultaten en de laatste TTM-operatie) is verwaarloosbaar klein ten opzichte van de totale rekentijd.
  • H-Tucker: Ook voor de H-Tucker-decompositie werden significante snelheidswinsten behaald. De auteurs merkten echter op dat de parallelisatie van H-Tucker complexer is door de ongelijke kosten van de operaties in de boomstructuur, wat een zorgvuldige workload-balancering vereist.

5. Betekenis en Conclusie

Dit artikel biedt een praktische oplossing voor het "curse of dimensionality"-probleem in tensor-decomposities. Door het combineren van fiber sampling en randomisatie, maken de auteurs het mogelijk om hoge-dimensionale tensors te comprimeren op manieren die eerder onmogelijk waren vanwege geheugenbeperkingen.

• Praktische Toepassing: De methode maakt het haalbaar om grote datasets te analyseren op standaard HPC-clusters zonder dat er enorme hoeveelheden RAM nodig zijn.
• Toekomstperspectief: Het werk opent de deur voor verdere onderzoek naar de foutanalyse van randomisatie in hiërarchische structuren en de optimalisatie van parallelle workflows voor complexe boomstructuren.

Kortom, de auteurs hebben een brug geslagen tussen theoretische randomisatie en praktische, schaalbare implementatie voor de decompositie van complexe multidimensionale data.