Randomized Methods for Kernelized DMD

Resumen Técnico: Métodos Aleatorizados para KDMD

Planteamiento del Problema
La Descomposición de Modos Dinámicos (DMD) es un método basado en datos utilizado para extraer la dinámica dominante de sistemas no lineales a partir de instantáneas secuenciales. Sin embargo, aplicar DMD a conjuntos de datos a gran escala con dimensiones de estado altas ($N$) y un gran número de instantáneas ($M$) presenta un cuello de botella computacional significativo. Si bien la DMD Kernelizada (KDMD) mitiga este problema de un $N$ elevado utilizando el truco del kernel, introduce una nueva restricción: el algoritmo requiere resolver dos problemas de autovalores de tamaño $M \times M$. Esto resulta en un escalamiento deficiente con respecto al número de instantáneas, lo que limita la aplicabilidad de KDMD para conjuntos de datos de trayectorias largas. Los enfoques aleatorizados existentes, como las Características de Fourier Aleatorias (RFF) y los métodos algebraicos como el algoritmo oASIS, intentan abordar esto pero sufren de tasas de convergencia lentas o inestabilidad numérica, respectivamente. Específicamente, oASIS depende del pivoteo diagonal, el cual puede fallar al no devolver aproximaciones precisas en ciertos contraejemplos y es numéricamente inestable en comparación con la factorización de Cholesky parcial con pivoteo.

Metodología
El artículo propone integrar el algoritmo RPCholesky (Cholesky Parcial con Pivoteo Aleatorio) en el marco de trabajo de KDMD para acelerar el cómputo mientras se mejora la estabilidad numérica.

1. Aproximación de Kernel mediante RPCholesky: En lugar de calcular la matriz Gramiana completa $G$ de $M \times M$ y resolver el problema de autovalores asociado, los autores utilizan RPCholesky para generar una aproximación de bajo rango $G \approx FF^*$. Este método selecciona índices de pivote $I = \{i_1, \dots, i_S\}$ basados en una distribución de probabilidad derivada de los elementos diagonales de la matriz residual, en lugar de utilizar una estrategia de pivoteo diagonal puramente codiciosa (greedy). Esto equilibra la "explotación" de los elementos diagonales grandes con la "exploración" de los más pequeños.
2. Integración Algorítmica: El KDMD propuesto con muestreo aleatorio (Algoritmo 2) reemplaza la descomposición de autovalores completa de $G$ por la descomposición de autovalores de la matriz más pequeña $F^*F$. Los factores resultantes se utilizan para construir la matriz de kernel reducida $\hat{K}$ y calcular los modos y autofunciones de DMD.
3. Residuales Basados en Datos: Un componente crítico de la metodología es la derivación de una fórmula de residual específica basada en datos para el entorno aleatorizado. Dado que el cálculo de residual estándar utilizado en el SVD-DMD no es directamente aplicable al resultado de KDMD aleatorizado, los autores derivan un nuevo residual $r(i)$ (Ecuación 7) que utiliza la información de selección de pivotes ($A[:, I]$ y $G[:, I]$) obtenida durante la ejecución de RPCholesky. Esto permite la clasificación y selección de los modos dominantes basados en su calidad de reconstrucción.
4. Optimización Computacional: Los autores señalan que para matrices de datos secuenciales $X$ e $Y$, las matrices de kernel pueden ensamblarse a partir de una única matriz más grande $D = [X, Y]$. Esto permite que el algoritmo RPCholesky se ejecute una sola vez sobre $D$, extrayendo los subbloques necesarios para $G$ y $A$, evitando así el costoso ensamblaje completo de estas matrices.

Contribuciones Clave

• Propuesta Algorítmica: El artículo introduce la aplicación del algoritmo RPCholesky a KDMD, ofreciendo una alternativa estable al algoritmo oASIS y a la aproximación Nyström con pivoteo diagonal.
• Estabilidad y Ordenamiento: Los autores demuestran que RPCholesky proporciona mejores garantías de estabilidad que los métodos previos de KDMD aleatorizado. Crucialmente, muestran que los residuales basados en datos derivados permiten un ordenamiento significativo de los modos de DMD, una característica que era inconsistente o errática con el pivoteo basado en oASIS.
• Análisis de Complejidad: El artículo proporciona un análisis de complejidad computacional que muestra que el enfoque de KDMD aleatorizado reduce el costo de $O(M^3)$ (para el KDMD estándar) a $O(SMN + S^2M + S^3)$, donde $S$ es el número de muestras aleatorias. Esto permite el procesamiento de conjuntos de datos donde $M$ es grande.
• Formulación de Residuales: La derivación de una métrica de residual específica para los modos de KDMD aleatorizado, permitiendo la selección de la dinámica dominante sin necesidad de requerir la matriz de kernel completa.

Resultados
La eficacia del método propuesto fue evaluada en tres problemas de referencia:

1. Flujo alrededor de un Cilindro: Utilizando datos de presión de una simulación de flujo laminar ($N=89351, M=150$), el KDMD basado en RPCholesky produjo modos visualmente similares al DMD estándar y al KDMD, con residuales comparables al KDMD estándar. En contraste, el método oASIS produjo residuales erráticos que no reflejaban el mismo comportamiento, impidiendo un ordenamiento efectivo de los modos.
2. Ecuación de Duffing No Forzada: Una prueba de estrés utilizando un conjunto de datos sintético ($10000 \times 7700$) mostró que los algoritmos de KDMD aleatorizado (RPCholesky, oASIS y RFF) lograron errores de reconstrucción relativa similares a medida que aumentaba el número de muestras $S$. Sin embargo, el método RPCholesky demostró una estabilidad superior en el ordenamiento de modos en comparación con oASIS. El análisis de tiempo computacional confirmó que todas las variantes aleatorizadas escalan de manera similar con respecto a $S$.
3. Conjunto de Datos de Temperatura de la Superficie del Mar: Aplicado a un conjunto de datos reales de gran escala ($2276$ instantáneas, $10^6$ puntos de datos), el KDMD basado en RPCholesky identificó con éxito los modos dominantes. Notablemente, los modos producidos por el algoritmo propuesto se adhirieron a la estructura física esperada (un primer modo independiente seguido de pares de complejos conjugados), mientras que el enfoque RFF EDMD no logró producir este ordenamiento por pares.

Significancia
El artículo sostiene que la combinación de RPCholesky y KDMD aborda las deficiencias específicas de estabilidad y ordenamiento de los métodos de kernel aleatorizados existentes. Al reemplazar el pivoteo diagonal codicioso por un muestreo aleatorio adaptativo, el método logra un equilibrio entre la explotación y la exploración de la información. La principal significancia radica en permitir que KDMD maneje un mayor número de instantáneas ($M$) con una estabilidad numérica mejorada y un mecanismo fiable para seleccionar los modos dominantes mediante residuales basados en datos, sin necesidad de ensamblar o almacenar las matrices de kernel completas de $M \times M$. Los autores posicionan esto como una herramienta viable para acelerar el análisis de sistemas dinámicos basados en datos a gran escala.