精读笔记

Problem Setting

论文研究的是低秩 PSD 矩阵优化中一个很具体但重要的问题：真实秩 r_A 未知时，实践上会选 r > r_A 的过参数化 BM factorization，但这种“更大模型”并不自动带来更快优化，反而会显著拖慢 GD。真正困难不是目标函数 1/4||YYᵀ-A||² 难写，而是 Y 同时承载方向和幅值，导致子空间识别、谱幅值估计、冗余维度消除被绑在同一动力系统里。以前方法要么要求 exact parameterization，要么用 scaled/preconditioned 更新缓解 conditioning，要么在 polar/Riemannian 形式上仍未完全解耦方向和幅值。关键矛盾是：未知秩需要过参数化保证表达能力，但过参数化在 BM 中会恶化鞍点逃逸和收敛动力学。

Motivation

已有路线缺的是一个能把“表达冗余”和“优化病态”分开的参数化。BM 的过参数化慢，本质上不是冗余维度本身有害，而是冗余维度进入了同一个 factor Y，使方向和 magnitude 相互污染。作者抓住的观察是：低秩 PSD recovery 的核心首先是找到 A 的 eigenspace；一旦子空间包含真实列空间，Θ = XᵀAX 基本给出正确幅值。因此，没必要让方向变量依赖一个尚未学好的幅值变量。DMD 的动机就是把低秩优化重新组织成子空间学习问题，而不是继续在 factor space 中让 GD 自己发现这种结构。

Core Idea

核心思想是显式做 direction–magnitude decomposition：把 Y 写成 X 和 Θ，优化对象从 YYᵀ 变成 XΘXᵀ，其中 X 在 Stiefel manifold 上表示方向子空间，Θ 表示在该子空间内的谱幅值。这个重参数化本身并不神奇；真正关键是作者进一步让 X 用 PCA surrogate 更新，而不是用原始 reconstruction loss 更新。这样方向学习只看 A 的主子空间结构，不被当前 Θ 的误差牵制。

这改变了信息流：BM 是方向和幅值互相决定，DMD 是方向先由 A 的谱结构驱动，幅值随后投影匹配。过参数化在这里不再只是额外自由度，而是增加随机初始子空间捕获真实 eigenspace 的概率和最小重叠。直觉上，r 越大，span(X₀) 越容易和 span(U) 有较好 overlap，鞍点逃逸阶段越短。因此它不是简单 scaling，而是通过参数化把 scaling 的收益导向了子空间覆盖。

Method

方法层面最重要的是三点。第一，DMD reformulation 用 XΘXᵀ 替代 YYᵀ，并把 Θ 从 PSD 放宽到 symmetric；它解决的是 BM 中方向/幅值耦合的问题，代价是引入 Stiefel 约束和一个对称幅值变量。第二，direction update 不沿 f(X,Θ) 的真实梯度，而沿 PCA surrogate 的 Riemannian gradient；这一步是核心，因为它让 X 的动力学接近子空间迭代/流形 PCA，避免了 Θ 未收敛时误导方向。第三，magnitude update 本质是 Θ 向 XᵀAX 收缩，μ=2 时近似直接设为当前子空间上的 Rayleigh quotient；它解决的是幅值无需长期优化的问题。

recursive DMD 是对 OP DMD 动力学的算法化解释：既然轨迹会按 A₀,A₁,... 逐步学习 eigenpair，就可以用 rank-1 DMD 反复抽取 leading eigenpair 并 deflate。它解决的是 OP DMD 每步维护 mr+r² 变量、每步代价随 r 增大的问题；但它把稳定性压力转移到 eigengap 和 deflation error 上。

Key Insight / Why It Works

最核心的 insight 是：低秩矩阵分解中的慢收敛主要来自 representation alignment 的失败，而不是幅值估计困难。DMD 有效是因为它把优化目标拆成两个时间尺度：X 只负责对齐 span(U)，Θ 只负责在已对齐子空间内拟合谱。理论中真正起作用的是 Φ_t = UᵀX_t 的 singular values 单调改善；一旦 principal angles 缩小，reconstruction error 自动下降。这比“换了一个优化器”更本质，是重新设计了参数化诱导的动力学。

OP DMD 的加速主要来自 better inductive bias + subspace coverage scaling。r 增大带来的收益不是模型表达能力更强，而是随机 Stiefel 子空间与真实 eigenspace 的最小奇异值更好，逃离低秩鞍点更快。这里的 overparameterization 是一种 randomized subspace amplifier。

saddle-to-saddle 分析最有价值的地方不是证明又有鞍点，而是说明 DMD 的轨迹仍然是 incremental spectral learning：每个 plateau 对应一个 best rank-ρ approximation，逃逸一次等价于学到一个新 eigenpair。这把 overparameterized dynamics 和 recursive deflation 联系起来。recursive DMD 则说明过参数化不是必要条件；它只是把 rank-by-rank curriculum 隐式并行化了。

