Finding Koopman Invariant Subspaces via Personalized PageRank¶

会议: NeurIPS 2026
arXiv: 2605.24666
OpenReview: https://openreview.net/forum?id=e6Buij6ykm
代码: https://anonymous.4open.science/r/Koopman-PageRank-C8D3/
领域: 学习理论
关键词: 库普曼算子, 扩展动态模态分解, 个性化PageRank, 不变子空间, 字典学习

一句话总结¶

针对非线性动力系统高维字典扩展动态模态分解（EDMD）中子空间截断与泄漏问题，本文证明了 Koopman 不变子空间在有限样本下必然诱导 EDMD 矩阵的零块结构，并提出将行归一化 EDMD 矩阵重构为 Markov 链、利用个性化 PageRank（PPR）精确检测不变子空间与控制多步泄漏误差。

研究背景与动机¶

非线性动力系统的长期演化预测与建模一直面临初值极端敏感、分岔和混沌吸引子等本质困难。Koopman 算子理论通过将状态空间中的非线性动力学提升到可观测量（observables）构成的无限维希尔伯特空间，实现了全局严格的线性化表征。在计算实践中，扩展动态模态分解（EDMD）通过将算子投影到由有限个基函数构成的初始候选字典（如多元高阶多项式、径向基函数等）上，利用最小二乘法估计有限维转移矩阵。然而，当初始字典维度很大时，EDMD 矩阵往往严重病态且易引发谱污染，而盲目增加字典规模并不能保证逼近误差单调下降；反之，若字典过小则无法封闭系统动力学。

这一矛盾的根源在于：理想的紧凑字典所张成的子空间必须是 Koopman 不变的（即算子作用在子空间内不发生外泄）。但在实践中，从包含数百乃至数千个候选可观测量的庞大初始集合中，通过穷举搜索寻找极小的不变子字典在组合爆炸意义下是不可行的（$\binom{\tilde{N}}{N}$ 复杂度）。以往方法（如基于主角度压缩、子空间迭代剪枝或深度神经网络隐空间学习）要么破坏了原始基函数的显式物理可解释性，要么缺乏严格的有限样本统计收敛与扰动误差理论保障。

本文的切入角度是深入探究 EDMD 矩阵的分块结构与不变子空间之间的代数与图动力学联系。作者发现，任何生成不变子空间的子字典即使在有限数据样本下，也必然使 EDMD 矩阵的非对角耦合块严格为零。核心 idea：将行归一化的 EDMD 矩阵转置视为可观测量网络上的有向马尔可夫链转移概率核，以重点预测的目标状态变量作为种子节点运行个性化 PageRank（PPR），利用随机游走在封闭子空间内的测度集中效应精确剪枝并排序可观测量，从而无组合搜索地提取出紧凑、可解释且具有有限样本统计界与多步泄漏控制界的最优子字典。

方法详解¶

整体框架¶

算法以大规模候选可观测量集合 $\mathcal{D}_{\tilde{N}} = \{\psi_1, \dots, \psi_{\tilde{N}}\}$、目标子字典尺寸 $N$、感兴趣的目标预测可观测量种子集合 $\mathcal{S} \subset \{1,\dots,\tilde{N}\}$ 以及阻尼因子 $\alpha \in (0,1)$ 为输入。整体计算流程分为四步：首先基于采样数据对计算大字典的原始 EDMD 矩阵 $K_{\tilde{N},M}$；接着对转置的绝对值矩阵 $|K_{\tilde{N},M}^{\top}|$ 进行逐行归一化，构建可观测量网络上的行随机转移矩阵 $P$；随后在此马尔可夫链上以 $\mathcal{S}$ 为种子偏好向量运行多步个性化 PageRank 算法，获得平稳分布测度向量 $\pi_{\mathcal{S},M}$ 并依得分从高到低选取前 $N$ 个关键可观测量构成子字典 $\mathcal{D}_N$；最后在精选的子字典上重新计算紧凑 EDMD 矩阵 $K_{N,M}$ 给出闭环动力学预测。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["候选大字典 D_N~ + 动力学数据对 (X, Y)"] --> B["计算全维 EDMD 矩阵<br/>K_N~,M = Psi(X)+ Psi(Y)"]
    B --> C["构建可观测量马尔可夫转移矩阵<br/>P = R(|K_N~,M^T|) 逐行归一化"]
    C --> D["种子驱动的个性化 PageRank 排序<br/>计算稳态向量 pi_S,M 并截取 Top-N 得分"]
    D --> E["子空间重构与低维动力学闭环<br/>在精选子字典 D_N 上重算紧凑 K_N,M"]
    E --> F["输出紧凑可解释子字典与低秩预测模型"]

关键设计¶

