精读笔记

Problem Setting

论文标题：Revisiting The PBH Test: Fast Uncontrollability Certificates via Krylov Methods（arXiv preprint / 2026-06-16）。

这篇论文真正处理的是“大规模 LTI 系统中给定目标 maneuver 的不可达性证明与诊断”，而不是一般意义上的 controllability 判定。输入是 (A,B)、有限 horizon N 和目标位移 Δx，问题是判断 Δx 是否属于 range(C_N)，若不属于，给出一个可验证的 dual certificate y，并从 y 中解释哪些不可控 PBH modes 阻塞了这个目标。

真正困难点在于：C_N 维度巨大且构造代价高；PBH 需要全局或区域谱信息，左特征向量在非正规或弱分离谱下可能病态；Gramian / least-squares 虽然直接对应 reachability，但在大规模稀疏系统里仍可能变成全局稠密对象。关键矛盾是：经典 controllability 是全局性质，但实际工程诊断常常只需要证明某个 target 不可达，并解释与该 target 相关的少数阻塞模式。论文试图利用这个 target-specific 性质避免全局谱分解。

Motivation

已有路线不够的地方不是理论不完整，而是计算对象过于全局。PBH 给出最干净的模态解释，但需要先找到相关左特征结构；controllability matrix / Gramian 给出可达子空间，但显式对象对大规模系统不友好；least-squares 可以 matrix-free，但若目标不可达，求残差本身不自动给出 PBH 级别的 modal explanation。

作者抓住的缺口是：优化 infeasibility certificate 通常只被当作“不可行证明”，没有被当作 spectral object 使用。对于 C_Nu=Δx，Fredholm alternative 产生的 y 正好是 reachable subspace 的正交分离向量；而 reachable subspace 的正交补在 LTI 系统里具有 A^T-invariant 结构。这使得 y 不只是几何证书，也天然嵌在 PBH 不可控左模态子空间中。这个观察把 convex duality 和 PBH modal analysis 接了起来。

Core Idea

核心思想可以概括为：不要先求系统不可控模态，再问目标是否受影响；而是先从目标不可达性生成一个 separating certificate，再只在这个 certificate 诱导的低维不变子空间里恢复模态。

理论上这成立，因为 Null(C_N^T) 在 N≥n 时等于不可控子空间的左侧表示，并且对 A^T 不变。任何 y∈Null(C_N^T) 都可以分解到 A^T 的 generalized eigenspaces；同时 y^TΔx≠0 保证这些模态确实与当前目标 maneuver 相关。相比传统 PBH 的 system-centric workflow，这里引入的 inductive bias 是 target-awareness：只解释当前 Δx 的 obstruction，而非枚举全部不可控结构。

scalability 的潜在来源也在这里：如果 certificate 只混合少数不可控模式，则 spectral extraction 的维度 r 远小于 n。注意这不是免费午餐；它把全局谱问题转移为“能否快速找到一个好 certificate”以及“certificate 的 cyclic subspace 是否低维且数值稳定”。

Method

方法层面最关键的不是两个算法本身，而是三个转换。

1. Reachability feasibility → dual infeasibility certificate。MECP 的能量目标其实不是重点，关键是约束 C_Nu=Δx。不可达等价于存在 y 使 C_N^T y=0 且 y^TΔx≠0。这个转换把不可控诊断从求解输入序列变为寻找分离方向。

2. Full C_N orthogonality → eigenvector plus B-orthogonality。直接检查 C_N^T y=0 仍然昂贵。作者用 shifted inverse iteration 在 A^T 上寻找近似左特征向量；如果 y 近似满足 A^T y≈λy 且 B^T y≈0，则 y^T A^kB≈λ^k y^TB≈0。也就是说，利用谱结构把对整个 controllability matrix 的正交性压缩为对 B 的正交性。这一步是算法加速的核心工程机制。

3. Mixed certificate → Krylov minimal polynomial。若 y 是多个不可控 generalized eigenvectors 的线性组合，则反复作用 A^T 会生成包含这些成分的 cyclic subspace。检测 Krylov 序列线性相关并拟合最小多项式，根就是参与该 certificate 的不可控 eigenvalues。这一步使得 modal extraction 不需要全局 eigendecomposition，而是在 certificate-local 的低维空间中完成。

Key Insight / Why It Works

最重要的 insight 是 Null(C_N^T) 的双重身份：它既是 reachability infeasibility 的 certificate space，也是 PBH 不可控左广义特征子空间。这个恒等关系让一个优化里的 dual ray 获得了 modal semantics。论文真正的贡献在于把这个关系明确计算化：certificate 不只是证明“到不了”，还告诉你“哪些不可控方向让它到不了”。

方法有效的本质不是更好的 rank test，而是 latent structure exploitation：LTI reachability 的正交补是 A^T-invariant，因此一个 target-induced vector y 可以生成小的 Krylov invariant/cyclic subspace。若这个子空间低维，后续提取自然便宜。这更接近 representation compression / local spectral probing，而不是单纯 scaling。

