Randomized Methods for Kernelized DMD

Technische Samenvatting: Gerandomiseerde Methoden voor Kernelized DMD

Probleemstelling
Dynamic Mode Decomposition (DMD) is een datagestuurde methode die wordt gebruikt om dominante dynamica te extraheren uit sequentiële snapshots van nietlineaire systemen. Het toepassen van DMD op grootschalige datasets met hoge staatdimensies ($N$) en een groot aantal snapshots ($M$) vormt echter een aanzienlijke computationele bottleneck. Hoewel Kernelized DMD (KDMD) dit probleem van grote $N$ vermindert door gebruik te maken van de kernel-trick, introduceert het een nieuwe beperking: het algoritme vereist het oplossen van twee $M \times M$ eigenproblemen. Dit resulteert in een slechte schaalbaarheid ten opzichte van het aantal snapshots, wat de toepasbaarheid van KDMD op datasets met lange trajecten beperkt. Bestaande gerandomiseerde benaderingen, zoals Random Fourier Features (RFF) en algebraïsche methoden zoals het oASIS-algoritme, proberen dit aan te pakken maar lijden aan trage convergentiesnelheden of numerieke instabiliteit, respectievelijk. Specifiek leunt oASIS op diagonale pivoting, wat in bepaalde tegenvoorbeelden kan falen in het leveren van nauwkeurige benaderingen en numeriek instabiel is vergeleken met gepivoteerde partiële Cholesky-factorisatie.

Methodologie
Het artikel stelt voor om het RPCholesky-algoritme (Randomly Pivoted Partial Cholesky) te integreren in het KDMD-framework om de berekening te versnellen en tegelijkertijd de numerieke stabiliteit te verbeteren.

1. Kernel-benadering via RPCholesky: In plaats van de volledige $M \times M$ Gramiaan-matrix $G$ te berekenen en het bijbehorende eigenprobleem op te lossen, maakt de auteur gebruik van RPCholesky om een low-rank benadering $G \approx FF^*$ te genereren. Deze methode selecteert pivot-indices $I = \{i_1, \dots, i_S\}$ op basis van een waarschijnlijkheidsverdeling afgeleid van de diagonale elementen van de residu-matrix, in plaats van een puur gulzig (greedy) diagonaal pivoting-strategie te gebruiken. Dit balanceert de "exploitatie" van grote diagonale elementen met de "exploratie" van kleinere elementen.
2. Algoritmische Integratie: De voorgestelde KDMD met gerandomiseerde sampling (Algoritme 2) vervangt de volledige eigendecompositie van $G$ door de eigendecompositie van de kleinere $S \times S$ matrix $F^*F$. De resulterende factoren worden gebruikt om de gereduceerde kernelmatrix $\hat{K}$ te construeren en de DMD-modi en eigenfuncties te berekenen.
3. Datagestuurde Residu's: Een cruciaal onderdeel van de methodologie is de afleiding van een specifieke datagestuurde residu-formule voor de gerandomiseerde setting. Omdat de standaard residu-berekening die wordt gebruikt in SVD-gebaseerde DMD niet direct toepasbaar is op de gerandomiseerde KDMD-output, leiden de auteurs een nieuw residu $r(i)$ (Vergelijking 7) af die gebruikmaakt van de pivot-selectie informatie ($A[:, I]$ en $G[:, I]$) verkregen tijdens de uitvoering van RPCholesky. Dit maakt het sorteren en selecteren van dominante modi mogelijk op basis van hun reconstructiekwaliteit.
4. Computationele Optimalisatie: De auteurs merken op dat voor sequentiële datamatrices $X$ en $Y$, de kernelmatrices kunnen worden samengesteld uit één grotere matrix $D = [X, Y]$. Dit maakt het mogelijk om het RPCholesky-algoritme eenmaal op $D$ uit te voeren, waarbij de noodzakelijke sub-blokken voor $G$ en $A$ worden geëxtraheerd, waardoor de dure volledige assemblage van deze matrices wordt vermeden.

