On Motzkin’s method for inconsistent linear systems
On Motzkin’s method for inconsistent linear systems
复制标题
DOI：
10.1007/s10543-018-0737-6
复制
发表时间：
2018-02
影响因子：
1.5
通讯作者：
Jamie Haddock;D. Needell
中科院分区：
文献类型：
--
作者：
Jamie Haddock;D. Needell
迭代线性求解器由于其计算效率和大规模线性系统的低内存占用而获得了最近的流行。松弛法，或Motzkin的方法，可以被看作是一种迭代方法，目前的估计项目的解决方案超平面对应的最违反的约束。虽然这导致了一致的系统，不一致的最小二乘问题的最优选择策略，该策略提出了收敛速度和解决方案的精度之间的权衡。我们提供了一个理论分析，表明Motzkin的方法提供了一个初始加速收敛速度，这种加速依赖于残差的动态范围。作为一个具体的例子，我们量化高斯系统的这种加速。最后，我们包括实验证据支持分析的真实的和合成系统。
Iterative linear solvers have gained recent popularity due to their computational efficiency and low memory footprint for large-scale linear systems. Therelaxation method, orMotzkin’s method, can be viewed as an iterative method that projects the current estimation onto the solution hyperplane corresponding to the most violated constraint. Although this leads to an optimal selection strategy for consistent systems, for inconsistent least square problems, the strategy presents a tradeoff between convergence rate and solution accuracy. We provide a theoretical analysis that shows Motzkin’s method offers an initially accelerated convergence rate and this acceleration depends on the dynamic range of the residual. We quantify this acceleration for Gaussian systems as a concrete example. Lastly, we include experimental evidence on real and synthetic systems that support the analysis.