论文标题
一种加权随机kaczmarz方法，用于求解线性系统
A Weighted Randomized Kaczmarz Method for Solving Linear Systems
论文作者
论文摘要
求解线性系统的Kaczmarz方法$ ax = b $将这样的系统解释为等式的集合，$ \ weft \ langle a_i，x \ right \ rangle = b_i $，其中$ a_i $是$ i- $ $ th行的$ th行满足了$ i- $ th方程。收敛率很难建立。假设要归一化的行，$ \ | a_i \ | _ {\ ell^2} = 1 $，Strohmer \＆vershynin确定，如果随机选择方程式的顺序，则$ \ Mathbb {e}〜\ | x_k | x_k -x_k- x \ x \ x \ x \ | _ {\ ell^2} $ comles extement extement。我们证明，如果选择了$ i- $ th行，则可能与$ \ weft | \ weft \ weft \ langle a_i，x_k \ rangle \ rangle -b_i \ right \ right |^{p {比纯粹随机方法快。作为$ p \ rightArrow \ infty $，该方法除非随机化并解释了最大校正方法的效果很好。我们从经验上观察到，该方法计算$ a $的小单数向量的近似值作为副产品。
The Kaczmarz method for solving a linear system $Ax = b$ interprets such a system as a collection of equations $\left\langle a_i, x\right\rangle = b_i$, where $a_i$ is the $i-$th row of $A$, then picks such an equation and corrects $x_{k+1} = x_k + λa_i$ where $λ$ is chosen so that the $i-$th equation is satisfied. Convergence rates are difficult to establish. Assuming the rows to be normalized, $\|a_i\|_{\ell^2}=1$, Strohmer \& Vershynin established that if the order of equations is chosen at random, $\mathbb{E}~ \|x_k - x\|_{\ell^2}$ converges exponentially. We prove that if the $i-$th row is selected with likelihood proportional to $\left|\left\langle a_i, x_k \right\rangle - b_i\right|^{p}$, where $0<p<\infty$, then $\mathbb{E}~\|x_k - x\|_{\ell^2}$ converges faster than the purely random method. As $p \rightarrow \infty$, the method de-randomizes and explains, among other things, why the maximal correction method works well. We empirically observe that the method computes approximations of small singular vectors of $A$ as a byproduct.