Belangrijkste Bijdragen

• Algoritmisch Voorstel: Het artikel introduceert de toepassing van het RPCholesky-algoritme op KDMD, wat een stabiel alternatief biedt voor het oASIS-algoritme en de Nyström-benadering met diagonale pivoting.
• Stabiliteit en Ordening: De auteurs demonstreren dat RPCholesky betere stabiliteitsgaranties biedt dan eerdere gerandomiseerde KDMD-methoden. Cruciaal is dat zij aantonen dat de afgeleide datagestuurde residu's een betekenisvolle ordening van DMD-modi mogelijk maken, een kenmerk dat inconsistent of grillig was bij oASIS-gebaseerde pivoting.
• Complexiteitsanalyse: Het artikel biedt een computationele complexiteitsanalyse die laat zien dat de gerandomiseerde KDMD-benadering de kosten vermindert van $O(M^3)$ (voor standaard KDMD) naar $O(SMN + S^2M + S^3)$, waarbij $S$ het aantal gerandomiseerde samples is. Dit maakt het verwerken van datasets waar $M$ groot is mogelijk.
• Residu-formulering: De afleiding van een specifieke residu-metriek voor gerandomiseerde KDMD-modi, wat de selectie van dominante dynamica mogelijk maakt zonder dat de volledige kernelmatrix nodig is.

Resultaten
De effectiviteit van de voorgestelde methode werd geëvalueerd op drie benchmarkproblemen:

1. Stroming rond een cilinder: Met behulp van drukgegevens van een laminaire stromingssimulatie ($N=89351, M=150$), produceerde de RPCholesky-gebaseerde KDMD modi die visueel vergelijkbaar zijn met standaard DMD en KDMD, met residu's die vergelijkbaar zijn met de standaard KDMD. In contrast hiermee produceerde de oASIS-methode grillige residu's die niet hetzelfde gedrag reflecteerden, wat effectieve modus-sortering verhinderde.
2. Ongeforceerde Duffing-vergelijking: Een stresstest met een synthetische dataset ($10000 \times 7700$) toonde aan dat de gerandomiseerde KDMD-algoritmen (RPCholesky, oASIS en RFF) vergelijkbare relatieve reconstructiefouten bereikten naarmate het aantal samples $S$ toenam. De RPCholesky-methode vertoonde echter een superieure stabiliteit in modus-ordening vergeleken met oASIS. Een computationele tijd-analyse bevestigde dat alle gerandomiseerde varianten vergelijkbaar schalen met betrekking tot $S$.
3. Zeeoppervlaktetemperatuur Dataset: Toegepast op een grote real-world dataset ($2276$ snapshots, $10^6$ datapunten), identificeerde de RPCholesky KDMD succesvol de dominante modi. Opvallend genoeg volgden de modi geproduceerd door het voorgestelde algoritme de verwachte fysieke structuur (een op zichzelf staande eerste modus gevolgd door complexe geconjugeerde paren), terwijl de RFF EDMD-benadering er niet in slaagde deze paar-ordening te produceren.

Significantie
Het artikel beweert dat de combinatie van RPCholesky en KDMD de specifieke stabiliteits- en ordeningsgebreken van bestaande gerandomiseerde kernelmethoden aanpakt. Door het gulzige diagonale pivoting te vervangen door adaptieve gerandomiseerde sampling, bereikt de methode een balans tussen informatie-exploitatie en -exploratie. De primaire significantie ligt in het in staat stellen van KDMD om grotere snapshot-aantallen ($M$) te verwerken met verbeterde numerieke stabiliteit en een betrouwbaar mechanisme voor het selecteren van dominante modi via datagestuurde residu's, zonder de noodzaak om de volledige $M \times M$ kernelmatrices te assembleren of op te slaan. De auteurs positioneren dit als een levensvatbaar instrument voor het versnellen van KDMD in grootschalige data-gestuurde dynamische systeemanalyses.