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

1. Problemstellung

Das Paper adressiert die Herausforderung, große multilinear Gleichungssysteme der Form $\Phi(X) = C$ effizient zu lösen, die in Anwendungen wie der Bild- und Videorestaurierung (z. B. Entschärfung von unscharfen und verrauschten Farbbildern oder Videos) auftreten.

• Herausforderung: Klassische Methoden basieren oft auf der Vektorisierung von Daten, was die intrinsische multidimensionale Struktur zerstört und zu extrem großen, speicherintensiven Matrizen führt. Tensor-basierte Ansätze erhalten diese Struktur, aber klassische tensorielle Krylov-Unterraum-Methoden (wie das globale GMRES oder Golub-Kahan) erfordern eine vollständige Orthogonalisierung unter Verwendung des Frobenius-Inner-Produkts.
• Komplexitätsproblem: Bei hochdimensionalen Tensoren (z. B. Farbbilder oder Videos mit mehreren Kanälen) werden die Kosten für die Orthogonalisierung prohibitiv hoch, da sie mit dem Produkt aller Tensor-Dimensionen skalieren.

2. Methodik

Die Autoren entwickeln einen randomisierten Rahmen, der Krylov-Unterraum-Methoden mit sketching (Projektion auf niedrigdimensionale Unterräume) und dem Einstein-Produkt kombiniert.

• Einstein-Produkt: Dies verallgemeinert die Matrixmultiplikation auf Tensoren höherer Ordnung, wobei die multidimensionalen Korrelationen erhalten bleiben. Es wird verwendet, um lineare Operatoren wie Unschärfen (Blurring) zu modellieren: $\Phi(X) = A *_N X$ oder $\Phi(X) = A *_N X *_M B$.
• Sketched Einstein Inner Product: Anstatt das teure Frobenius-Inner-Produkt über den gesamten Tensor zu berechnen, wird ein „sketching"-Operator $S$ eingeführt. Dieser projiziert den Tensor durch zufällige Projektionsmatrizen $\Theta_k$ auf niedrigere Dimensionen. Das sketched Inner-Produkt ist definiert als:
  $$\langle X, Y \rangle_\Theta = \langle S(X), S(Y) \rangle_F$$
  Unter der Annahme einer Subspace-Embedding-Eigenschaft (mit einer kleinen Fehlerwahrscheinlichkeit $\epsilon$) bleibt die geometrische Struktur und die Konvergenzverhalten erhalten, während die Dimension drastisch reduziert wird.
• Randomized Tensor Global Arnoldi-Prozess: Die Autoren modifizieren den klassischen globalen Arnoldi-Algorithmus, indem sie den sketched Operator $\Phi_S$ verwenden. Dies ermöglicht die Konstruktion einer orthonormalen Basis für den Krylov-Unterraum mit deutlich reduzierten Kosten.
• Regularisierung: Da viele Restaurierungsprobleme schlecht gestellt (ill-posed) sind, wird Tikhonov-Regularisierung integriert. Das große Problem wird auf ein kleines, projiziertes Tikhonov-Problem im Unterraum reduziert, das effizient gelöst werden kann. Die Regularisierungsparameter $\mu$ werden mittels Generalized Cross-Validation (GCV) oder der L-Kurve-Methode bestimmt.
• Algorithmen: Es werden zwei Hauptalgorithmen vorgestellt:
  1. Sketched Tensor Global GMRES: Für die Lösung linearer Tensor-Gleichungssysteme.
  2. Sketched Block Golub-Kahan: Für Least-Squares-Probleme, die bei der Bildrestaurierung häufig auftreten.

3. Wichtige Beiträge

• Entwicklung des RTG-GMRES: Einführung der „Randomized Tensor Global GMRES"-Methode, die die Orthogonalisierungskosten signifikant senkt, ohne die Konvergenzeigenschaften unter Subspace-Embedding-Annahmen zu verlieren.
• Theoretische Fundierung: Herleitung von Residuen-Schranken, Störungsanalysen und Beweisen für die Singularwert-Boundings der sketched Tensoren. Es wird gezeigt, dass die sketched Methode die algebraische Struktur des Einstein-Produkts bewahrt.
• Effiziente Block-Verfahren: Erweiterung der Block-GMRES- und Block-Golub-Kahan-Verfahren auf den Tensor-Raum unter Verwendung des sketched Einstein-Inner-Produkts.
• Anwendung auf reale Daten: Demonstration der Methode auf hochdimensionalen Problemen (RGB-Bilder und Videos), wo traditionelle Methoden an Speicher- oder Rechengrenzen stoßen.

4. Ergebnisse

Die numerischen Experimente wurden in MATLAB auf Standard-Hardware durchgeführt und verglichen die sketched Methoden mit klassischen tensor-basierten Methoden (ohne Sketching).

• Genauigkeit: Die sketched Methoden liefern Ergebnisse, die in Bezug auf den Peak Signal-to-Noise Ratio (PSNR) und den relativen Fehler (RE) mit den klassischen Methoden vergleichbar oder sogar leicht besser sind. Das Sketching beeinträchtigt die Rekonstruktionsqualität nicht signifikant.
• Rechenzeit: Der größte Vorteil liegt in der Effizienz. Die sketched Algorithmen reduzierten die CPU-Zeit um etwa 40–60 %.
  • Beispiel: Bei einem Rauschniveau von $10^{-3}$ sank die Zeit für den „Einstein Block Golub-Kahan" von 7,29 s (klassisch) auf 3,32 s (sketched).
  • Der „Sketched Einstein Block Golub-Kahan" erwies sich als der beste Kompromiss zwischen Genauigkeit und Geschwindigkeit.
• Skalierbarkeit: Die Methode ist besonders vorteilhaft für hochdimensionale Daten und zeitkritische Anwendungen, da sie den Speicherbedarf und die Rechenkomplexität senkt.

5. Bedeutung und Fazit

Das Paper stellt einen wichtigen Fortschritt im Bereich des wissenschaftlichen Rechnens für multidimensionale Daten dar.

• Praktische Relevanz: Die Methode bietet einen praktikablen Weg, um hochauflösende Bilder und Videos zu restaurieren, ohne die multidimensionale Struktur der Daten durch Vektorisierung zu zerstören.
• Effizienzgewinn: Durch die Kombination von Randomisierung (Sketching) mit etablierten Krylov-Methoden wird die Barriere für die Anwendung tensor-basierter Algorithmen auf sehr große Probleme gesenkt.
• Zukunftsaussichten: Die Autoren sehen Potenzial für weitere Erweiterungen in anderen Bereichen wie hyperspektraler Bildgebung, hochdimensionalen PDE-Diskretisierungen und Signalverarbeitung, wo ähnliche multidimensionale Strukturen vorliegen.

Zusammenfassend beweist das Paper, dass randomisierte sketching-Techniken eine leistungsstarke Alternative zu klassischen deterministischen Verfahren sind, die eine hohe Genauigkeit bei deutlich reduzierten Rechenkosten garantieren.