A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

技术摘要：线性最小二乘向后误差的变分方程与下界

问题陈述
本文解决了高效估计具有多个右端项的线性最小二乘问题向后误差 $\mu$ 的挑战：
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
其中 $A \in \mathbb{R}^{m \times n}$ 且 $B \in \mathbb{R}^{m \times d}$。向后误差 $\mu$ 定义为扰动 $[E, \theta F]$ 的最小范数，使得近似解 $X$ 成为扰动系统 $(A+E)^T(A+E)X = (A+E)^T(B+F)$ 的精确解。

对于迭代求解器而言，直接计算 $\mu$ 代价过高，因为它需要求解大型特征值问题或广义特征值问题。虽然已存在估算方法（如 Karlson-Waldén 估算），但它们往往难以精确计算，或者缺乏保证的界限（即它们不是严格的上界或下界）。本文寻求一种推导可靠且计算廉价的估算方法，特别关注可作为 LSQR 和 LSMR 等迭代方法停止准则的下界。

方法论
核心方法论依赖于在不定线性代数框架内，将向后误差表示为广义特征值问题。

1. 变分公式：本文首先建立了向后误差 $\mu(A, R_\theta)$ 的变分方程，其中 $R_\theta$ 是变换后的残差矩阵。它将 $\mu$ 表示为在由约束 $X^T J_{n,d} X = -I_d$ 定义的不定流形上的最大化问题，其中 $J_{n,d} = \text{diag}(I_n, -I_d)$。
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. 双曲 CS 分解：为了解决该优化问题，作者利用了双曲 CS 分解（这是酉矩阵 CS 分解的不定类比）。该分解允许将关于矩阵 $X$ 的优化解耦为关于正交矩阵和对角缩放矩阵的优化。
3. 分解定理：通过应用该分解，本文推导出一个定理，表明具有 $d$ 个右端项的问题的向后误差可以分解为 $d$ 个较小的向后误差问题之和，每个问题仅涉及单个右端项。
4. 下界构建：利用该分解，作者提出了一种基于草图（sketching）的下界。通过利用草图矩阵 $SA$（其中$S$为草图矩阵）计算单个测试向量$p$，他们可以评估单右端项向后误差公式。这提供了真实向后误差的可证明下界。

主要贡献

• 定理 1（分解）：主要的理论贡献是将向后误差 $\mu(A, R_\theta)$ 分解为较小项之和：
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  其中 $P$ 和 $Q$ 是具有正交列的矩阵。这将问题的复杂度降低为一系列标量优化。
• 单右端项的精确表达式：本文提供了单右端项情况下向后误差 $\mu(a, r)$ 的稳定闭式表达式，该表达式依赖于向量之和与差的范数：
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• 基于草图的下界：作者为迭代方法提出了一种新的下界。通过使用草图矩阵 $S$ 计算近似方向 $p$，他们可以评估单右端项公式以获得值 $\mu(Ap/\|p\|_2, r_\theta)$。
  • 该值可证明是真实向后误差的下界。
  • 本文证明该下界的质量与草图化的 Karlson-Waldén 估算相当，具体满足不等式：
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    其中 $\eta$ 代表草图的失真度，$\nu$ 是 Karlson-Waldén 估算。
• 迭代细化与重用：本文讨论了通过迭代细化向量 $p$ 以及在各次迭代中“重用”计算出的向量 $Ap$ 来改进该估算的方法，以降低计算成本。

结果
数值实验使用 LSMR 求解器在 SuiteSparse 集合中的一个高条件数（$\approx 3.5 \times 10^{16}$）矩阵上进行了测试。结果表明：

• 提出的下界在准确性上始终与草图化的 Karlson-Waldén 估算相当。
• 在草图成本较低（$n_{sketch}$ 较小）的情况下，提出的下界有时比草图化的 Karlson-Waldén 估算更准确。
• “重用”的下界（在迭代过程中重用 $Ap$）在大部分迭代历史中保持接近真实向后误差，表明其作为廉价误差监测器的实用性。
• 仅当草图尺寸非常大（$16n$）时，对向量 $p$ 的迭代细化才提高了准确性，这表明对于标准草图尺寸，增加的计算成本可能得不偿失。
• 尝试使用类似技术构建上界，发现其仅略优于现有的简单上界（如 $\|A^T r\|_2 / \|r\|_2$），并且仍然显著高估了真实误差。

意义与主张
本文声称其主要意义在于理论层面：它提供了一种向后误差的分解，自然地导出了可计算的下界。

• 可靠性：与不能保证是上界或下界的草图化 Karlson-Waldén 估算不同，所提出的方法产生严格下界。这对于停止准则非常有价值，因为它保证真实误差至少与估算值一样大。
• 效率：该方法允许将基于草图的估算转换为具有相当质量的下界，同时增加了作为界限的保证。
• 谦逊：作者对于上界持谦逊态度，指出他们以类似方式产生上界的尝试“通常不成功”。他们承认，多右端项的分解涉及对两个矩阵（$P$ 和 $Q$）的优化，这比下界所需的单向量优化更为复杂。未来的工作建议解决多右端项情况，并调查为何寻找好的上界似乎比寻找好的下界更困难。