Operator-based Analysis of Numerical Projection Perturbations in Grassmann Manifold Optimization

技术摘要：Grassmann 流形优化中基于算子的数值投影扰动分析

问题陈述
在 Grassmann 流形 $\text{Gr}(p, n)$ 上的优化是数据科学、机器学习和信号处理中的一个基本原语，广泛应用于低秩矩阵补全和子空间跟踪等任务。在数值实现中，流形上的点通常由正交投影算子 $P$（对称、幂等且秩为 $p$ 的矩阵）表示。经典的扰动理论（如 Parlett (1998)、Wedin (1972) 以及 Stewart & Sun (1990) 等奠基性著作所建立的理论）将扰动视为任意对称矩阵。这些理论表明，子空间误差（或幂等缺陷 $\| \tilde{P}^2 - \tilde{P} \|_F$）随扰动范数 $\epsilon = \|E\|_F$ 呈线性增长。

然而，在黎曼优化算法（例如梯度下降、收缩映射/retractions）中，由梯度步、收缩映射误差或浮点舍入产生的扰动并非是任意的，而是具有**切向结构（tangent-structured）**的。它们满足特定的分块形式 $E = P\Delta(I-P) + (I-P)\Delta^\top P$。本文指出，现有文献通过将所有对称扰动统一对待，未能区分“沿流形滑动”的方向与“将迭代点推离流形”的方向。因此，结构性抵消的可能性——即对于切向扰动，幂等缺陷可能呈二次方而非线性增长——一直未得到表征。

方法论
作者开发了一个显式利用切向扰动分块结构的基于算子的扰动框架。

1. 数学框架： 分析利用了谱定理以及切空间 $T_P\text{Gr}(p, n)$ 的特定分块分解。在 $P$ 的谱基下，切向扰动 $E$ 具有形式 $\begin{bmatrix} 0 & \Delta \\ \Delta^\top & 0 \end{bmatrix}$，其中 $\Delta \in \mathbb{R}^{p \times (n-p)}$。
2. 精确恒等式： 作者没有依赖渐近界限，而是推导了扰动投影 $\tilde{P} = P + E$ 的精确代数恒等式。
3. 谱分析： 利用简化后的扰动块 $\Delta$ 的奇异值，推导出了 $\tilde{P}$ 的闭式谱分布。
4. 对比分析： 本文将切向扰动与一般对称扰动（特别是其在谱基下具有非零对角块的扰动）进行对比，以隔离出二次方抵消的来源。
5. 数值验证： 在随机正交投影算子以及源自 CIFAR-10 图像数据集（主成分分析）的真实数据投影算子上进行了实验。这些实验在 IEEE 双精度算术下验证了理论预测。

核心贡献与结果

• 二次方残差恒等式 (Lemma 1)： 本文证明，对于任何切向扰动 $E$，幂等缺陷满足精确恒等式 $\tilde{P}^2 - \tilde{P} = E^2$。这表明展开式中的一阶项完全消失，仅留下纯粹的二次方缺陷项。
• 紧致常数界限 (Lemma 2 & Theorem 5)： 作者推导出了残差的紧致上界：$\|\tilde{P}^2 - \tilde{P}\|_F \leq \epsilon^2 / \sqrt{2}$。当且仅当简化后的扰动块 $\Delta$ 的秩为 1 时，等号成立。此外，他们建立了一个与维度无关的双侧界限：
  $$\frac{\epsilon^2}{\sqrt{2r}} \leq \|\tilde{P}^2 - \tilde{P}\|_F \leq \frac{\epsilon^2}{\sqrt{2}}$$
  其中 $r = \text{rank}(E)/2$。这表明当扰动分布在多个奇异方向上时，残差会显著小于最坏情况下的界限。
• 闭式谱 (Theorem 4)： 扰动投影的特征值被显式推导为 $\lambda_{\pm}(\sigma_i) = \frac{1}{2}(1 \pm \sqrt{1 + 4\sigma_i^2})$，其中 $\sigma_i$ 是 $\Delta$ 的奇异值，此外还包括未扰动的特征值 0 和 1。
• 后向误差分析 (Theorem 6)： 到最近的正交投影算子 $P^*$ 的距离满足 $\|P^* - \tilde{P}\|_F = \|\tilde{P}^2 - \tilde{P}\|_F + O(\epsilon^6)$。这证实了其后向误差是二次方的，且具有最优常数。
• 切向结构的必要性 (Theorem 7)： 本文证明了二次方抵消是切向结构所特有的。如果扰动包含“法向”分量（即在谱基下具有非零对角块），则幂等缺陷会退化为线性增长（$O(\epsilon)$）。
• 收缩映射传播 (Theorem 9)： 虽然投影算子本身的结构是二次方稳定的，但本文澄清了这种增益并不会自动通过标准的收缩映射（retractions）进行传播。除非使用特定的保结构收缩映射，否则收缩映射步骤后的优化迭代误差仍保持为一阶（$O(\epsilon)$）。
• 稳定性判据： 作者提出了适用于双精度计算的实用稳定性判据：
  • 依赖秩的判据： $\epsilon < \sqrt{u/p}$
  • 不依赖秩的判据： $\epsilon \lesssim 2^{1/4}\sqrt{u}$
    其中 $u \approx 2.22 \times 10^{-16}$ 为单位舍入误差。

意义与主张
本文声称解决了 Grassmann 流形优化在理论理解上的空白，即确立了切向结构扰动享有二次方后向误差界限，而任意对称扰动则受限于线性界限。

• 理论影响： 结果提供了一个与维度无关的紧致常数界限 ($\epsilon^2/\sqrt{2}$)，改进了以往往往依赖于谱间隙或维度 $n$ 与 $p$ 的线性界限。
• 数值意义： 二次方增长意味着对于足够小的扰动（例如切空间中的舍入误差），投影算子可以无需显式的重投影步骤，便能达到机器精度的幂等性。这可以显著降低大规模子空间跟踪和低秩恢复的计算开销。
• 实验验证： 在随机数据和真实世界（CIFAR-10）数据上的数值实验均证实了理论预测达到了机器精度。具体而言，在 $\epsilon = 10^{-6}$ 时，切向扰动产生的后向误差比同范数的非切向扰动小约六个数量级，验证了线性与二次方增长的区别。

局限性与未来工作
作者谦逊地指出了几点局限性：

1. 分析假设了精确的正交投影算子，并未涵盖非正交投影算子或一般的对称扰动（尽管文中进行了对比分析）。
2. 二次方增益无法通过标准收缩映射得以保留；实现端到端的二次方稳定性需要开发保结构的收缩映射，这属于未来的研究方向。
3. 所提供的稳定性判据是充分而非必要的。
4. 将研究扩展至 Stiefel 流形及其他具有类似切向结构的流形被确定为未来的研究方向。

总之，本文通过严谨的基于算子的分析证明了 Grassmann 流形的几何结构会导致数值误差中的特定抵消，为更稳定、更高效的黎曼优化算法提供了路径。