1. EDMD 矩阵分块零结构与不变子空间的严格对应

以往研究多在无限数据极限下讨论 Galerkin 投影性质，而本文证明了在有限样本观测下的严格代数恒等性。当初始大字典 $\mathcal{D}_{\tilde{N}}$ 中存在某个大小为 $N$ 的子集 $\mathcal{D}_N$ 张成严格的 Koopman 不变子空间 $\mathcal{F}_N$ 时，将对应可观测量的列调整至前部，由分块数据评估矩阵 $\mathbf{\Psi}_{\tilde{N}}(\mathbf{X}) = [\mathbf{\Psi}_N(\mathbf{X})\quad \mathbf{\Psi}_{N_2}(\mathbf{X})]$ 及相应的 Moore-Penrose 伪逆和 Schur 补矩阵展开可知： $$K_{\tilde{N},M} = \begin{bmatrix} K_{\tilde{N},M}^{11} & K_{\tilde{N},M}^{12} \\ K_{\tilde{N},M}^{21} & K_{\tilde{N},M}^{22} \end{bmatrix} = \begin{bmatrix} K_{N,M} & K_{\tilde{N},M}^{12} \\ O_{(\tilde{N}-N)\times N} & K_{\tilde{N},M}^{22} \end{bmatrix}$$ 只要数据评估矩阵满足满列秩条件（Assumption 1），其左下角耦合块 $K_{\tilde{N},M}^{21}$ 必然恒等于零，且左上角子块与单独用 $\mathcal{D}_N$ 拟合的 $K_{N,M}$ 完全恒等。更进一步，对于仅近似不变的子空间，正交基下的单步演化 $L^2$ 逼近误差满足： $$\sum_{i=1}^N \|\mathcal{K}\psi_i - \mathcal{K}_{N,M}\psi_i\|_{L^2}^2 \le 2\left(\|K_{\tilde{N},M}^{21}\|_F^2 + \|K^{\text{true}}[(\tilde{N}+1):\infty, 1:\tilde{N}]\|_F^2\right) + \varepsilon$$ 这证明了极小化非对角块 $\|K_{\tilde{N},M}^{21}\|_F$ 就是在数据驱动意义下最小化子空间泄漏与预测误差的充要代数代理。

2. 可观测量耦合网络建模与个性化 PageRank 测度集中

为了避免组合级排列枚举，本文定义行随机矩阵 $P = \mathcal{R}(|K_{\tilde{N},M}^{\top}|)$，其转移概率 $P[i,j] \propto |K_{\tilde{N},M}[j,i]|$ 精确刻画了在单步算子推进下从可观测量 $\psi_i$ 到 $\psi_j$ 的耦合强度。当左下块为零时，转置矩阵的右上块 $P^{12}$ 严格为零，使得子字典 $\mathcal{D}_N$ 在该随机游走网络中构成一个“吸收/不可逆外泄的闭合社区”。给定种子集 $\mathcal{S}$（如需要预测的物理坐标），PPR 的稳态分布方程为： $$\pi_{\mathbf{s}}^{\top} = (1-\alpha)\mathbf{s}^{\top}(I - \alpha P)^{-1}$$ 相比于全图均匀瞬移的标准 PageRank（PR），PPR 具有双重优势：其一，标准 PR 要求内部块满足严格的混合谱隙条件，遇到不接收块内入边的“匮乏节点（starved node）”时检测窗口迅速坍缩；而 PPR 仅需弱得多的图可达性（reachability）条件，即种子集能够通过正向路径到达目标块内每个节点，即可在任意阻尼因子 $\alpha \in (0,1)$ 下保证子字典内的得分严格大于子字典外部的任意节点（即间隙 $\Delta_{\text{PPR}} > 0$）；其二，PPR 彻底消除了均匀瞬移引入的背景方差偏移。

3. 有限样本扰动理论与无假设多步泄漏控制界

