KRYLOV METHODS FOR LOW-RANK REGULARIZATION
KRYLOV METHODS FOR LOW-RANK REGULARIZATION
复制标题
DOI：
10.1137/19m1302727
复制
发表时间：
2020-01-01
影响因子：
1.5
通讯作者：
Nagy, James G.
中科院分区：
文献类型：
--
作者：
Gazzola, Silvia;Meng, Chang;Nagy, James G.
本文介绍了计算大规模线性问题的低秩近似解的新的求解器，特别关注线性反问题的正则化。虽然Krylov方法结合显式投影到低秩子空间已经用于离散随机或时间依赖偏微分方程产生的适定系统，但我们主要关注的是解决所谓的核范数正则化问题的算法，其中对解施加适当的核范数惩罚以及以2范数表示的拟合数据项：这具有隐含地强制低秩解决方案的效果。通过采用迭代重加权范数方法，核范数正则化问题被重新表述为一系列二次问题，然后可以使用Krylov方法有效地解决，从而产生一个内部-外部迭代方案。我们的方法与文献中其他求解器的不同之处在于：（a）利用Kronecker乘积性质来定义重新加权的2-范数惩罚项;（B）有效的预处理Krylov方法取代梯度（投影）方法;（c）正则化参数可以有效地自适应地沿沿着迭代设置。此外，我们重新制定灵活的Krylov方法的框架内的核规范正则化和一些现有的Krylov方法，将低秩投影的新inner-outer方法。这导致了一个计算效率更高（但启发式）的策略，不依赖于内部-外部迭代方案。包括图像去模糊，计算机断层扫描和修复在内的数值实验表明，我们的新求解器与其他最先进的求解器相比，在低秩问题上具有竞争力，并且与其他经典Krylov方法相比，可以提供更高质量的重建。
This paper introduces new solvers for the computation of low-rank approximate solutions to large-scale linear problems, with a particular focus on the regularization of linear inverse problems. Although Krylov methods incorporating explicit projections onto low-rank subspaces are already used for well-posed systems that arise from discretizing stochastic or time-dependent PDEs, we are mainly concerned with algorithms that solve the so-called nuclear norm regularized problem, where a suitable nuclear norm penalization on the solution is imposed alongside a fit-to-data term expressed in the 2-norm: this has the effect of implicitly enforcing low-rank solutions. By adopting an iteratively reweighted norm approach, the nuclear norm regularized problem is reformulated as a sequence of quadratic problems, which can then be efficiently solved using Krylov methods, giving rise to an inner-outer iteration scheme. Our approach differs from the other solvers available in the literature in that (a) Kronecker product properties are exploited to define the reweighted 2-norm penalization terms; (b) efficient preconditioned Krylov methods replace gradient (projection) methods; (c) the regularization parameter can be efficiently and adaptively set along the iterations. Furthermore, we reformulate within the framework of flexible Krylov methods both the new innerouter methods for nuclear norm regularization and some of the existing Krylov methods incorporating low-rank projections. This results in an even more computationally efficient (but heuristic) strategy that does not rely on an inner-outer iteration scheme. Numerical experiments including image deblurring, computed tomography, and inpainting show that our new solvers are competitive with other state-of-the-art solvers for low-rank problems and deliver reconstructions of increased quality with respect to other classical Krylov methods.