线性系统的随机迭代方法
研究随机算法和线性代数条件数,以提高坐标下降和迭代投影算法,在一些概率分布下,提高收敛速度。此外,进一步讨论以度量正则性假设下凸系统的推广及其与 ill-posedness 的距离的关系。
Jun, 2008
本文介绍了基于随机投影的 Kaczmarz 方法的两个块版本,这两个版本可以期望地收敛到不一致系统的最小二乘解。通过砖石铺设 A 矩阵,可以保证这种算法的指数收敛。数值实验表明,这种方法实际上可以带来实际上的优势。
Mar, 2014
本篇研究开发了一种自适应的非精确牛顿法,通过使用随机迭代草图求解器不精确地求解拉格朗日牛顿系统,并在精确增广拉格朗日优势函数上执行线搜索以选择适当的步长,以控制随机求解器的精度和惩罚参数,以确保不精确的牛顿方向是精确增广拉格朗日的下降方向,从而全局近乎确定地收敛,并表明在本地可采用单位步长,因此该方法表现出局部线性收敛。
May, 2023
我们提出了一种随机迭代算法,此算法以期望指数收敛于给定线性方程组的最小欧几里得范数最小二乘解,该算法是随机 Kaczmarz 方法的扩展,其期望运算次数正比于系统的平方条件数乘以输入矩阵的非零数目。
May, 2012
该研究对 Kaczmarz 算法进行了分析,证明了在有噪音的情况下,随机化方法达到了与无误差情况下相同的误差阈值,并给出了例子来展示结果在一般情况下的尖锐程度,这是解决线性方程组 Ax=b 问题的一种迭代算法。
Feb, 2009
本文提出一种基于用户定义参数(矩阵和概率分布)的随机问题,它具有等价的解释方式,能够转化为最优化问题、线性系统、不动点问题和概率交点问题,并提出了三种具有全局线性收敛率的随机算法来解决问题,这些方法可以被理解为随机梯度下降、随机牛顿法、随机近端点法、随机投影法。
Jun, 2017
介绍了 Kaczmarz 方法的随机版本来解决一致、超定的线性问题,证明了它具有期望指数收敛速度,且速度不依赖于方程的数量,甚至只需知道随机的一小部分。
Feb, 2007
该论文介绍了如何加速随机坐标下降方法,提高收敛速度,同时又不用支付每次迭代的代价。它提出了一个新的通用方法,并证明它的收敛性,并在多个领域中获得更快的渐近运行时间。
May, 2013
提出了一种新的随机稀疏 Kaczmarz 方法并证明了它在解决线性方程组,成分分解和低秩矩阵问题方面的线性收敛性,同时数值实验表明了其优越性。
Oct, 2016
该研究提出了一种随机化的二阶优化方法 ——Newton Sketch,使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数,该算法证明具有超线性收敛和指数高概率,与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化,即使在没有自共轭的情况下,也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序,带有凸约束的二次程序,逻辑回归和其他广义线性模型以及半定规划的扩展问题。
May, 2015