但 Alg. 1 的加速部分有明显 engineering 成分。shifted inverse iteration 本身是经典局部特征向量算法；用 Gershgorin bounds 生成 shifts 也只是粗覆盖。它的成功依赖于 shift 是否靠近不可控 target-relevant 模态，以及该模态是否能被 inverse iteration 数值稳定地抓到。这里没有强 completeness guarantee，因此 certificate search 是 one-sided。论文的理论保证主要说明“拿到的 certificate 是什么”，而不是“算法一定高效拿到 certificate”。

Alg. 2 的核心贡献比 Alg. 1 更干净：从 certificate 的 Krylov sequence 提取参与模态，确实是把 PBH 诊断限制到 target-local cyclic subspace。但它使用 polynomial root finding，这在 r 稍大、根聚集、非正规系统下会成为主要数值瓶颈。因此论文的最佳适用区间很明确：大 n、稀疏 A、目标只激发少数不可控模态、谱不过分聚集。超出这个区间，增益可能迅速变成不稳定的局部谱搜索。

Relation To Prior Work

最接近的技术谱系有三条：PBH modal controllability test、大规模 Krylov/eigenvalue methods、以及 convex optimization infeasibility certificates。论文的新意不在单独任何一条：PBH 早已有不可控左特征向量解释；Fredholm/Farkas 早已有 infeasibility certificate；Krylov 最小多项式提取也不是新数值线代。但把 infeasibility certificate 当作 PBH-relevant spectral object，并用它生成 target-local Krylov 子空间，这个组合是实质性的。

与传统 PBH 的本质区别是 target conditioning。PBH 通常回答系统有哪些不可控模态；本文回答当前 Δx 被哪些不可控成分阻塞。与 Gramian/rank 方法的区别是解释性：Gramian 或 C_N rank 能说明 reachable space，但不自然返回 PBH modes。与 sparse eigensolvers 的区别则更微妙：本文并没有摆脱 eigen-computation，而是把 eigen-computation 从 global A 转移到 certificate-guided local subspace。

所以这篇更像是“duality-guided modal diagnosis”而不是新的 controllability theorem。理论部分是已有概念的强连接，算法部分是经典 Krylov 工具在这个连接上的应用。

Dataset / Evaluation

实验使用 routing/traffic 风格的合成网络，构造为 A=blkdiag(A_ctrl,A_unc)，B 只作用于 controllable block，Δx 被设计为激发 uncontrollable coordinates。这个设置非常适合验证论文机制：确实存在清晰不可控子空间，certificate 应该能找到，extraction 应该能对上 planted eigenvalues。

评估支持了 scalability claim 的弱版本：在 n 到千级、稀疏结构下，certificate-based 方法比 full PBH、Gramian 和 least-squares 更快；extraction 能恢复不少 planted modes。它也验证了 y 的数值 certificate 条件，即 B^T y 小、y^TΔx 非零。

但 benchmark 没有充分验证更难的 claim：真实网络线性化下的非正规性、近不可控而非精确不可控、复杂 Jordan/clustered spectrum、目标只弱激发不可控方向时的鲁棒性。由于不可控结构是 block planted，问题相对干净；性能增益可能主要来自 scaling / sparse linear algebra / synthetic separability。文中未充分说明算法在非块对角、强耦合但秩亏的系统中是否同样稳定。

Limitation

最核心限制是 completeness 与 numerical robustness。

首先，Alg. 1 成功即证伪，但失败没有意义。有限 shift scan 不能保证覆盖所有 target-relevant uncontrollable modes；random initialization 和 inverse iteration 的收敛也可能被谱聚集、非正规性或近奇异 shift solve 影响。因此它不是 PBH 的完整替代，而是快速找到反例证书的启发式/半证书式流程。

其次，B^T y≈0 代替 C_N^T y≈0 依赖 y 足够接近 A^T eigenvector。若 y 是优化 solver 返回的一般 Null(C_N^T) 元素，它未必是单一 eigenvector；若 inverse iteration 残差不够小，这个 proxy 可能漏掉 A^kB 项的误差累积。论文没有系统量化 residual 到 certificate violation 的误差界。

第三，spectral extraction 的上限由 r 和 conditioning 决定。Krylov 矩阵 rank detection 本身对阈值敏感；最小多项式系数拟合与根求解在高阶、重根、近重根下都不稳定。文中承认 r≈几十是较可靠区间，这意味着方法适用于“少数模式阻塞”的场景，不适合大量不可控模态混合的全局诊断。

第四，实验增益归因不完全清楚。C+E 比 PBH 快，可能是因为只扫描少数 shifts、只提取部分 modes、benchmark 稀疏且 block-structured，而不是因为 certificate paradigm 在所有大规模系统上都更优。所谓“recover PBH modes”也不是完整 recovery：实验中并未恢复全部 planted modes。

Takeaway

• 1. 最值得迁移的 insight：infeasibility certificate 可以不只是 feasibility artifact，而是带有系统结构语义的对象。
• 对很多 control / optimization 问题，dual ray 可能同样能作为诊断入口。
• 2. 这篇真正推动的是 target-centric controllability diagnosis：从“系统是否可控”转向“这个 maneuver 为什么不可达”。
• 这在大规模网络控制中比全局 PBH 更接近实际需求。

一句话总结

这篇论文把 PBH 不可控模态诊断重构为 target-induced infeasibility certificate 的局部 Krylov 谱分析，是一条从全局 controllability test 走向可扩展、目标条件化反例证书的控制计算路线。