Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration

Titel: Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product met Toepassingen in Beeld- en Videorestauratie

1. Probleemstelling

Het paper adresseert het probleem van het oplossen van grote, lineaire multilineaire systemen die voortkomen uit de restauratie van kleurbeelden en video's (zoals ontvaging en ruisreductie).

• De uitdaging: Traditionele matrixgebaseerde methoden vereisen vaak vectorisatie van de data, wat de intrinsieke multidimensionale structuur van de gegevens vernietigt en leidt tot enorme, geheugenintensieve problemen.
• Tensor-benadering: Hoewel tensor-methoden (gebaseerd op het Einstein-product) de multidimensionale structuur behouden, worden klassieke algoritmen zoals het Tensor Global GMRES (Generalized Minimal Residual) en Golub-Kahan methoden computationally onhaalbaar voor hoog-dimensionale problemen. De reden hiervoor is de hoge kostprijs van de volledige orthogonalisatie en het berekenen van Frobenius-inproducten voor grote tensoren.
• Doel: Het ontwikkelen van een efficiëntere methode die de convergentie-eigenschappen behoudt maar de rekenkosten drastisch verlaagt, specifiek voor ill-geplaatste problemen (zoals het reconstrueren van onscherpe en ruizige beelden).

2. Methodologie

De auteurs introduceren een gerandomiseerd raamwerk dat de klassieke tensor Krylov-subruimte methoden combineert met sketching (random projecties) via het Einstein-product.

• Het Einstein-product: Dit is een generalisatie van matrixvermenigvuldiging voor hogere-orde tensoren, genoteerd als $A *_N X$. Het behoudt de correlaties tussen verschillende kanalen (bijv. RGB-kleuren).
• Sketched Einstein Inproduct: In plaats van het volledige Frobenius-inproduct $\langle X, Y \rangle_F$ te berekenen, wordt een "gesketched" inproduct gebruikt:
  $$\langle X, Y \rangle_\Theta = \langle S(X), S(Y) \rangle_F$$
  Hierbij is $S$ een lineaire operator die de tensor projecteert naar een lagere dimensie via mode-wise random projectiematrices ($\Theta_k$). Dit veronderstelt een subspace embedding, waarbij de geometrische structuur met hoge waarschijnlijkheid behouden blijft binnen een bepaalde tolerantie $\epsilon$.
• Randomized Tensor Global Arnoldi Proces:
  • Het klassieke Arnoldi-proces wordt aangepast door de operator $\Phi$ te vervangen door een gesketchede versie $\Phi_S = S(\Phi(\cdot))$.
  • De orthogonalisatie van de basisvectoren gebeurt met het gesketchede inproduct in plaats van het volledige inproduct.
  • Dit resulteert in een Randomized Tensor Global GMRES (RTG-GMRES) en een gesketchede variant van de Block Golub-Kahan methode.
• Tikhonov Regularisatie: Om de instabiliteit van ill-geplaatste problemen (zoals ontvaging) op te lossen, wordt Tikhonov regularisatie geïntegreerd. De regularisatieparameter $\mu$ wordt gekozen via Generalized Cross-Validation (GCV) op het gereduceerde projectieprobleem.

3. Belangrijkste Bijdragen

1. Nieuw Algoritme: De ontwikkeling van Randomized Tensor Krylov Subspace Methods die specifiek zijn ontworpen voor het Einstein-product, waardoor de multidimensionale structuur intact blijft zonder vectorisatie.
2. Complexiteitsreductie: De methode verlaagt de orthogonalisatiekosten aanzienlijk. Door het werken in een gecomprimeerde ruimte (via sketching) worden de kosten voor tensor-tensor producten en inproducten gereduceerd, terwijl de convergentiebehoud wordt gegarandeerd onder subruimte-embeddingsvoorwaarden.
3. Theoretische Analyse: Het paper levert rigoureuze theoretische bewijzen voor:
   • Residu-bounds.
   • Perturbatie-analyse van de gesketchede operator.
   • Singulariteitswaarde-bounds voor de gesketchede tensoren.
   • De validiteit van de Tikhonov-regularisatie in het gereduceerde domein.
4. Block Formules: Uitbreiding van de methoden naar block-tensor formuleringen (Block GMRES en Block Golub-Kahan), wat essentieel is voor het verwerken van meerdere kanalen (zoals RGB-beelden) of videoframes tegelijkertijd.

4. Resultaten

De methode is getest op het restaureren van onscherpe en ruizige RGB-afbeeldingen en video's, met een vergelijking tussen:

• Klassieke Tensor GKB (zonder sketching).
• Gesketchede Einstein Block GMRES.
• Gesketchede Einstein Block Golub-Kahan.

Kernbevindingen uit de numerieke experimenten:

• Snelheid: De gesketchede methoden zijn 40% tot 60% sneller dan de klassieke methoden. Bijvoorbeeld, bij een ruisniveau van $10^{-2}$ daalde de rekentijd voor de Block Golub-Kahan methode van 1,58s naar 0,70s.
• Nauwkeurigheid: De kwaliteit van de restauratie (gemeten in PSNR - Peak Signal-to-Noise Ratio en Relative Error) bleef vergelijkbaar of zelfs licht verbeterd ten opzichte van de niet-gesketchede versies. Dit bevestigt dat sketching de oplossingskwaliteit niet ten koste gaat.
• Efficiëntie: De Block Golub-Kahan methode met sketching bood de beste afweging tussen nauwkeurigheid en snelheid.

5. Significantie en Toepassing

Dit onderzoek biedt een krachtig en praktisch raamwerk voor het oplossen van grote, hoog-dimensionale tensorvergelijkingen in de beeldverwerking.

• Schaalbaarheid: Het maakt het mogelijk om zeer grote problemen (zoals hoge-resolutie video's en hyperspectrale beelden) op te lossen op standaard hardware, wat met klassieke methoden vaak onmogelijk zou zijn door geheugen- en rekentijdbeperkingen.
• Toekomstperspectief: De methode is niet beperkt tot beeldrestauratie; het is ook toepasbaar op andere gebieden zoals signaalverwerking en de discretisatie van multivariabele partiële differentiaalvergelijkingen (PDE's).
• Conclusie: Het combineren van sketching met tensor Krylov-methoden is een effectieve strategie om de "curse of dimensionality" te doorbreken, waardoor snelle en nauwkeurige restauratie van complexe, multidimensionale data mogelijk wordt.