结合矩阵 Bernstein 不等式对样本协方差的集中性刻画与 PageRank 预解式摄动理论，定理 4 给出了有限样本端到端误差界：当样本量 $M \gtrsim \tilde{N}^2 \log(\tilde{N}/\rho)$ 时，经验 PPR 向量 $\pi_M$ 与总体无泄漏理想向量 $\pi_{\text{pop}}^{(0)}$ 的 $\ell_1$ 距离以 $\mathcal{O}(1/\sqrt{M})$ 的速率收敛： $$\|\pi_M - \pi_{\text{pop}}^{(0)}\|_1 \le \frac{2\alpha(\varepsilon_0 + \varepsilon_M)}{(1-\alpha)r_{\min}^{(0)}}$$ 由此导出的样本复杂度表明，PPR 在 $\alpha=1/2$ 时即可消除对极值阻尼的依赖，其所需样本量显著低于标准 PR。尤为关键的是，即便系统在给定的候选基底中根本不存在严格的不变子空间，命题 9 仍证明了任意选定子字典 $S_N$ 的 $\gamma$ 折现多步泄漏上界直接由该子字典外部的 PPR 质量所严格控制： $$\Lambda_{\mathbf{s}}^{\gamma}(S_N) \coloneqq (1-\gamma)\sum_{k=1}^{\infty}\gamma^k \sum_{j\notin S_N}[\mathbf{s}^{\top}|K_{\tilde{N},M}^{\top}|^k]_j \le \frac{1-\gamma}{1-\alpha}\left(1 - \pi_{\mathbf{s},M}(S_N)\right)$$ 其中 $\gamma = \alpha / \|K_{\tilde{N},M}^{\top}\|_{\infty}$。该结论为使用 PPR 截取高分节点提供了无需任何不变性先验假设的纯预测精度保证。

损失函数 / 训练策略¶

算法首先在全字典 $\mathcal{D}_{\tilde{N}}$ 上通过标准无偏最小二乘回归求解 $K_{\tilde{N},M} = \mathbf{\Psi}_{\tilde{N}}(\mathbf{X})^{+} \mathbf{\Psi}_{\tilde{N}}(\mathbf{Y})$。求得转移阵 $P$ 后，利用幂迭代法（Power Iteration）或预解式线性方程组求解 PPR 向量 $\pi_{\mathcal{S},M}$。得到排名前 $N$ 的可观测量后，丢弃其余维度，重新在数据矩阵 $\mathbf{\Psi}_N(\mathbf{X}), \mathbf{\Psi}_N(\mathbf{Y})$ 上做投影最小二乘求解紧凑矩阵 $K_{N,M}$。实验中对连续动力学系统采用 Runge-Kutta 步长离散化采集快照，阻尼因子在无先验时取经典值 $\alpha=0.85$ 或理论最优简化值 $\alpha=0.5$。

实验关键数据¶

主实验¶

论文在四类复杂动力学系统上进行了系统评估：Duffing 振荡器、Van der Pol 振荡器、Lorenz 混沌系统以及三势阱 Ramachandran 分子动力学模型。下表列出了三势阱 Ramachandran 动力学（初始 $\tilde{N}=236$ 维混合基底，包含 4 个环形状态坐标、28 个单变量傅里叶模态、64 个交叉项、40 个对角傅里叶项以及 100 个网格高斯 RBF，总样本 $M=10^5$，20 次独立随机重复）在不同选定子字典规模 $N$ 下，各排序方法相对于随机均匀排序（Random Ordering）的单步预测误差比值（数值低于 1.0 表示优于随机基准）：

方法	N=5 误差比值	N=10 误差比值	N=20 误差比值	说明
PPR (本文方法)	0.30 ± 0.04	0.38 ± 0.06	0.55 ± 0.08	在极小字典 (N=5) 下降低 70% 误差，全尺度优势显著
PCCA+	0.68 ± 0.11	0.77 ± 0.14	0.99 ± 0.16	粗粒化谱聚类在小尺寸有效，大尺寸逼近随机
TICA	0.94 ± 0.15	1.06 ± 0.19	1.44 ± 0.24	仅关注慢变量特征，较大尺寸出现性能严重恶化
标准 PR	1.09 ± 0.18	1.18 ± 0.21	1.33 ± 0.22	缺乏局部聚焦，均匀瞬移带来严重噪声污染

消融实验与结构分析¶

通过三状态理论玩具模型（Example A 与 Example B）系统分析了可容忍最大外泄量 $\epsilon^{\max}$ 与内部混合性/匮乏节点的影响：

理论场景配置	拓扑特性	标准 PR 容忍泄漏上限 $\epsilon_{\text{PR}}^{\max}$	PPR 容忍泄漏上限 $\epsilon_{\text{PPR}}^{\max}$	优势倍数	说明
Example A (良好混合内部块)	内部完全可约双向连通循环	0.125 ($1/8$)	0.250 ($1/4$)	2.0×	PPR 允许双倍的外泄扰动仍能严格识别子空间
Example B (存在匮乏节点)	节点2无内部入边 (Starved)	0.042 ($1/24$)	0.250 ($1/4$)	6.0×	PR 因混合性破坏窗口骤缩，PPR 仅依可达性保持宽容限

在 Duffing 振荡器（90 阶双变量 Laguerre 多项式，真实不变子空间包含状态多项式）实验中，PPR 在仅选择 $N=5$ 个可观测量时即达到了 $\sim 10^{-12}$ 量级的超低单步预测误差；对比对称子空间分解算法（TSSD），TSSD 在精度参数 $\epsilon \in [0,1]$ 网格扫描下仅能粗糙检出 $N=3, 45, 65$ 三种离散尺寸，完全缺乏细粒度剪枝灵活性。

