The double splitting iteration method for solving the large indefinite least squares problem

技术摘要：求解大型不定最小二乘问题的双重分裂迭代法

问题陈述
本文针对求解大规模不定最小二乘（ILS）问题所面临的计算挑战，该问题表述为最小化不定二次型 $(b - Ax)^T J (b - Ax)$，其中 $A \in \mathbb{R}^{m \times n}$ 是一个大型稀疏矩阵，$b \in \mathbb{R}^m$，且 $J = \text{diag}(I_p, -I_q)$ 是一个满足 $p+q=m$ 的符号矩阵。当 $pq > 0$时，该问题导出的正规方程$A^T J A x = A^T J b$ 涉及一个非正定的 Hessian 矩阵。虽然直接法适用于小型稠密问题，但对于大规模系统，迭代方案更为可取。目前该问题最先进的迭代求解器主要依赖于系数矩阵 $A^T J A = M - N$ 的单重分裂策略，例如基于分裂（SP）的方法、广义 SP（GSP）方法以及交替方向隐式（ADI）方法。

方法论
作者提出了一种新颖的**双重分裂（DS）**迭代法。与将系数矩阵分解为两部分（$M - N$）的传统方法不同，该方法利用了三部分分解：
$$A^T J A = P - R - S$$
其中 $P$ 为非奇异矩阵。受 GSP 方法结构的启发，作者基于划分 $A = [A_1; A_2]$ 定义了特定的矩阵：

• $P = \alpha I + A_1^T A_1$（对称正定，SPD）
• $R = A_2^T A_2$（对称）
• $S = \alpha I$（对称）
  其中 $\alpha > 0$ 为给定参数。

该分解导出了一个两步稳态迭代格式：
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
该公式利用了前两次迭代（$x_k$ 和 $x_{k-1}$）的信息，从而区别于 SP 和 GSP 方法的一步性质。该格式的收敛性通过分析关联块迭代矩阵 $W$ 的谱半径 $\rho(W)$ 进行考察。作者推导出了 $W$ 的特征值 $\lambda$ 的标量二次方程，并应用关于二次方程根的引理证明了对于所有 $\alpha > 0$，均有 $|\lambda| < 1$。

主要贡献

1. 新颖的迭代框架：本文引入了一种专门针对 ILS 问题产生的正规方程的双重分裂策略，为占主导地位的单重分裂范式提供了一种独特的替代方案。
2. 无条件收敛性证明：作者提供了严格的谱分析，证明所提出的 DS 迭代法对于任意正参数 $\alpha$ 均无条件收敛。该结果通过将其与先前文献中关于 Hermitian 正定矩阵的现有收敛准则相联系，进一步明确了其背景。
3. 算法实现：文中给出了详细的算法（算法 2.1），概述了计算步骤，包括利用 Cholesky 分解求逆 SPD 矩阵 $P$。

数值结果
进行了两项数值实验，以评估 DS 方法相对于 SP、GSP 和 ADI 方法的性能：

• 示例 3.1（稠密矩阵）：使用随机生成的超大规模稠密矩阵，测试了 DS 方法在不同维度（$m$ 高达 54,000）下的表现。在最优参数 $\alpha=1$ 下，DS 方法恰好收敛于2 次迭代。虽然 SP 和 GSP 也在 1 次迭代内收敛，但 DS 方法实现了显著更低的 CPU 时间（例如，在 $m=51,000$ 时，DS 约为 4.8 秒，而 GSP 约为 75 秒）。
• 示例 3.2（稀疏矩阵）：使用源自总体最小二乘问题的矩阵，对 DS 方法在稀疏结构下进行了测试。在最优参数 $\alpha=10^{-4}$ 下，DS 方法再次收敛于2 次迭代。在所有测试的规模（高达 $m=8,192$）下，它在计算时间上始终优于单重分裂方法，证明了即使在问题规模增加时，其效率依然卓越。

意义与主张
本文主张，所提出的双重分裂迭代范式是对传统单重分裂方法的建设性改进。其主要意义在于该方法能够针对大规模 ILS 问题实现更快的收敛速度（以 CPU 时间衡量）和鲁棒性。作者强调，尽管该方法需要前两次迭代的信息，但引入这种历史信息使得与单步 SP、GSP 和 ADI 方法相比，计算成本大幅降低。这项工作为未来关于基于双重分裂的迭代法研究提供了方法论参考，并暗示了向自适应参数选择及其他类型不定线性系统扩展的潜力。