论文标题
ALS：线性系统的增强拉格朗日草图方法
ALS: Augmented Lagrangian Sketching Methods for Linear Systems
论文作者
论文摘要
我们开发了两种基本的随机素描技术。惩罚素描（PS）和增强拉格朗日草图（ALS）用于解决一致的线性系统。提出的PS和ALS技术通过引入Lagrangian罚款草图扩展并推广了Sketch＆Project方法（SP）方法的范围。在此过程中，我们将SP方法恢复为特殊情况，并开发出新的随机迭代方法的家族。通过在拟议的PS方法中改变草图参数，我们恢复了新颖的随机方法，例如牛顿下降，惩罚性kaczmarz，惩罚kaczmarz，惩罚随机下降，惩罚坐标坐标下降，惩罚性高斯追求和惩罚块Kaczmarz。此外，提出的ALS方法综合了各种新的随机方法，例如增强的牛顿血统，增强的Kaczmarz，增强的随机下降，增强的坐标下降，增强的高斯追击，并增强了Kaczmarz的kaczmarz kaczmarz成为一个框架。此外，我们表明，开发的PS和ALS框架可用于将原始线性系统重新制定为等效的随机优化问题，即惩罚随机重新重新制定和增强随机重新印度。我们证明了PS和ALS方法的全局收敛速率以及子线性$ \ Mathcal {o}（\ frac {1} {k} {k}）$ rates $ cesaro的迭代率率。所提出的收敛结果适用于广泛的随机矩阵分布家族，这提供了微调适合特定应用的随机性的机会。最后，我们执行的计算实验证明了与现有SP方法相比，我们方法的效率。
We develop two fundamental stochastic sketching techniques; Penalty Sketching (PS) and Augmented Lagrangian Sketching (ALS) for solving consistent linear systems. The proposed PS and ALS techniques extend and generalize the scope of Sketch & Project (SP) method by introducing Lagrangian penalty sketches. In doing so, we recover SP methods as special cases and furthermore develop a family of new stochastic iterative methods. By varying sketch parameters in the proposed PS method, we recover novel stochastic methods such as Penalty Newton Descent, Penalty Kaczmarz, Penalty Stochastic Descent, Penalty Coordinate Descent, Penalty Gaussian Pursuit, and Penalty Block Kaczmarz. Furthermore, the proposed ALS method synthesizes a wide variety of new stochastic methods such as Augmented Newton Descent, Augmented Kaczmarz, Augmented Stochastic Descent, Augmented Coordinate Descent, Augmented Gaussian Pursuit, and Augmented Block Kaczmarz into one framework. Moreover, we show that the developed PS and ALS frameworks can be used to reformulate the original linear system into equivalent stochastic optimization problems namely the Penalty Stochastic Reformulation and Augmented Stochastic Reformulation. We prove global convergence rates for the PS and ALS methods as well as sub-linear $\mathcal{O}(\frac{1}{k})$ rates for the Cesaro average of iterates. The proposed convergence results hold for a wide family of distributions of random matrices, which provides the opportunity of fine-tuning the randomness of the method suitable for specific applications. Finally, we perform computational experiments that demonstrate the efficiency of our methods compared to the existing SP methods.