在 Lorenz 混沌吸引子谱分析中，PPR 在截断尺寸仅为 $N=30 \sim 60$ 时即可高度保真地复现包裹在不稳定周期轨道周围的 $\approx 6\,\text{rad/s}$ 特征赝本征函数（pseudo-eigenfunctions），而传统增量升阶排序（Incremental Ordering）则至少需要 $N \ge 120$ 才能捕捉该振荡拓扑。

关键发现¶

种子驱动的物理可解释性涌现：在 Ramachandran 势能实验中，以 4 个状态坐标为种子时，PPR 评分呈现出极为鲜明的“两级阶梯结构”——排名前 4 位为状态坐标本身（占总权重约 17%），紧随其后的均为分布在势阱鞍点与过渡边界处的 Gaussian RBF 基函数。这一现象在物理上极度自洽：状态坐标表征宏观亚稳态，而鞍点边界 RBF 则精确捕捉了势阱间的瞬态跃迁动力学。
混合条件与可达条件的本质分离：实验与理论一致表明，标准 PR 对字典的连通混合度存在严苛依赖；若某个必要的可观测量在图结构中处于“源节点”或“少入边”状态，标准 PR 会因无法积累瞬移外的随机游走权重而遗漏该特征。PPR 将依赖条件削弱为从种子出发的有向通路可达性，彻底解决了这一瓶颈。
避免高维过拟合与谱污染：传统 EDMD 随着可观测量增加容易受噪声微扰放大形成虚假特征值（spurious eigenvalues），而 PPR 挑选出的紧凑子字典在较长预测步长（如 20 步多步外推）下均保持了稳定无发散的轨迹追踪精度。

亮点与洞察¶

将算子代数结构转化为有向图流形：创造性地利用行归一化转置将矩阵回归问题重塑为离散 Markov 游走过程，巧妙绕过了 $\binom{\tilde{N}}{N}$ 的 NP-hard 组合搜寻难题。
有限样本下的零块不变量发现：严格证明了 Koopman 不变子空间在有限样本下的零块代数精确性（无需数据趋于无穷），为基于数据块范数的剪枝提供了坚实的第一性原理依据。
无假设折现多步泄漏上界：证明了 PPR 测度在子字典外的分布直接绑定了任意多步动态外泄误差，使得该算法即使在复杂的现实非线性系统（不存在闭合不变子空间）中也能具备强大的鲁棒性。

局限与展望¶

确定性与独立同分布假设约束：现有有限样本集中性证明（Theorem 4）严格依赖于样本对独立同分布且系统为确定性动力学的假设；虽然在 Lorenz（遍历吸引子连续轨迹）和 Ramachandran（过阻尼 Langevin 随机动力学）实验中表现优异，但严格的随机系统与遍历时间序列理论扩展仍属开放课题。
行归一化的模长信息折损：在步骤 2 中对转置矩阵按行除以行模长时，丢弃了不同可观测量的绝对尺度量纲差异，使得折现泄漏界可能在某些尺度悬殊的系统中不够紧致。
阻尼因子自适应选择：目前阻尼因子 $\alpha$ 多设定为经验常数（如 0.85 或 0.5），未来针对特定动力学时间尺度自动调节最佳 $\alpha$ 具有重要价值。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将 Personalized PageRank 引入 Koopman 算子不变子空间辨识，揭示了零块矩阵结构与 Markov 闭合链之间的深刻对偶性。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖解析振荡器、混沌吸引子及高维分子势阱系统，兼具谱分析、多步外推与理论极限算例验证。
写作质量: ⭐⭐⭐⭐⭐ 逻辑层层推进，定理推导详实，主干叙述与附录证明自洽紧凑。
价值: ⭐⭐⭐⭐⭐ 为困扰数据驱动动力学领域的“高维字典 curse of dimensionality”提供了兼具理论保证与极低计算开销的通用解决框架。

理论场景配置	拓扑特性	标准 PR 容忍泄漏上限 \(\epsilon_{\text{PR}}^{\max}\)	PPR 容忍泄漏上限 \(\epsilon_{\text{PPR}}^{\max}\)	优势倍数	说明
Example A (良好混合内部块)	内部完全可约双向连通循环	0.125 (\(1/8\))	0.250 (\(1/4\))	2.0×	PPR 允许双倍的外泄扰动仍能严格识别子空间
Example B (存在匮乏节点)	节点2无内部入边 (Starved)	0.042 (\(1/24\))	0.250 (\(1/4\))	6.0×	PR 因混合性破坏窗口骤缩，PPR 仅依可达性保持宽容限