Randomized Methods for Kernelized DMD

Technical Summary: Randomized Methods for Kernelized DMD

Problem Statement
Dynamic Mode Decomposition (DMD) is a data-driven method used to extract dominant dynamics from sequential snapshots of nonlinear systems. However, applying DMD to large-scale datasets with high state dimensions ($N$) and large numbers of snapshots ($M$) presents a significant computational bottleneck. While Kernelized DMD (KDMD) mitigates the issue of large $N$ by utilizing the kernel trick, it introduces a new constraint: the algorithm requires solving two $M \times M$ eigenproblems. This results in poor scaling with respect to the number of snapshots, limiting KDMD's applicability to long trajectory datasets. Existing randomized approaches, such as Random Fourier Features (RFF) and algebraic methods like the oASIS algorithm, attempt to address this but suffer from slow convergence rates or numerical instability, respectively. Specifically, oASIS relies on diagonal pivoting, which can fail to return accurate approximations in certain counterexamples and is numerically unstable compared to pivoted partial Cholesky factorization.

Methodology
The paper proposes integrating the RPCholesky algorithm (Randomly Pivoted Partial Cholesky) into the KDMD framework to accelerate computation while enhancing numerical stability.

1. Kernel Approximation via RPCholesky: Instead of computing the full $M \times M$ Gramian matrix $G$ and solving the associated eigenproblem, the authors utilize RPCholesky to generate a low-rank approximation $G \approx FF^*$. This method selects pivot indices $I = \{i_1, \dots, i_S\}$ based on a probability distribution derived from the diagonal elements of the residual matrix, rather than using a purely greedy diagonal pivoting strategy. This balances the "exploitation" of large diagonal elements with the "exploration" of smaller ones.
2. Algorithmic Integration: The proposed KDMD with randomized sampling (Algorithm 2) replaces the full eigendecomposition of $G$ with the eigendecomposition of the smaller $S \times S$ matrix $F^*F$. The resulting factors are used to construct the reduced kernel matrix $\hat{K}$ and compute DMD modes and eigenfunctions.
3. Data-Driven Residuals: A critical component of the methodology is the derivation of a specific data-driven residual formula for the randomized setting. Since the standard residual calculation used in SVD-based DMD is not directly applicable to the randomized KDMD output, the authors derive a new residual $r(i)$ (Equation 7) that utilizes the pivot selection information ($A[:, I]$ and $G[:, I]$) obtained during the RPCholesky execution. This allows for the sorting and selection of dominant modes based on their reconstruction quality.
4. Computational Optimization: The authors note that for sequential data matrices $X$ and $Y$, the kernel matrices can be assembled from a single larger matrix $D = [X, Y]$. This allows the RPCholesky algorithm to be run once on $D$, extracting the necessary sub-blocks for $G$ and $A$, thereby avoiding the expensive full assembly of these matrices.

Key Contributions

• Algorithmic Proposal: The paper introduces the application of the RPCholesky algorithm to KDMD, offering a stable alternative to the oASIS algorithm and the Nyström approximation with diagonal pivoting.
• Stability and Ordering: The authors demonstrate that RPCholesky provides better stability guarantees than previous randomized KDMD methods. Crucially, they show that the derived data-driven residuals allow for a meaningful ordering of DMD modes, a feature that was inconsistent or erratic with oASIS-based pivoting.
• Complexity Analysis: The paper provides a computational complexity analysis showing that the randomized KDMD approach reduces the cost from $O(M^3)$ (for standard KDMD) to $O(SMN + S^2M + S^3)$, where $S$ is the number of random samples. This enables the processing of datasets where $M$ is large.
• Residual Formulation: The derivation of a specific residual metric for randomized KDMD modes, enabling the selection of dominant dynamics without requiring the full kernel matrix.

Results
The efficacy of the proposed method was evaluated on three benchmark problems:

1. Flow Around a Cylinder: Using pressure data from a laminar flow simulation ($N=89351, M=150$), the RPCholesky-based KDMD produced modes visually similar to standard DMD and KDMD, with residuals comparable to the standard KDMD. In contrast, the oASIS method produced erratic residuals that did not reflect the same behavior, preventing effective mode sorting.
2. Unforced Duffing Equation: A stress test using a synthetic dataset ($10000 \times 7700$) showed that the randomized KDMD algorithms (RPCholesky, oASIS, and RFF) achieved similar relative reconstruction errors as the number of samples $S$ increased. However, the RPCholesky method demonstrated superior stability in mode ordering compared to oASIS. Computational time analysis confirmed that all randomized variants scale similarly with respect to $S$.
3. Sea Surface Temperature Dataset: Applied to a large real-world dataset ($2276$ snapshots, $10^6$ data points), the RPCholesky KDMD successfully identified dominant modes. Notably, the modes produced by the proposed algorithm adhered to the expected physical structure (a standalone first mode followed by complex conjugate pairs), whereas the RFF EDMD approach failed to produce this pairwise ordering.

Significance
The paper claims that the combination of RPCholesky and KDMD addresses the specific stability and ordering drawbacks of existing randomized kernel methods. By replacing greedy diagonal pivoting with adaptive randomized sampling, the method achieves a balance between information exploitation and exploration. The primary significance lies in enabling KDMD to handle larger snapshot counts ($M$) with improved numerical stability and a reliable mechanism for selecting dominant modes via data-driven residuals, without the need to assemble or store the full $M \times M$ kernel matrices. The authors position this as a viable tool for accelerating KDMD in large-scale data-driven dynamical systems analysis.