可能只是辅助的部分是 Θ 的具体更新形式和一些复杂度常数；真正贡献在于 direction surrogate 与子空间对齐分析。实验中 matrix sensing/completion 的收益可能部分来自把 full-observation 下合理的 spectral surrogate 直接迁移过去，严格增益归因不清。

Relation To Prior Work

这篇最接近三条线：BM matrix factorization 的过参数化动力学、polar/Riemannian 低秩参数化、以及 GD 的 incremental/saddle-to-saddle spectral learning。和 BM-GD 的本质差异是，DMD 不让同一个因子同时学习方向和幅值；和 scaled GD / preconditioned methods 的差异是，它不是在原参数化里修 conditioning，而是改变参数化和梯度信息路径；和 RGD/PoLAR 类方法的差异是，它更彻底地把 direction update 从原始 loss 中抽离出来，用 PCA surrogate 直接驱动子空间。

看似新的 saddle-to-saddle 现象并不是全新，BM 和 matrix sensing 中已有 incremental learning 分析；新增的是在 DMD 下这个现象变得更透明，并被用来推出 recursive DMD。真正实质创新是把“过参数化导致慢”转化为“过参数化提高随机子空间覆盖”，并给出复杂度上随 r 增大改善的结论。它属于 parameterization-optimization co-design 的谱方法化分支，而不是普通的一阶优化改良。

Dataset / Evaluation

实验覆盖 matrix factorization、matrix sensing、matrix completion，任务范围能说明 DMD 思路不只在最简单 full-observation setting 下跑通。但这些实验都是合成低秩矩阵，谱结构、rank、condition number 都由作者控制，没有真实世界矩阵、噪声、模型错设或大规模稀疏系统验证。因此 evaluation 更支持“在理想谱结构下，DMD 的动力学符合理论”而不是支持广义低秩优化场景下的鲁棒优势。

实验确实验证了两个核心 claim：OP DMD 比 GD/RGD 更快，且增大 r 会加速；RE DMD 在 well-separated spectrum 下 wall-clock 可能更好，在不分离时变差。这些现象和理论机制一致。但 sensing/completion 部分更像 operator substitution 后的 empirical extension，文中未充分说明 surrogate gradient 在这些观测模型下何时仍等价于正确的 eigenspace learning。

Limitation

最大限制是理论成立的结构性前提很强：PSD 或 symmetric 目标、低秩精确结构、随机 Stiefel 初始化、可访问 A 或线性观测 operator、以及 recursive DMD 需要 eigengap。对于 noisy / approximately low-rank / indefinite / nonuniform sampling 的情况，方向 surrogate 是否仍然学到正确子空间并不清楚。

OP DMD 的 scalability 也有上限。每步需要维护 X∈R^{m×r}、Θ∈S^r，并做 Riemannian retraction；在 dense A 下主成本仍是 m²r 级。所谓 memory efficient 主要是相对 SDP 或 full matrix variable，不等于适合真正大规模矩阵。RE DMD 降低每步成本，但把问题转移到 sequential deflation：谱不分离时迭代数暴涨，误差传播也更难控制。

另一个限制是增益归因在实验上不完全干净。OP DMD 使用了专门为方向设计的 PCA surrogate，而 baseline GD/RGD 沿原始目标走；因此优势既来自 decomposition，也来自更强的 spectral prior。可以说它不是一个公平的“同目标优化器比较”，而是引入了额外问题结构。对矩阵分解这是合理 inductive bias，但对更一般低秩优化是否仍合理，文中未充分说明。

Takeaway

• 第一，低秩优化里参数化比优化器本身更关键；把方向和幅值混在一个 factor 中会制造不必要的动力学病态。
• 第二，过参数化是否有益取决于它是否改善 representation alignment；DMD 展示了一种让 overparameterization 变成 subspace coverage amplifier 的方式。
• 第三，saddle-to-saddle dynamics 可以被当成算法设计信号：如果隐式轨迹本来就是 rank-by-rank 学习，那么 recursive / deflation / block curriculum 可能是更省资源的显式版本。
• 第四，未来真正值得做的是把这种 direction surrogate 思想推广到 noisy sensing、completion、LoRA/foundation-model adaptation 等非理想谱结构中，并弄清楚何时 surrogate 仍是正确 bias。

一句话总结

Direction–Magnitude Decomposition 把低秩 BM 优化从耦合 factor dynamics 改造成子空间对齐优先的谱学习过程，真正贡献是说明过参数化可以通过正确参数化从优化负担变成鞍点逃逸加速器。