论文标题
线性可行性问题的贪婪随机平均块投影方法
A greedy randomized average block projection method for linear feasibility problems
论文作者
论文摘要
随机投影（RP）方法是一种简单的迭代方案，用于解决线性可行性问题，并且由于其速度和低内存需求而获得了流行。本文通过使用两种成分来开发标准RP方法的加速变体：贪婪的概率标准和平均块方法，并获得了求解贪婪的随机平均块投影（GRABP）方法，以求解线性不平等的大规模系统。我们证明，在推断得出的不同选择下，这种方法在期望中线性收敛。在随机生成和现实世界数据上的数值实验表明，Grabp的优势比几个最先进的求解器，例如随机投影（RP）方法，采样Kaczmarz Motzkin（SKM）方法，广义SKM（GSKM）方法以及Skm方法的Nesterov Acceleration。
The randomized projection (RP) method is a simple iterative scheme for solving linear feasibility problems and has recently gained popularity due to its speed and low memory requirement. This paper develops an accelerated variant of the standard RP method by using two ingredients: the greedy probability criterion and the average block approach, and obtains a greedy randomized average block projection (GRABP) method for solving large-scale systems of linear inequalities. We prove that this method converges linearly in expectation under different choices of extrapolated stepsizes. Numerical experiments on both randomly generated and real-world data show the advantage of GRABP over several state-of-the-art solvers, such as the randomized projection (RP) method, the sampling Kaczmarz Motzkin (SKM) method, the generalized SKM (GSKM) method, and the Nesterov acceleration of SKM method.
