Randomized Extended Kaczmarz for Solving Least Squares
Anastasios Zouzias Anastasios Zouzias is with the Department of Computer Science at the University of Toronto, Canada. E-mail: Part of this work was done while the author was visiting the Department of Computer Science at Princeton University. Nikolaos M. Freris Nikolaos M. Freris is with IBM Research - Zürich, Säumerstrasse 4, 8803 Rüschlikon, Switzerland. E-mail:
Abstract
We present a randomized iterative algorithm that exponentially converges in expectation to the minimum Euclidean norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the square condition number of the system multiplied by the number of non-zeros entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin.
中文速览
求解线性方程组的最小范数最小二乘问题（即当方程无解时找最"合理"的近似解）长期依赖QR分解、奇异值分解等计算代价较高的确定性方法。本文提出一种名为"随机扩展Kaczmarz（Randomized Extended Kaczmarz）"的随机迭代算法，通过每轮以概率正比于行/列范数平方随机选取矩阵的行与列、交替做投影更新，将经典Kaczmarz方法推广到无解方程组的情形，并严格证明该算法以指数速度期望收敛到最小欧氏范数最小二乘解。理论分析表明，达到给定精度所需的算术运算次数正比于矩阵条件数的平方与非零元素个数的乘积，这对稀疏、良态、强矩形矩阵尤为高效。数值实验进一步验证，在稀疏良态问题上该算法显著优于LAPACK的标准例程，在稠密随机矩阵上也可与Blendenpik等主流随机预处理方法媲美，为大规模最小二乘问题提供了一种简单且理论保证完备的新选择。
原文 arXiv:1205.5770;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1205.5770v3