solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6452次
Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. (arXiv:1503.08235v3 [math.NA] UPDATED)
来源于:arXiv
The Kaczmarz and Gauss-Seidel methods both solve a linear system
$\bf{X}\bf{\beta} = \bf{y}$ by iteratively refining the solution estimate.
Recent interest in these methods has been sparked by a proof of Strohmer and
Vershynin which shows the randomized Kaczmarz method converges linearly in
expectation to the solution. Lewis and Leventhal then proved a similar result
for the randomized Gauss-Seidel algorithm. However, the behavior of both
methods depends heavily on whether the system is under or overdetermined, and
whether it is consistent or not. Here we provide a unified theory of both
methods, their variants for these different settings, and draw connections
between both approaches. In doing so, we also provide a proof that an extended
version of randomized Gauss-Seidel converges linearly to the least norm
solution in the underdetermined case (where the usual randomized Gauss Seidel
fails to converge). We detail analytically and empirically the convergence
properties of both methods 查看全文>>