Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs
Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs
复制标题
用于线性离散不适定问题的 Krylov 迭代求解器 CGME 和 LSMR 的正则化特性及其在截断随机 SVD 中的应用
DOI：
10.1007/s11075-019-00865-w
复制
发表时间：
2020-02-24
影响因子：
2.1
通讯作者：
Jia, Zhongxiao
中科院分区：
文献类型：
--
作者：
Jia, Zhongxiao
对于大规模线性离散不适定问题min平行于Ax-B平行于或Ax = B，其中B被高斯白色噪声污染，通常使用以下Krylov求解器：LSQR及其数学上等价的CGLS（即，应用于A（T）Ax = A（T）B的共轭梯度（CG）方法），CGME（即，应用于min的CG方法平行于AAT y-B平行于或AA（T）y = B其中x = A（T）y），以及LSMR（即，最小残差（MINRES）方法应用于A（T）Ax = A（T）B）。这些方法具有内在的正则化效应，其中迭代次数k起正则化参数的作用。本文分析了CGME和LSMR的正则化效果，建立了CGME迭代的滤波SVD展开等结果，证明了CGME和LSMR的2-范数滤波最佳正则化解的精度分别低于或至少与LSQR的精度相当.我们还证明了CGME和LSMR的半收敛性总是不迟于LSQR的半收敛性，也不早于LSQR的半收敛性。作为一个副产品，使用CGME的分析方法，我们改进了一个基本结果的截断秩k近似SVD的随机算法产生的A的准确性，并揭示了截断步骤如何损害的准确性。数值实验验证了我们在CGME和LSMR上的结果。
For the large-scale linear discrete ill-posed problem min parallel to Ax-b parallel to or Ax = b with b contaminated by Gaussian white noise, the following Krylov solvers are commonly used: LSQR, and its mathematically equivalent CGLS (i.e., the Conjugate Gradient (CG) method applied to A(T)Ax = A(T)b), CGME (i.e., the CG method applied to min parallel to AATy-b parallel to or AA(T)y = b with x = A(T)y), and LSMR (i.e., the minimal residual (MINRES) method applied to A(T)Ax = A(T)b). These methods have intrinsic regularizing effects, where the number k of iterations plays the role of the regularization parameter. In this paper, we analyze the regularizing effects of CGME and LSMR and establish a number of results including the filtered SVD expansion of CGME iterates, which prove that the 2-norm filtering best possible regularized solutions by CGME and LSMR are less accurate than and at least as accurate as those by LSQR, respectively. We also prove that the semi-convergence of CGME and LSMR always occurs no later and sooner than that of LSQR, respectively. As a byproduct, using the analysis approach for CGME, we improve a fundamental result on the accuracy of the truncated rank k approximate SVD of A generated by randomized algorithms, and reveal how the truncation step damages the accuracy. Numerical experiments justify our results on CGME and LSMR.