Randomized Methods for Kernelized DMD

Resumo Técnico: Métodos Aleatórios para KDMD (Decomposição de Modos Dinâmicos Kernelizada)

Definição do Problema
A Decomposição de Modos Dinâmicos (DMD) é um método baseado em dados usado para extrair a dinâmica dominante de sistemas não lineares sequenciais. No entanto, aplicar a DMD a conjuntos de dados de grande escala com dimensões de estado elevadas ($N$) e um grande número de instantâneos ($M$) apresenta um gargalo computacional significativo. Embora a KDMD (Duts de Modos Dinâmicos Kernelizada) mitigue o problema do $N$ elevado ao utilizar o truque do kernel, ela introduz uma nova restrição: o algoritmo requer a resolução de dois problemas de autovalores de ordem $M \times M$. Isso resulta em uma escalabilidade deficiente em relação ao número de instantâneos, limitando a aplicabilidade da KDMD a conjuntos de dados de trajetórias longas. Abordagens aleatórias existentes, como as Características de Fourier Aleatórias (RFF) e métodos algébricos como o algoritmo oASIS, tentam abordar isso, mas sofrem com taxas de convergência lentas ou instabilidade numérica, respectivamente. Especificamente, o oASIS depende de pivoteamento diagonal, que pode falhar ao retornar aproximações precisas em certos contraexemplos e é numericamente instável em comparação com a fatoração de Cholesky parcial com pivoteamento.

Metodologia
O artigo propõe a integração do algoritmo RPCholesky (Cholesky Parcial com Pivoteamento Aleatório) à estrutura da KDMD para acelerar o cálculo, ao mesmo tempo em que aumenta a estabilidade numérica.

1. Aproximação de Kernel via RPCholesky: Em vez de calcular a matriz Gramiana $M \times M$ completa $G$ e resolver o problema de autovalores associado, os autores utilizam o RPCholesky para gerar uma aproximação de baixo posto $G \approx FF^*$. Este método seleciona índices de pivô $I = \{i_1, \dots, i_S\}$ baseados em uma distribuição de probabilidade derivada dos elementos diagonais da matriz residual, em vez de usar uma estratégia puramente gananciosa de pivoteamento diagonal. Isso equilibra a "explotação" de grandes elementos diagonais com a "exploração" de elementos menores.
2. Integração Algorítmica: A proposta de KDMD com amostragem aleatória (Algoritmo 2) substitui a autodecomposição completa de $G$ pela autodecomposição da matriz menor $F^*F$. Os fatores resultantes são usados para construir a matriz de kernel reduzida $\hat{K}$ e calcular os modos de DMD e autofunções.
3. Resíduos Baseados em Dados: Um componente crítico da metodologia é a derivação de uma fórmula de resíduo específica baseada em dados para o cenário aleatório. Como o cálculo de resíduo padrão usado no SVD-DMD não é diretamente aplicável ao output da KDMD aleatorizada, os autores derivam um novo resíduo $r(i)$ (Equação 7) que utiliza a informação de seleção de pivô ($A[:, I]$ e $G[:, I]$) obtida durante a execução do RPCholesky. Isso permite a ordenação e seleção de modos dominantes com base em sua qualidade de reconstrução.
4. Otimização Computacional: Os autores observam que, para matrizes de dados sequenciais $X$ e $Y$, as matrizes de kernel podem ser montadas a partir de uma única matriz maior $D = [X, Y]$. Isso permite que o algoritmo RPCholesky seja executado uma única vez em $D$, extraindo os subblocos necessários para $G$ e $A$, evitando assim a montagem completa e dispendiosa dessas matrizes.

Principais Contribuições

• Proposta Algorítmica: O artigo introduz a aplicação do algoritmo RPCholesky à KDMD, oferecendo uma alternativa estável ao algoritmo oASIS e à aproximação Nyström com pivoteamento diagonal.
• Estabilidade e Ordenação: Os autores demonstram que o RPCholesky fornece melhores garantias de estabilidade do que os métodos anteriores de KDMD aleatórios. Crucialmente, eles mostram que os resíduos derivados baseados em dados permitem uma ordenação significativa dos modos de DMD, uma característica que era inconsistente ou errática com o pivoteamento baseado em oASIS.
• Análise de Complexidade: O artigo fornece uma análise de complexidade computacional mostrando que a abordagem de KDMD aleatorizada reduz o custo de $O(M^3)$ (para a KDMD padrão) para $O(SMN + S^2M + S^3)$, onde $S$ é o número de amostras aleatórias. Isso permite o processamento de conjuntos de dados onde $M$ é grande.
• Formulação de Resíduo: A derivação de uma métrica de resíduo específica para os modos de KDMD aleatorizada, permitindo a seleção de dinâmicas dominantes sem a necessidade da matriz de kernel completa.

Resultados
A eficácia do método proposto foi avaliada em três problemas de referência:

1. Fluxo ao Redor de um Cilindro: Usando dados de pressão de uma simulação de fluxo laminar ($N=89351, M=150$), a KDMD baseada em RPCholesky produziu modos visualmente semelhantes ao DMD e KDMD padrão, com resíduos comparáveis ao KDMD padrão. Em contraste, o método oASIS produziu resíduos erráticos que não refletiam o mesmo comportamento, impedindo a ordenação eficaz dos modos.
2. Equação de Duffing Não Forçada: Um teste de estresse usando um conjunto de dados sintético ($10000 \times 7700$) mostrou que os algoritmos de KDMD aleatorizada (RPCholesky, oASIS e RFF) alcançaram erros de reconstrução relativa similares conforme o número de amostras $S$ aumentava. No entanto, o método RPCholesky demonstrou superior estabilidade na ordenação de modos em comparação ao oASIS. A análise de tempo computacional confirmou que todas as variantes aleatorizadas escalam de forma semelhante em relação a $S$.
3. Conjunto de Dados de Temperatura da Superfície do Mar: Aplicado a um conjunto de dados real de grande escala ($2276$ instantâneos, $10^6$ pontos de dados), a KDMD baseada em RPCholesky identificou com sucesso os modos dominantes. Notavelmente, os modos produzidos pelo algoritmo proposto aderiram à estrutura física esperada (um primeiro modo isolado seguido por pares complexos conjugados), enquanto a abordagem RFF EDMD falhou em produzir essa ordenação de pares.

Significância
O artigo afirma que a combinação de RPCholesky e KDMD aborda as deficiências específicas de estabilidade e ordenação dos métodos de kernel aleatórios existentes. Ao substituir o pivoteamento diagonal ganancioso pela amostragem aleatória adaptativa, o método alcança um equilíbrio entre explotação e exploração de informação. A principal significância reside em permitir que a KDMD lide com contagens de instantâneos ($M$) maiores com melhor estabilidade numérica e um mecanismo confiável para selecionar modos dominantes via resíduos baseados em dados, sem a necessidade de montar ou armazenar as matrizes de kernel $M \times M$ completas. Os autores posicionam isso como uma ferramenta viável para acelerar a KDMD na análise de sistemas dinâmicos baseados em dados de grande escala.