Randomized Methods for Kernelized DMD

Résumé technique : Méthodes randomisées pour la DMD noyau (Kernelized DMD)

Énoncé du problème
La Décomposition de Modes Dynamiques (DMD) est une méthode basée sur les données utilisée pour extraire la dynamique dominante de systèmes non linéaires séquentiels. Cependant, l'application de la DMD à des jeux de données à grande échelle avec des dimensions d'état élevées ($N$) et un grand nombre de clichés ($M$) présente un goulot d'étranglement computationnel important. Bien que la DMD par noyau (KDMD) atténue ce problème lié au grand $N$ en utilisant le "truc du noyau" (kernel trick), elle introduit une nouvelle contrainte : l'algorithme nécessite la résolution de deux problèmes de valeurs propres de taille $M \times M$. Cela entraîne une faible extensibilité par rapport au nombre de clichés, limitant l'applicabilité de la KDMD aux jeux de données de trajectoires longues. Les approches randomisées existantes, telles que les caractéristiques de Fourier aléatoires (RFF) et les méthodes algébriques comme l'algorithme oASIS, tentent de remédier à cela mais souffrent soit de taux de convergence lents, soit d'instabilité numérique. Plus précisément, oASIS repose sur un pivotement diagonal, qui peut échouer à retourner des approximations précises dans certains contre-exemples et s'avère numériquement moins stable qu'une factorisation de Cholesky partielle pivotée.

Méthodologie
Le document propose d'intégrer l'algorithme RPCholesky (Cholesky partiel à pivotement aléatoire) dans le cadre de la KDMD pour accélérer le calcul tout en améliorant la stabilité numérique.

1. Approximation par noyau via RPCholesky : Au lieu de calculer la matrice de Gram complète $M \times M$ $G$ et de résoudre le problème de valeurs propres associé, les auteurs utilisent RPCholesky pour générer une approximation de rang faible $G \approx FF^*$. Cette méthode sélectionne des indices de pivot $I = \{i_1, \dots, i_S\}$ basés sur une distribution de probabilité dérivée des éléments diagonaux de la matrice résiduelle, plutôt que d'utiliser une stratégie de pivotement diagonal purement gloutonne. Cela équilibre l'« exploitation » des grands éléments diagonaux et l'« exploration » des plus petits.
2. Intégration algorithmique : La KDMD proposée avec échantillonnage randomisé (Algorithme 2) remplace la décomposition en valeurs propres complète de $G$ par la décomposition en valeurs propres de la matrice plus petite $S \times S$ $F^*F$. Les facteurs résultants sont utilisés pour construire la matrice de noyau réduite $\hat{K}$ et calculer les modes et les fonctions propres de la DMD.
3. Résidus pilotés par les données : Un composant critique de la méthodologie est la dérivation d'une formule de résidu spécifique pilotée par les données pour le cadre randomisé. Puisque le calcul de résidu standard utilisé dans la DMD basée sur la SVD n'est pas directement applicable à la sortie de la KDMD randomisée, les auteurs dérivent un nouveau résidu $r(i)$ (Équation 7) qui utilise les informations de sélection de pivot ($A[:, I]$ et $G[:, I]$) obtenues lors de l'exécution de RPCholesky. Cela permet le tri et la sélection des modes dominants basés sur leur qualité de reconstruction.
4. Optimisation computationnelle : Les auteurs notent que pour des matrices de données séquentielles $X$ et $Y$, les matrices de noyau peuvent être assemblées à partir d'une seule matrice plus large $D = [X, Y]$. Cela permet d'exécuter l'algorithme RPCholesky une seule fois sur $D$, extrayant les sous-blocs nécessaires pour $G$ et $A$, évitant ainsi l'assemblage complet et coûteux de ces matrices.

Contributions clés

• Proposition algorithmique : Le document introduit l'application de l'algorithme RPCholesky à la KDMD, offrant une alternative stable à l'algorithme oASIS et à l'approximation de Nyström avec pivotement diagonal.
• Stabilité et ordonnancement : Les auteurs démontrent que RPCholesky offre de meilleures garanties de stabilité que les méthodes précédentes de KDMD randomisée. Crucialement, ils montrent que les résidus dérivés permettent un ordonnancement significatif des modes DMD, une caractéristique qui était incohérente ou erratique avec le pivotement basé sur oASIS.
• Analyse de complexité : Le document fournit une analyse de la complexité computationnelle montrant que l'approche KDMD randomisée réduit le coût de $O(M^3)$ (pour la KDMD standard) à $O(SMN + S^2M + S^3)$, où $S$ est le nombre d'échantillons aléatoires. Cela permet le traitement de jeux de données où $M$ est grand.
• Formulation du résidu : La dérivation d'une métrique de résidu spécifique pour les modes de la KDMD randomisée, permettant la sélection de la dynamique dominante sans nécessiter la matrice de noyau complète.

Résultats
L'efficacité de la méthode proposée a été évaluée sur trois problèmes de référence :

1. Écoulement autour d'un cylindre : En utilisant des données de pression d'une simulation d'écoulement laminaire ($N=89351, M=150$), la KDMD basée sur RPCholesky a produit des modes visuellement similaires à la DMD et la KDMD standards, avec des résidus comparables à la KDMD standard. En revanche, la méthode oASIS a produit des résidus erratiques qui ne reflétaient pas le même comportement, empêchant un tri efficace des modes.
2. Équation de Duffing non forcée : Un test de résistance utilisant un jeu de données synthétique ($10000 \times 7700$) a montré que les algorithmes de KDMD randomisés (RPCholesky, oASIS et RFF) atteignaient des erreurs de reconstruction relatives similaires à mesure que le nombre d'échantillons $S$ augmentait. Cependant, la méthode RPCholesky a démontré une stabilité supérieure dans l'ordonnancement des modes par rapport à oASIS. L'analyse du temps de calcul a confirmé que toutes les variantes randomisées évoluent de manière similaire par rapport à $S$.
3. Jeu de données de température de surface de la mer : Appliquée à un large jeu de données réelles ($2276$ clichés, $10^6$ points de données), la KDMD par RPCholesky a réussi à identifier les modes dominants. Notamment, les modes produits par l'algorithme proposé respectent la structure physique attendue (un premier mode autonome suivi de paires conjuguées complexes), alors que l'approche RFF EDMD n'a pas réussi à produire cet ordonnancement par paires.

Signification
Le document affirme que la combinaison de RPCholesky et de la KDMD répond aux inconvénients spécifiques de stabilité et d'ordonnancement des méthodes de noyau randomisées existantes. En remplaçant le pivotement diagonal gloutonne par un échantillonnage aléatoire adaptatif, la méthode atteint un équilibre entre l'exploitation et l'exploration de l'information. La principale signification réside dans la capacité de la KDMD à gérer de grands nombres de clichés ($M$) avec une stabilité numérique améliorée et un mécanisme fiable de sélection des modes dominants via des résidus pilotés par les données, sans avoir besoin d'assembler ou de stocker les matrices de noyau complètes de taille $M \times M$. Les auteurs positionnent cela comme un outil viable pour accélérer la KDMD dans l'analyse de systèmes dynamiques à grande échelle basés sur les données.