solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6410次
A Doubly Stochastic Gauss-Seidel Algorithm for Solving Linear Equations and Certain Convex Minimization Problems. (arXiv:1810.05251v1 [math.OC])
来源于:arXiv
Consider the classical problem of solving a general linear system of
equations $Ax=b$. It is well known that the (successively over relaxed)
Gauss-Seidel scheme and many of its variants may not converge when $A$ is
neither diagonally dominant nor symmetric positive definite. Can we have a
linearly convergent G-S type algorithm that works for any $A$? In this paper we
answer this question affirmatively by proposing a doubly stochastic G-S
algorithm that is provably linearly convergent (in the mean square error sense)
for any feasible linear system of equations. The key in the algorithm design is
to introduce a nonuniform double stochastic scheme for picking the equation and
the variable in each update step as well as a stepsize rule. These techniques
also generalize to certain iterative alternating projection algorithms for
solving the linear feasibility problem $A x\le b$ with an arbitrary $A$, as
well as certain high-dimensional convex minimization problems. Our results
demonstrate th 查看全文>>