Iterative Methods for Solving Factorized Linear Systems
Iterative Methods for Solving Factorized Linear Systems
复制标题
DOI：
10.1137/17m1115678
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
A. Ma;D. Needell;Aaditya Ramdas
中科院分区：
文献类型：
--
作者：
A. Ma;D. Needell;Aaditya Ramdas
随机迭代算法，如Kaczmarz和Gauss-Seidel方法，由于其速度，简单性和近似求解大型线性方程组而无需访问整个矩阵的能力而获得了最近的关注。在这项工作中，我们考虑的设置，我们希望解决一个线性系统在一个大型矩阵X，存储在一个因式分解的形式，X = UV;这个设置要么自然出现在许多应用程序中，或可能会强加时，与大型低秩数据集的原因存储所需的空间。我们提出了一个变种的随机Kaczmarz方法，这样的系统，利用因式分解的形式，并避免计算X。我们证明了一个指数收敛速度和补充我们的理论保证与实验证据表明，因子化的变体产生显着的加速收敛。
Stochastic iterative algorithms such as the Kaczmarz and Gauss-Seidel methods have gained recent attention because of their speed, simplicity, and the ability to approximately solve large-scale linear systems of equations without needing to access the entire matrix. In this work, we consider the setting where we wish to solve a linear system in a large matrix X that is stored in a factorized form, X = UV; this setting either arises naturally in many applications or may be imposed when working with large low-rank datasets for reasons of space required for storage. We propose a variant of the randomized Kaczmarz method for such systems that takes advantage of the factored form, and avoids computing X. We prove an exponential convergence rate and supplement our theoretical guarantees with experimental evidence demonstrating that the factored variant yields significant acceleration in convergence.