Randomized Methods for Kernelized DMD

技术摘要：用于核化 DMD 的随机化方法

问题陈述
动态模式分解（DMD）是一种用于从非线性系统的序列快照中提取主导动力学的数据驱动方法。然而，将 DMD 应用于具有高状态维度 ($N$) 和大量快照数量 ($M$) 的大规模数据集时，面临着显著的计算瓶颈。虽然核化 DMD (KDMD) 通过利用核技巧缓解了 $N$ 过大的问题，但它引入了一个新的约束：算法需要求解两个 $M \times M$ 的特征问题。这导致其对快照数量的扩展性较差，限制了 KDMD 在长轨迹数据集上的适用性。现有的随机化方法，如随机傅里叶特征 (RFF) 和代数方法（如 oASIS 算法），试图解决这一问题，但前者存在收敛速度慢的问题，而后者则存在数值不稳定的问题。具体而言，oASIS 依赖于对角线枢轴选择（diagonal pivoting），这在某些反例中可能无法返回准确的近似值，且与经过枢轴部分 Cholesky 分解（pivoted partial Cholesky factorization）相比在数值上不够稳定。

方法论
本文建议将 RPCholesky 算法（随机枢轴部分 Cholesky）集成到 KDMD 框架中，以加速计算并增强数值稳定性。

1. 通过 RPCholesky 进行核近似： 与计算完整的 $M \times M$ Gramian 矩阵 $G$ 并求解相关的特征问题不同，作者利用 RPCholesky 生成低秩近似 $G \approx FF^*$。该方法根据基于残差矩阵对角元素的概率分布来选择枢轴索引 $I = \{i_1, \dots, i_S\}$，而不是使用纯粹的贪婪对角线枢轴策略。这平衡了对大对角元素的“利用”（exploitation）与对较小元素的“探索”（exploration）。
2. 算法集成： 提出的带有随机采样功能的 KDMD（算法 2）使用较小的 $S \times S$ 矩阵 $F^*F$ 的特征分解来替代 $G$ 的全特征分解。所得因子用于构建缩减后的核矩阵 $\hat{K}$ 并计算 DMD 模态和特征函数。
3. 数据驱动残差： 方法论的一个关键组成部分是推导出一种针对随机化设置的特定数据驱动残差公式。由于标准 SVD-DMD 中使用的标准残差计算并不直接适用于随机化 KDMD 输出，作者推导出了一个新的残差 $r(i)$（等式 7），该残差利用了在 RPCholesky 执行过程中获得的枢轴选择信息（$A[:, I]$ 和 $G[:, I]$）。这使得能够根据重建质量对主导模态进行排序和选择。
4. 计算优化： 作者指出，对于序列数据矩阵 $X$ 和 $Y$，核矩阵可以从单个更大的矩阵 $D = [X, Y]$ 中组装而成。这使得 RPCholesky 算法可以在 $D$ 上运行一次，从而提取出 $G$ 和 $A$ 所需的子块，避免了这些矩阵的高昂组装成本。

核心贡献

• 算法提案： 本文引入了将 RPCholesky 算法应用于 KDMD 的方法，为 oASIS 算法和使用对角线枢轴的 Nyström 近似提供了一种稳定的替代方案。
• 稳定性与排序： 作者证明了 RPCholesky 提供了比以往随机化 KDMD 方法更好的稳定性保证。至关重要的是，他们展示了推导出的数据驱动残差能够实现有意义的 DMD 模态排序，而这一特性在基于 oASIS 的枢轴法中是不一致或不稳定的。
• 复杂度分析： 本文提供了计算复杂度分析，表明随机化 KDMD 方法将成本从 $O(M^3)$（标准 KDMD）降低到 $O(SMN + S^2M + S^3)$，其中 $S$ 是随机样本数。这使得处理 $M$ 较大的数据集成为可能。
• 残差公式化： 推导出一种针对随机化 KDMD 模态的特定残差度量，从而能够在不需要完整核矩阵的情况下选择主导动力学。

结果
所提方法的有效性在三个基准问题上得到了评估：

1. 绕圆柱流动： 使用层流模拟中的压力数据（$N=89351, M=150$），基于 RPCholesky 的 KDMD 生成的模态在视觉上与标准 DMD 和 KDMD 相似，且残差与标准 KDMD 相当。相比之下，oASIS 方法产生的残差表现出不规则行为，未能反映相同的行为，从而阻碍了有效的模态排序。
2. 无强迫 Duffing 方程： 使用合成数据集（$10000 \times 7700$）进行的压力测试显示，随着样本数 $S$ 的增加，随机化 KDMD 算法（RPCholesky、oASIS 和 RFF）达到了相似的相对重建误差。然而，与 oASIS 相比，RPCholesky 方法在模态排序方面表现出更优越的稳定性。计算时间分析确认，所有随机化变体在关于 $S$ 的扩展性方面表现相似。
3. 海表温度数据集： 应用于一个大型真实数据集（$2276$个快照，$10^6$ 个数据点），基于 RPCholesky 的 KDMD 成功识别了主导模态。值得注意的是，所提算法生成的模态符合预期的物理结构（一个独立的第一个模态，随后是共轭复数对），而 RFF EDMD 方法则未能产生这种成对排序。

意义
本文声称，RPCholesky 与 KDMD 的结合解决了现有随机化核方法在稳定性与排序方面的缺陷。通过用自适应随机采样取代贪婪对角线枢轴，该方法实现了信息利用与探索之间的平衡。其主要意义在于使 KDMD 能够处理具有更大快照计数（$M$）的数据集，同时提供改进的数值稳定性以及通过数据驱动残差选择主导动力学的可靠机制，且无需组装或存储完整的 $M \times M$ 核矩阵。作者将其定位为加速大规模数据驱动动力系统分析中 KDMD 计算的有效工具。