Randomized Methods for Kernelized DMD

Technisches Resümee: Randomisierte Methoden für kernelisiertes DMD

Problemstellung
Die Dynamic Mode Decomposition (DMD) ist eine datengesteuerte Methode zur Extraktion dominanter Dynamiken aus sequenziellen Snapshots nichtlinearer Systeme. Die Anwendung von DMD auf großskalige Datensätze mit hohen Zustandsdimensionen ($N$) und einer großen Anzahl an Snapshots ($M$) stellt jedoch einen erheblichen Rechenengpass dar. Während die kernelisierte DMD (KDMD) das Problem großer $N$ durch die Nutzung des Kernel-Tricks mildert, führt sie eine neue Einschränkung ein: Der Algorithmus erfordert das Lösen zweier $M \times M$ Eigenprobleme. Dies führt zu einer schlechten Skalierbarkeit hinsichtlich der Anzahl der Snapshots, was die Anwendbarkeit von KDMD auf Datensätze mit langen Trajektorien einschränkt. Bestehende randomisierte Ansätze, wie Random Fourier Features (RFF) und algebraische Methoden wie der oASIS-Algorithmus, versuchen dies zu adressieren, leiden aber unter langsamen Konvergenzraten bzw. numerischer Instabilität. Insbesondere verlässt sich oASIS auf diagonales Pivoting, was in bestimmten Gegenbeispielen dazu führen kann, dass keine genauen Approximationen zurückgegeben werden, und im Vergleich zur gepivotteten partiellen Cholesky-Faktorisierung numerisch instabil ist.

Methodik
Das Paper schlägt die Integration des RPCholesky-Algorithmus (Randomly Pivoted Partial Cholesky) in das KDMD-Framework vor, um die Berechnung zu beschleunigen und gleichzeitig die numerische Stabilität zu erhöhen.

1. Kernel-Approximation via RPCholesky: Anstatt die vollständige $M \times M$ Gramian-Matrix $G$ zu berechnen und das zugehörige Eigenproblem zu lösen, nutzen die Autoren RPCholesky, um eine Low-Rank-Approximation $G \approx FF^*$ zu generieren. Diese Methode wählt Pivot-Indizes $I = \{i_1, \dots, i_S\}$ basierend auf einer Wahrscheinlichkeitsverteilung, die aus den Diagonalelementen der Residuenmatrix abgeleitet wird, anstatt eine rein gierige (greedy) Strategie des diagonalen Pivotings zu verwenden. Dies balanciert die „Exploitation“ (Ausnutzung) großer Diagonalelemente mit der „Exploration“ (Erkundung) kleinerer Elemente aus.
2. Algorithmische Integration: Der vorgeschlagene randomisierte KDMD-Ansatz (Algorithmus 2) ersetzt die vollständige Eigendekomposition von $G$ durch die Eigendekomposition der kleineren $S \times S$ Matrix $F^*F$. Die resultierenden Faktoren werden verwendet, um die reduzierte Kernel-Matrix $\hat{K}$ zu konstruen und DMD-Modi sowie Eigenfunktionen zu berechnen.
3. Datengesteuerte Residuen: Eine kritische Komponente der Methodik ist die Ableitung einer spezifischen datengesteuerten Residuenformel für das randomisierte Setting. Da die Standard-Residuenberechnung, die in der SVD-basierten DMD verwendet wird, nicht direkt auf den randomisierten KDMD-Output anwendbar ist, leiten die Autoren ein neues Residuum $r(i)$ (Gleichung 7) ab, das die während der RPCholesky-Ausführung erhaltenen Pivot-Selektionsinformationen ($A[:, I]$ und $G[:, I]$) nutzt. Dies ermöglicht die Sortierung und Auswahl dominanter Modi basierend auf ihrer Rekonstruktionsqualität.
4. Kompetitive Optimierung: Die Autoren merken an, dass für sequenzielle Datenmatrizen $X$ und $Y$ die Kernel-Matrizen aus einer einzigen größeren Matrix $D = [X, Y]$ zusammengesetzt werden können. Dies erlaubt es, den RPCholesky-Algorithmus einmal auf $D$ auszuführen, um die notwendigen Teilblöcke für $G$ und $A$ zu extrahieren, wodurch die teure vollständige Assemblierung dieser Matrizen vermieden wird.

