An Improved Incremental Singular Value Decomposition and New Error Bounds

技术摘要：一种改进的增量奇异值分解与新误差界

问题陈述
增量奇异值分解（SVD）最初由 Brand [2, 3] 提出，并由 Fareed 等人 [10] 推广至加权内积情形，是流数据场景下低秩近似的标准方法，适用于无法存储完整矩阵的情况。该算法在新增列到达时更新截断 SVD（$U \approx Q\Sigma R^\top$）。然而，在浮点运算中，每次更新都会将运行奇异基 $Q$ 乘以一个小的正交因子。虽然单次乘法在舍入误差范围内保持正交性，但这些误差会随流长度 $n$ 累积。最终，$Q$ 会丧失数值正交性，导致奇异值不准确且截断准则不可靠。

标准补救措施是定期执行重正交化（例如通过修正 Gram–Schmidt 方法），在正交性退化时触发。然而，为维持指定精度水平所需的频率一直是一个未解之谜。正如 Brand [3, p. 28] 所指出的，尚不清楚需要多频繁地进行重正交化才能保证特定的整体数值精度水平，尤其是在重正交化计算代价高昂的加权设置中（例如有限元本征正交分解）。

方法论
作者提出了一种对增量 SVD 算法的重构，推迟对运行奇异因子的更新。核心方法论基于两个观察：

1. 秩非增主导性：在低秩应用中，大多数输入列位于当前子空间内（残差 $< \text{tol}$）。这些“秩非增”列不会扩展子空间。
2. 批处理：$s$ 个连续秩非增列的累积效应，可以通过对包含投影系数的短而宽的缓冲矩阵进行一次瘦 SVD 来复现，而无需执行 $s$ 次单独的 bordered 矩阵 SVD。

所提出的算法（算法 5）为秩非增列的投影系数维护一个缓冲区。在这些步骤中，运行因子 $Q$ 保持不变。当“秩增大”列到达时（残差 $\ge \text{tol}$），算法执行以下操作：

• 通过计算累积系数的单次瘦 SVD 来刷新缓冲区，并批量更新 $Q$ 和 $R$。
• 处理新列，可能对该局部 bordered 矩阵的最小奇异值应用第二次截断测试，以丢弃可忽略的秩。
• 仅在这些秩增大事件发生时，应用两遍经典 Gram–Schmidt（CGS-2）以恢复所附加列的 $W$-正交性。

这种重构将施加于 $Q$ 的大型正交乘法次数从 $O(n)$（流长度）减少到 $O(r + J_{E2})$，其中 $r$ 是数值秩，$J_{E2}$ 是截断性秩增大事件的数量。

主要贡献
本文提供了两项主要理论进展和一项实用算法改进：

1. 独立于流长度的正交性界：
   作者证明（定理 4.1），在标准概率舍入误差模型下，计算得到的左因子 $Q$ 的 $W$-正交性损失受限于：
   $$\|I - Q^\top W Q\|_2 \leq c_1 (r + J_{E2}) r \sqrt{m} \log(2/\delta) \varepsilon_{\text{mach}} + O(\varepsilon_{\text{mach}}^2)$$
   关键在于，该界独立于流长度 $n$。它仅通过 $\sqrt{m}$ 因子依赖于 $m$（列维度）。这解决了 Brand 提出的未解之谜：无需在每一步进行重正交化；所提出的批处理策略确保了正交性在机器精度范围内随 $n$ 均匀保持。

2. 精确的前向误差界：
   本文建立了 $W$-加权算子范数下分解的新前向误差界（定理 4.5）：
   $$\|U - Q\Sigma R^\top\|_W \leq \sqrt{n} \, \text{tol} + (\text{关于 } n \text{ 一致的舍入项})$$
   这比 Fareed 和 Singler [9] 现有的界（$n \, \text{tol}$）更精确。作者通过构造性示例证明 $\sqrt{n}$ 速率是可实现的，表明之前的界松散了 $\sqrt{n}$ 倍。

3. 算法效率：
   通过减少昂贵的重正交化步骤数量并批处理更新，所提出的算法显著降低了计算开销。

结果
数值实验在二维抛物型测试问题（包括无权重和有权重的有限元设置）及合成数据上进行。

• 正交性：现有算法（Brand 的直接更新和 Fareed 的重正交化更新）显示出正交性退化随 $n$ 增长（在加权情况下漂移至 $10^{-3}$），而所提出的算法在流长度高达 $n=10,000$ 且列维度高达 $m=100,000$ 的范围内，将正交性维持在机器精度（$\sim 10^{-14}$）。
• 误差界：实验证实了 $\sqrt{n} \, \text{tol}$ 截断速率。在一个构造性示例中，测量误差与 $\sqrt{n} \, \text{tol}$ 预测相符，而 Fareed–Singler 界（$n \, \text{tol}$）的松散程度随 $\sqrt{n}$ 增长。
• 性能：所提出的算法比其最接近的竞争对手快 4.5 倍至 34 倍。在加权情况下，现有算法 94% 的时间消耗在重正交化上，而所提出的算法将此成本降低了三个数量级。

意义
本文声称解决了关于增量 SVD 中重正交化频率的未解之谜。通过重构算法以批处理秩非增更新，实现了：

1. 均匀正交性：运行基保持数值正交，无论流长度如何，从而消除了对缺乏先验保证的启发式、周期性重正交化检查的需求。
2. 更紧的误差分析：提供了数学上严谨、精确的误差界（$\sqrt{n} \, \text{tol}$），将现有最先进水平提高了 $\sqrt{n}$ 倍。
3. 实际加速：该方法在主要由重正交化成本主导的应用（如有限元 POD）中提供了显著的加速，且不牺牲精度。

作者指出，该算法的早期版本已应用于时间分数阶偏微分方程、积分微分方程以及偏微分方程约束优化，依赖于现已确立的正交性和误差保证。未来的工作建议收紧正交性漂移分析（目前保守约 $10^3$ 倍），并优化目前主导运行时间的投影步骤。