Wesentliche Beiträge

• Algorithmischer Vorschlag: Das Paper führt die Anwendung des RPCholesky-Algorithmus auf KDMD ein und bietet eine stabile Alternative zum oASIS-Algorithmus und der Nyström-Approximation mit diagonalem Pivoting.
• Stabilität und Ordnung: Die Autoren zeigen, dass RPCholesky bessere Stabilitätsgarantien als bisherige randomisierte KDMD-Methoden bietet. Entscheidend ist, dass die abgeleiteten datengesteuerten Residuen eine sinnvolle Ordnung der DMD-Modi ermöglichen – ein Merkmal, das mit dem oASIS-basierten Pivoting inkonsistent oder erratisch war.
• Komplexitätsanalyse: Das Paper liefert eine Analyse der Rechenkomplexität, die zeigt, dass der randomisierte KDMD-Ansatz die Kosten von $O(M^3)$ (für Standard-KDMD) auf $O(SMN + S^2M + S^3)$ reduziert, wobei $S$ die Anzahl der Zufallsproben ist. Dies ermöglicht die Verarbeitung von Datensätzen, bei denen $M$ groß ist.
• Residuen-Formulierung: Die Ableitung einer spezifischen Residuenmetrik für randomisierte KDMD-Modi ermöglicht die Auswahl dominanter Dynamiken, ohne die vollständige Kernel-Matrix zu benötigen.

Ergebnisse
Die Wirksamkeit der vorgeschlagenen Methode wurde anhand von drei Benchmark-Problemen evaluiert:

1. Strömung um einen Zylinder: Unter Verwendung von Druckdaten einer laminaren Strömungssimulation ($N=89351, M=150$) erzeugte das RPCholesky-basierte KDMD Modi, die visuell ähnlich zu Standard-DMD und KDMD sind, mit Residuen, die vergleichbar mit dem Standard-KDMD sind. Im Gegensatz dazu erzeugte die oASIS-Methode erratische Residuen, die das gleiche Verhalten nicht widerspiegelten, was eine effektive Modus-Sortierung verhinderte.
2. Ungesteuerte Duffing-Gleichung: Ein Stresstest unter Verwendung eines synthetischen Datensatzes ($10000 \times 7700$) zeigte, dass die randomisierten KDMD-Algorithmen (RPCholesky, oASIS und RFF) mit zunehmender Probenzahl $S$ ähnliche relative Rekonstruktionsfehler erreichten. Die RPCholesky-Methode demonstrierte jedoch eine überlegene Stabilität in der Modus-Sortierung im Vergleich zu oASIS. Eine Analyse der Rechenzeit bestätigte, dass alle randomisierten Varianten in Bezug auf $S$ ähnlich skalieren.
3. Meerestemperatur-Datensatz: Angewendet auf einen großen realen Datensatz ($2276$ Snapshots, $10^6$ Datenpunkte), identifizierte das RPCholesky-KDMD erfolgreich dominante Modi. Bemerkenswert ist, dass die durch den vorgeschlagenen Algorithmus erzeugten Modi der erwarteten physikalischen Struktur entsprachen (ein einzelner erster Modus gefolgt von komplex konjugierten Paaren), während der RFF EDMD-Ansatz scheiterte, diese paarweise Ordnung zu erzeugen.

Bedeutung
Das Paper behauptet, dass die Kombination aus RPCholesky und KDMD die spezifischen Stabilitäts- und Ordnungsmängel bestehender randomisierter Kernel-Methoden adressiert. Durch den Ersatz von gierigem diagonalem Pivoting durch adaptives randomisiertes Sampling erreicht die Methode ein Gleichgewicht zwischen Informationsausnutzung (Exploitation) und Exploration. Die primäre Bedeutung liegt darin, KDMD zu ermöglichen, größere Snapshot-Anzahlen ($M$) mit verbesserter numerischer Stabilität und einem zuverlässigen Mechanismus zur Auswahl dominanter Modi mittels datengesteuerter Residuen zu handhaben, ohne die Notwendigkeit, die vollständigen $M \times M$ Kernel-Matrizen zu assemblieren oder zu speichern. Die Autoren positionieren dies als ein lebensfähiges Werkzeug zur Beschleunigung von KDMD in der großskaligen datengesteuerten Dynamik-Analyse.