求解线性方程组稀疏解的稀疏贪婪随机Kaczmarz算法

摘要

求解线性方程组的稀疏解在图像重构、信号处理和机器学习等领域中具有广泛的应用，通过引入$l_{\mathrm{1}}$-范数正则化，可以转化为求解一个约束优化问题。基于一种选择系数矩阵工作行的概率准则，提出了稀疏贪婪随机Kaczmarz算法，并给出了有噪声干扰和无噪声干扰情况下该算法的收敛性分析。理论表明本文算法的收缩因子小于随机稀疏Kaczmarz算法的收缩因子。数值实验验证了本文算法的有效性。

关键词

Kaczmarz算法; 稀疏解; 收敛性; 随机迭代

求解线性方程组$\mathit{A}\mathit{x}=\mathit{b}$的稀疏解在图像重构、信号处理和机器学习中具有广泛应用^［1-4］。通过引入$l_{\mathrm{1}}$-范数，求解线性方程组的稀疏解可以转化为求解式（1）正则化最小二乘问题：

$$\underset{\mathit{x}\in {\mathbf{R}}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}f\left(\mathit{x}\right)=\lambda {‖\mathit{x}‖}_{\mathrm{1}}+\frac{\mathrm{1}}{\mathrm{2}}{‖\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}} \mathrm{s}.\mathrm{t}.\mathit{A}\mathit{x}=\mathit{b}$$

（1）

求解该问题常见的算法包括基追踪方法、Bregman方法、共轭梯度方法等^［5-7］。

自Strohmer和Vershynin^［8］证明了随机Kaczmarz算法具有线性收敛率以来，许多专家学者对随机Kaczmarz算法进行了深入的研究^［9-11］。Kaczmarz算法求解的是最小二乘解，通常是稠密的，为了求解线性方程组的稀疏解，文献［12］提出稀疏Kaczmarz算法，该算法在原有的Kaczmarz算法基础之上引入了软阈值函数，解决了最小二乘解稠密性的问题。

在线性方程组相容的情况下，文献［13］证明了稀疏Kaczmarz算法迭代收敛到问题（1）的唯一解。令右端噪声项${\mathit{b}}^{\delta }$满足$\Vert \mathit{b}-{\mathit{b}}^{\delta }{\Vert }_{\mathrm{2}}\le \delta$时，线性方程组可能不相容，文献［14-15］证明了随机Kaczmarz算法的迭代值依期望收敛，并且与无噪声情况下有相同的收缩因子。文献［16］在稀疏Kaczmarz算法基础之上，提出了随机稀疏Kaczmarz算法，并在有噪声干扰和无噪声干扰的情况下给出了随机稀疏Kaczmarz算法的收敛性分析。当系数矩阵的行范数相差较小时，随机Kaczmarz算法将等概率选取$\mathit{A}$的行，此时随机Kaczmarz算法的收敛速率较慢，因此Bai和Wu ^［17］结合贪婪和随机思想，提出一种新的概率准则来选取工作行，形成贪婪随机Kaczmarz算法。更多贪婪随机Kaczmarz算法的研究参见文献［18-21］。

在稀疏随机Kaczmarz算法的基础之上^［21］，受贪婪算法的启发，本文提出稀疏贪婪随机Kaczmarz算法，给出稀疏贪婪随机Kaczmarz算法在有噪声干扰和无噪声干扰情况下的收敛性分析，并以大量的数值实验验证本文算法的计算效率。

符号标记如下，定义$\widehat{\mathit{x}}$为线性方程组$\mathit{A}\mathit{x}=\mathit{b}$的解，其中$\mathit{A}\in {\mathbf{R}}^{m\times n}$，$\mathit{b}\in {\mathbf{R}}^m$，${\mathit{a}}_i$表示系数矩阵A的第$i$行。支持集S=$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\widehat{\mathit{x}})=\left\{j\in \{\mathrm{1},\dots ,n\}\mid {\widehat{\mathit{x}}}_j\ne \mathrm{0}\right\}$是列向量$\widehat{\mathit{x}}$中非零元的下标所构成的集合，${\mathit{A}}_S$是$\mathit{A}$的子矩阵，由支持集$S$中的指标选取系数矩阵$\mathit{A}$的列构成，${\mathit{a}}_{i_S}$表示的是${\mathit{A}}_S$的第$i$行，${\mathit{x}}_S$是在支持集$S$限制下的列向量；定义$\widehat{\sigma }$${}_{\mathrm{m}\mathrm{i}\mathrm{n}}(\mathit{A})=\mathrm{m}\mathrm{i}\mathrm{n}\left\{{\sigma }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}_J\right)\mid J\subset \{\mathrm{1},\dots ,n\},{\mathit{A}}_J\ne \mathrm{0}\right\}$为子矩阵${\mathit{A}}_J$的最小奇异值，其中${\mathit{A}}_J$为指标集$J$中A的列构成的子矩阵，令$\tilde{\kappa }=\frac{\Vert \mathit{A}{\Vert }_F}{{\widehat{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}(\mathit{A})}$；$\odot$为哈达玛积（Hadamard product）；$\widehat{k}$为对支持集大小的估计值；${\mathit{w}}_j$为稀疏随机Kaczmarz算法第$j$次迭代的权重值，${\mathit{w}}_j\in {\mathbf{R}}^{m\times \mathrm{1}}$。

1 稀疏贪婪随机Kaczmarz算法

当$\mathit{A}\mathit{x}=\mathit{b}$的解$\mathit{x}$稀疏时，文献［21］提出了稀疏随机Kaczmarz算法，加快了算法的收敛速率（算法1）。

算法1  　稀疏随机Kaczmarz算法^［21］。①输入$\mathit{A}\in {\mathbf{R}}^{m\times n}$，$\mathit{b}\in {\mathbf{R}}^m$，最大迭代数M和估计的支持集的大小$\widehat{k}$。②输出${\mathit{x}}_j\mathrm{。}$③初始化$S=\left\{\mathrm{1},\dots ,n\right\}$，${\mathit{x}}_{\mathrm{0}}=\mathrm{0}$，$j=\mathrm{0}\mathrm{。}$④当$j\le M$时，置$j=j+\mathrm{1}$。⑤选择行向量${\mathit{a}}_i,i\in \{\mathrm{1},\dots ,n\}$，每一行对应的概率为$\frac{\Vert {\mathit{a}}_{\mathit{i}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}$。⑥确定估计的支持集$S$，$S=\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}\left({\left.{\mathit{x}}_{j-\mathrm{1}}\right|}_{\mathrm{m}\mathrm{a}\mathrm{x}\{\widehat{k},n-j+\mathrm{1}\}}\right)\mathrm{。}$⑦生成权重值${\mathit{w}}_j$，${\mathit{w}}_j(l)=\left\{\begin{array}{ll}\mathrm{1}& l\in S\\ \frac{\mathrm{1}}{\sqrt[]{j}}& l\in S^c\end{array}\right.$。⑧。⑨转步骤④。

稀疏随机Kaczmarz算法可以用比随机Kaczmarz算法更少的迭代步数找到最小二乘解。由于支持集和稀疏度都是未知的，因此稀疏随机Kaczmarz算法从支持集中所有元素的稀疏度的初始估计开始，然后在每一次迭代中，稀疏随机Kaczmarz算法通过去掉向量$\mathit{x}$中数量级最小的元素下标来更新估计的支持集。该算法第$j$次迭代的加权准则为

$${\mathit{w}}_j(l)=\left\{\begin{array}{ll}\mathrm{1}& l\in S\\ \frac{\mathrm{1}}{\sqrt[]{j}}& l\in S^c\end{array}\right.$$

其中，$j$为迭代步数。当$j\to \mathrm{\infty }$时，${\mathit{w}}_j\odot {\mathit{a}}_i\to {\mathit{a}}_{i_S}$，因此原线性方程组退化成

$$\mathit{b}=\mathit{A}\mathit{x}={\mathit{A}}_S{\mathit{x}}_S$$

由于$\kappa \left({\mathit{A}}_S\right)\le \kappa (\mathit{A})$，因此稀疏随机Kaczmarz算法的收敛因子小于随机Kaczmarz算法。但是由于最小二乘解总是稠密的，该算法在求解超定线性方程组时，虽然在稀疏解零元对应位置上的元素很小，但仍然不等于零，因此在文献中提出稀疏Kaczmarz算法，文献［16］在稀疏Kaczmarz算法的基础上，提出了随机稀疏Kaczmarz算法（算法2）。

算法2  　随机稀疏Kaczmarz算法^［16］。①输入$\mathit{A}\in {\mathbf{R}}^{m\times n}$，$\mathit{b}\in {\mathbf{R}}^m$，最大迭代数$M$。②输出${\mathit{x}}_k$。③初始化：${\mathit{x}}_{\mathrm{0}}={\mathit{x}}_{\mathrm{0}}^{\mathrm{*}}=\mathrm{0}$。④置$k=\mathrm{0}$，当k$\le M-\mathrm{1}$时。⑤选择行向量${\mathit{a}}_{i_k},i_k\in \{\mathrm{1},\dots ,n\}$，每一行对应的概率为$\frac{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}$。⑥。⑦${\mathit{x}}_{k+\mathrm{1}}=S_{\lambda }\left({\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}\right)$。⑧转步骤④。

算法2中$\lambda >\mathrm{0}$，$S_{\lambda }(\mathit{x})=\mathrm{m}\mathrm{a}\mathrm{x}\{|\mathit{x}|-\lambda ,\mathrm{0}\}\cdot \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(\mathit{x})$。结合稀疏随机Kaczmarz算法和随机稀疏Kaczmarz算法的思想，受贪婪算法的启发，本文提出稀疏贪婪随机Kaczmarz算法，在保证算法能够计算出稀疏解的同时，通过贪婪的概率准则来选择工作行从而达到加快算法收敛速度的目的。算法3给出稀疏贪婪随机Kaczmarz算法。

算法3  　稀疏贪婪随机Kaczmarz算法。①输入$\mathit{A}\in {\mathbf{R}}^{m\times n}$，$\mathit{b}\in {\mathbf{R}}^m$，最大迭代数$M$和估计的支持集的大小$\widehat{k}$。②输出${\mathit{x}}_k$。③初始化$S=\left\{\mathrm{1},\dots ,n\right\}$，${\mathit{x}}_{\mathrm{0}}={\mathit{x}}_{\mathrm{0}}^{\mathrm{*}}=\mathrm{0}\mathrm{。}\mathrm{④}$置$k=\mathrm{0}$时，当k$\le M-\mathrm{1}$时。⑤计算

$${ϵ}_k=\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{\Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}}\underset{\mathrm{1}\le i_k\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}\right\}+\frac{\mathrm{1}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}\right)$$

（2）

⑥决定正整数指标集

$${\mathrm{𝒰}}_k=\left\{i_k|{\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}\ge {ϵ}_k\Vert b-A{x}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}\right\}$$

（3）

⑦计算向量${\tilde{\mathit{r}}}_k$的第$i$行${\tilde{\mathit{r}}}_k^{(i)}$

$${\tilde{\mathit{r}}}_k^{(i)}=\left\{\begin{array}{ll}{\mathit{b}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k& \mathrm{若}i\in {\mathrm{𝒰}}_k\\ \mathrm{0}& \mathrm{其}\mathrm{他}\end{array}\right.$$

⑧以概率准则$p(r_{\mathrm{r}\mathrm{o}\mathrm{w}}=i_k)\frac{{\left|r_k^{(i)}\right|}^{\mathrm{2}}}{\Vert {\mathit{r}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}}$选择$i_k\in {\mathrm{𝒰}}_k$。⑨确定估计的支持集$S$，如下：$S=\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}\left({\left.{\mathit{x}}_k\right|}_{\mathrm{m}\mathrm{a}\mathrm{x}\{\widehat{k},n-k\}}\right)$。⑩生成权重值${\mathit{w}}_{k+\mathrm{1}}$

$${\mathit{w}}_{k+\mathrm{1}}\left(l\right)=\left\{\begin{array}{ll}\mathrm{1}& l\in S\\ \frac{\mathrm{1}}{\sqrt[]{k+\mathrm{1}}}& l\in S^c\end{array}\right.$$

⑪计算

⑫计算 ${\mathit{x}}_{k+\mathrm{1}}=S_{\lambda }\left({\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}\right)$。⑬转步骤④。

2 稀疏贪婪随机Kaczmarz算法的收敛性分析

为了证明求解正则基追踪问题（1）稀疏贪婪随机Kaczmarz算法依期望线性收敛，先回顾一些基本的概念和性质^［22］。

令$f:{\mathbf{R}}^n\to \mathbf{R}$是凸函数，用$\partial f(\mathit{x})$表示$f$在$\mathit{x}\in {\mathbf{R}}^n$的次微分

其中，$\partial f(\mathit{x})$是一个非空紧凸集。

定义1  　凸函数$f:{\mathbf{R}}^n\to \mathbf{R}$，如果存在$\alpha >\mathrm{0}$，使得对任意的$\mathit{x},\mathit{y}\in {\mathbf{R}}^n$且${\mathit{x}}^{\mathrm{*}}\in \partial f(\mathit{x})$，有

那么$f$是强凸的，当和$\alpha$的具体值相关时，则称$f$是$\alpha$-强凸的。

定义2  ^［22］     如果$f:{\mathbf{R}}^n\to \mathbf{R}$是$\alpha$-强凸，那么它的共轭函数可微且有$\mathrm{1}/\alpha -\mathrm{L}\mathrm{i}\mathrm{p}\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{t}\mathrm{z}$连续梯度，例如

$${\left(\nabla f^{\mathrm{*}}\left({\mathit{x}}^{\mathrm{*}}\right)-\nabla f^{\mathrm{*}}\left({\mathit{y}}^{\mathrm{*}}\right)\right)}_{\mathrm{2}}\le \frac{\mathrm{1}}{\alpha }\cdot {\left({\mathit{x}}^{\mathrm{*}}-{\mathit{y}}^{\mathrm{*}}\right)}_{\mathrm{2}},\forall {\mathit{x}}^{\mathrm{*}},{\mathit{y}}^{\mathrm{*}}\in {\mathbf{R}}^n$$

有式（4）不等式成立：

（4）

定义3  　令$f:{\mathbf{R}}^n\to \mathbf{R}$是强凸函数，那么$\mathit{x},\mathit{y}\in {\mathbf{R}}^n$之间的Bregman距离$D_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\mathit{y})$由$f$和一个次梯度${\mathit{x}}^{\mathrm{*}}\in \partial f(\mathit{x})$定义

如果$f$是可微的，那么有$\partial f(\mathit{x})=\{\nabla f(\mathit{x})\}$，因为，所以可以简化来写$D_f(\mathit{x},\mathit{y})=D_f^{x^{\mathrm{*}}}(\mathit{x},\mathit{y})$。

下面的引理都遵循强凸性的假设^［13］，给出了随机方法收敛性分析所需的Bregman距离的关键性质。

引理1  ^［13］     令$f:{\mathbf{R}}^n\to \mathbf{R}$是$\alpha$强凸函数，对任意的$\mathit{x},\mathit{y}\in {\mathbf{R}}^n$和${\mathit{x}}^{\mathrm{*}}\in \partial f(\mathit{x})\mathrm{、}{\mathit{y}}^{\mathrm{*}}\in \partial f(\mathit{y})$有

因此

$$D_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\mathit{y})=\mathrm{0} \iff \mathit{x}=\mathit{y}$$

对于序列${\mathit{x}}_k$和${\mathit{x}}_k^{\mathrm{*}}\in \partial f({\mathit{x}}_k)$，$D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\mathit{y}\right)$的有界性意味着${\mathit{x}}_k$和${\mathit{x}}_k^{\mathrm{*}}$有界。如果$f$有一个$L–\mathrm{L}\mathrm{i}\mathrm{p}\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{t}\mathrm{z}$连续梯度，那么也有$D_f(\mathit{x},\mathit{y})\le \frac{L}{\mathrm{2}}\cdot \Vert \mathit{x}-\mathit{y}{\Vert }_{\mathrm{2}}^{\mathrm{2}}$。

定义4  　令$f:{\mathbf{R}}^n\to \mathbf{R}$是强凸函数，且$C\subset {\mathbf{R}}^n$是一个非空闭凸集，则$\mathit{x}$到$C$上的Bregman投影是关于$f$和${\mathit{x}}^{\mathrm{*}}\in \partial f(\mathit{x})$满足下式的唯一点${\mathrm{\Pi }}_C^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x})\in C$：

$$D_f^{{\mathit{x}}^{\mathrm{*}}}\left(\mathit{x},{\mathrm{\Pi }}_C^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x})\right)=\underset{\mathit{y}\in C}{\mathrm{m}\mathrm{i}\mathrm{n}}{D}_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\mathit{y})=:\mathrm{d}\mathrm{i}\mathrm{s}{\mathrm{t}}_f^{{\mathit{x}}^{\mathrm{*}}}{(\mathit{x},C)}^{\mathrm{2}}$$

对于可微的$f$，可以简化为${\mathrm{\Pi }}_C(\mathit{x})$和$\mathrm{d}\mathrm{i}\mathrm{s}{\mathrm{t}}_f(\mathit{x},C)$。

引理2  ^［13］     令$f:{\mathbf{R}}^n\to \mathbf{R}$是强凸函数，x到C上的Bregman投影点$\widehat{\mathit{x}}\in C$是与$f$和${\mathit{x}}^{\mathrm{*}}\in \partial f(x)$相关，当且仅当存在一个$\widehat{\mathit{x}}$${}^{\mathrm{*}}\in \partial f(\widehat{\mathit{x}})$满足式（5）或式（6）：

（5）

$$D_f^{{\widehat{\mathit{x}}}^{\mathrm{*}}}(\widehat{\mathit{x}},\mathit{y})\le D_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\mathit{y})-D_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\widehat{\mathit{x}})\forall \mathit{y}\in C$$

（6）

可以叫这样的点${\widehat{\mathit{x}}}^{\mathrm{*}}$是$\widehat{\mathit{x}}={\mathrm{\Pi }}_C^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x})$的可允次梯度。

引理3表明，Bregman投影到仿射子空间和半空间可以通过求解可微共轭函数$f^{\mathrm{*}}$的无约束优化问题来计算。

引理3  ^［13］     令$f:{\mathbf{R}}^n\to \mathbf{R}$是$\alpha$-强凸函数，$\mathit{A}\in {\mathbf{R}}^{m\times n}$，$\mathit{b}\in {\mathbf{R}}^m$，$\mathit{u}\in {\mathbf{R}}^n$和$\beta \in \mathbf{R}$。

（1）$\mathit{x}\in {\mathbf{R}}^n$到仿射空间$L(\mathit{A},\mathit{b}):=\{\mathit{x}\in {\mathbf{R}}^n|$$\mathit{A}\mathit{x}=\mathit{b}\}\ne \mathrm{\varnothing }$的Bregman投影是

$$\widehat{\mathit{x}}:={\mathrm{\Pi }}_{L(\mathit{A},\mathit{b})}^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x})=\nabla f^{\mathrm{*}}\left({\mathit{x}}^{\mathrm{*}}-{\mathit{A}}^{\mathrm{T}}\widehat{\mathit{w}}\right)$$

其中$\widehat{\mathit{w}}\in {\mathbf{R}}^m$是下式的解：

更重要的是，根据引理2，${\widehat{\mathit{x}}}^{\mathrm{*}}:={\mathit{x}}^{\mathrm{*}}-{\mathit{A}}^{\mathrm{T}}\widehat{\mathit{w}}$是$\widehat{\mathit{x}}$的可允次梯度。如果$\mathit{A}$行满秩，那么对任意的$\mathit{y}\in L(\mathit{A},\mathit{b})$有

$$D_f^{{\mathit{z}}^{\mathrm{*}}}(\mathit{z},\mathit{y})\le D_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\mathit{y})-\frac{\alpha }{\mathrm{2}}\cdot {\left({\left(\mathit{A}{\mathit{A}}^{\mathrm{T}}\right)}^{-\frac{\mathrm{1}}{\mathrm{2}}}(\mathit{A}\mathit{x}-\mathit{b})\right)}_{\mathrm{2}}^{\mathrm{2}}$$

（2）$\mathit{x}\in {\mathbf{R}}^n$到超平面满足$\mathit{u}\ne \mathrm{0}$的Bregman投影是

$$\widehat{\mathit{x}}:={\mathrm{\Pi }}_{H(\mathit{u},\mathit{\beta })}^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x})=\nabla f^{\mathrm{*}}\left({\mathit{x}}^{\mathrm{*}}-\widehat{t}\cdot \mathit{u}\right)$$

其中 $\widehat{t}\in \mathbf{R}$是下式的解：

$$\underset{t\in \mathbf{R}}{\mathrm{m}\mathrm{i}\mathrm{n}}{f}^{\mathrm{*}}\left({\mathit{x}}^{\mathrm{*}}-t\cdot \mathit{u}\right)+t\cdot \beta$$

更重要的是$\widehat{\mathit{x}}$${}^{\mathrm{*}}:={\mathit{x}}^{\mathrm{*}}-\widehat{t}\cdot \mathit{u}$是$\widehat{\mathit{x}}$的可允次梯度，对任意的$\mathit{y}\in H(\mathit{u},\beta )$有

如果$\mathit{x}$不是在半空间，那么有必要满足$\widehat{t}>\mathrm{0}$，${\mathrm{\Pi }}_{H_{\le }(\mathit{u},\beta )}^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x})=\widehat{\mathit{x}}$且上面的不等式对任意的$\mathit{y}\in H_{\le }(\mathit{u},\beta )$都成立。

引理4^［16］对于任意的$\mathit{x}\in {\mathbf{R}}^n$满足$\partial f(\mathit{x})\bigcap \mathrm{ℛ}\left({\mathit{A}}^{\mathrm{T}}\right)\ne \mathrm{\varnothing }$和任意的${\mathit{x}}^{\mathrm{*}}={\mathit{A}}^{\mathrm{T}}\mathit{y}\in \partial f(\mathit{x})\bigcap \mathrm{ℛ}\left({\mathit{A}}^{\mathrm{T}}\right)$，有

$$D_f^{{\mathit{x}}^{\mathrm{*}}}(\mathit{x},\widehat{\mathit{x}})\le \frac{\mathrm{1}}{{\widehat{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{2}}(\mathit{A})}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\cdot \Vert \mathit{A}\mathit{x}-\mathit{b}{\Vert }_{\mathrm{2}}^{\mathrm{2}}$$

定理1  （无噪声情况） 令$\tilde{\kappa }=\frac{\Vert \mathit{A}{\Vert }_F}{{\widehat{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}(\mathit{A})}$，${ϵ}_k=\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{{\left(\mathit{b}-\mathit{A}{\mathit{x}}_k\right)}_{\mathrm{2}}^{\mathrm{2}}}\mathrm{m}\mathrm{a}{\mathrm{x}}_{\mathrm{1}\le i_k\le m}\left\{\frac{{\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}\right\}+\frac{\mathrm{1}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}\right)$。稀疏贪婪随机Kaczmarz算法所产生的迭代序列${\mathit{x}}_k$依期望线性收敛到唯一解$\widehat{\mathit{x}}$，其收缩因子为

$$q=\mathrm{1}-\frac{\mathrm{1}}{{\tilde{\kappa }}^{\mathrm{2}}}\cdot \frac{{ϵ}_k\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }$$

（7）

从而

$$E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\right]\le q\cdot E\left[D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)\right]$$

且

$$E\left[{\left({\mathit{x}}_k-\widehat{\mathit{x}}\right)}_{\mathrm{2}}\right]\le q^{\frac{k}{\mathrm{2}}}\cdot \sqrt[]{\mathrm{2}\lambda \Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{1}}+\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}$$

证明  　根据引理3的（2）中的估计，有式（8）成立：

（8）

对式（8）两边同时取条件期望有

（9）

根据式（2）和式（3）的定义，有不等式（10）成立：

$${\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}\ge {ϵ}_k\Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}},\forall i_k\in {\mathrm{𝒰}}_k$$

（10）

将式（10）代入到式（9）中，从而有

$$E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\mid i_{\mathrm{0}},\dots ,i_{k-\mathrm{1}}\right]\le \mathrm{ }{D}_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)-{\sum }_{i_k\in {\mathrm{𝒰}}_k}\frac{{\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{\sum }_{i\in {\mathrm{𝒰}}_k}{\left|{\mathit{b}}_i-{\mathit{a}}_i{\mathit{x}}_k\right|}^{\mathrm{2}}}\cdot \mathrm{ }\frac{\mathrm{1}}{\mathrm{2}}\cdot \frac{|{\mathit{a}}_{i_k}({\mathit{x}}_k-\widehat{\mathit{x}}){|}^{\mathrm{2}}}{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}\le D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)-\frac{\mathrm{1}}{\mathrm{2}}\cdot \frac{{\sum }_{i_k\in {\mathrm{𝒰}}_k}|{\mathit{a}}_{i_k}({\mathit{x}}_k-\widehat{\mathit{x}}){|}^{\mathrm{2}}}{{\sum }_{i\in {\mathrm{𝒰}}_k}{\left|{\mathit{b}}_i-{\mathit{a}}_i{\mathit{x}}_k\right|}^{\mathrm{2}}}\cdot {ϵ}_k\cdot \Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}=D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)-\frac{\mathrm{1}}{\mathrm{2}}\cdot \frac{{\sum }_{i_k\in {\mathrm{𝒰}}_k}|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k{|}^{\mathrm{2}}}{{\sum }_{i\in {\mathrm{𝒰}}_k}{\left|{\mathit{b}}_i-{\mathit{a}}_i{\mathit{x}}_k\right|}^{\mathrm{2}}}\cdot {ϵ}_k\cdot \Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}=D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)-\frac{\mathrm{1}}{\mathrm{2}}\cdot {ϵ}_k\cdot \Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}$$

（11）

由式（11）的推导，可以得出

$$E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\mid i_{\mathrm{0}},\dots ,i_{k-\mathrm{1}}\right]\le D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)-\frac{\mathrm{1}}{\mathrm{2}}\cdot {ϵ}_k\cdot \Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}$$

根据引理4有

$$\begin{array}{l}E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\mid i_{\mathrm{0}},\dots ,i_{k-\mathrm{1}}\right]\le \\ D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)-\frac{\mathrm{1}}{\mathrm{2}}\cdot {ϵ}_k\cdot \frac{{\tilde{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{2}}|\hat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }\cdot D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)\le \\ \left(\mathrm{1}-\frac{\mathrm{1}}{\mathrm{2}}\cdot {ϵ}_k\cdot {\tilde{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{2}}\frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }\right)\cdot D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)\end{array}$$

（12）

由于$\tilde{\kappa }=\frac{\Vert \mathit{A}{\Vert }_F}{{\tilde{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}(\mathit{A})}$，从而

$$E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\mid i_{\mathrm{0}},\dots ,i_{k-\mathrm{1}}\right]\le (\mathrm{1}-\frac{\mathrm{1}}{{\tilde{\kappa }}^{\mathrm{2}}}\cdot \frac{{ϵ}_k\cdot \Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda })\cdot D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)$$

（13）

令$q=\mathrm{1}-\frac{\mathrm{1}}{{\tilde{\kappa }}^{\mathrm{2}}}\cdot \frac{{ϵ}_k\cdot \Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }$，则

$$E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\right]\le q\cdot E\left[D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)\right]$$

根据引理1，令$\alpha$=1可得

$$E\left[\Vert {\mathit{x}}_k-\widehat{\mathit{x}}{\Vert }_{\mathrm{2}}\right]\le q^{\frac{k}{\mathrm{2}}}\cdot \sqrt[]{\mathrm{2}\lambda \Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{1}}+\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}$$

证毕。

定理2  　（有噪声情况） 已知右段噪声项${\mathit{b}}^{\delta }\in {\mathbf{R}}^m$满足$\Vert \mathit{b}-{\mathit{b}}^{\delta }{\Vert }_{\mathrm{2}}\le \delta$。如果稀疏贪婪随机Kaczmarz算法的迭代值${\mathit{x}}_k$由${\mathit{b}}^{\delta }$替代$\mathit{b}$来计算，那么有噪声干扰和无噪声干扰有相同的收缩因子

$q=\mathrm{1}-\frac{\mathrm{1}}{{}^{{\tilde{\kappa }}^{\mathrm{2}}}}\cdot \frac{{ϵ}_k\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }$且

$$E\left[{\left({\mathit{x}}_k-\widehat{\mathit{x}}\right)}_{\mathrm{2}}\right]\le q^{\frac{k}{\mathrm{2}}}\cdot \sqrt[]{\mathrm{2}\lambda \Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{1}}+\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}+\sqrt[]{\frac{\mathrm{2}|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{4}\lambda }{{ϵ}_k\cdot |\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}}\cdot \frac{\delta }{\Vert \mathit{A}{\Vert }_F\cdot {\tilde{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}(\mathit{A})}$$

证明  　令

$${\mathit{x}}_k^{\delta }:=\widehat{\mathit{x}}+\frac{{\mathit{b}}_{i_k}^{\delta }-{\mathit{b}}_{i_k}}{\Vert a_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}\cdot {\mathit{a}}_{i_k}\in H\left({\mathit{a}}_{i_k},{\mathit{b}}_{i_k}^{\delta }\right)$$

和式（8）相类似有

（14）

将式（14）进行简单的变换等价于式（15）：

（15）

在稀疏贪婪随机Kaczmarz算法中有 因此

而

所以

类似于无噪声情况的证明方法可以得到

$$\begin{array}{l}E\left[D_f^{{\mathit{x}}_{k+\mathrm{1}}^{\mathrm{*}}}\left({\mathit{x}}_{k+\mathrm{1}},\widehat{\mathit{x}}\right)\right]\le q\cdot E\left[D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)\right]+\\ \frac{\mathrm{1}}{\mathrm{2}}\cdot \frac{{\left({\mathit{b}}^{\delta }-\mathit{b}\right)}_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}\end{array}$$

通过归纳得出

$$\begin{array}{l}E\left[D_f^{{\mathit{x}}_k^{\mathrm{*}}}\left({\mathit{x}}_k,\widehat{\mathit{x}}\right)\right]\le q^k\cdot \left(\lambda \Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{1}}+\frac{\mathrm{1}}{\mathrm{2}}\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}\right)+\\ \frac{\mathrm{1}}{\mathrm{1}-q}\cdot \frac{\mathrm{1}}{\mathrm{2}}\cdot \frac{{\left({\mathit{b}}^{\delta }-\mathit{b}\right)}_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}\end{array}$$

由引理1，令$\alpha =\mathrm{1}$，且$\sqrt[]{u+v}\le \sqrt[]{u}+\sqrt[]{v}$，有

$$E\left[{\left({\mathit{x}}_k-\widehat{\mathit{x}}\right)}_{\mathrm{2}}\right]\le q^{\frac{k}{\mathrm{2}}}\cdot \sqrt[]{\mathrm{2}\lambda \Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{1}}+\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}+\sqrt[]{\frac{\mathrm{1}}{\mathrm{1}-q}\cdot \frac{\Vert {\mathit{b}}^{\delta }-\mathit{b}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}}$$

（16）

将$q=\mathrm{1}-\frac{\mathrm{1}}{{\tilde{\kappa }}^{\mathrm{2}}}\cdot \frac{{ϵ}_k\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }$代入式（16）中就可以得到

$$E\left[{\left({\mathit{x}}_k-\widehat{\mathit{x}}\right)}_{\mathrm{2}}\right]\le q^{\frac{k}{\mathrm{2}}}\cdot \sqrt[]{\mathrm{2}\lambda \Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{1}}+\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}+\sqrt[]{\frac{\mathrm{2}|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{4}\lambda }{{ϵ}_k\cdot |\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}}\cdot \frac{\delta }{\Vert \mathit{A}{\Vert }_F\cdot {\tilde{\sigma }}_{\mathrm{m}\mathrm{i}\mathrm{n}}(\mathit{A})}$$

证毕。

注意到稀疏贪婪随机Kaczmarz算法的收缩因子为

$$q=\mathrm{1}-\frac{\mathrm{1}}{{\tilde{\kappa }}^{\mathrm{2}}}\cdot \frac{{ϵ}_k\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }$$

文献［16］定理3.2中随机稀疏Kaczmarz算法的收缩因子为

$$\tilde{q}=\mathrm{1}-\frac{\mathrm{1}}{{\tilde{\kappa }}^{\mathrm{2}}}\cdot \frac{\mathrm{1}}{\mathrm{2}}\cdot \frac{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{|\widehat{\mathit{x}}{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}+\mathrm{2}\lambda }$$

因

$$\underset{\mathrm{1}\le i_k\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}\right)\ge {\displaystyle \sum _{i_k=\mathrm{1}}^m}\frac{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}\cdot \frac{{\left|{\mathit{b}}_{i_k}-{\mathit{a}}_{i_k}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\Vert {\mathit{a}}_{i_k}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}=\frac{\Vert \mathit{b}-\mathit{A}{\mathit{x}}_k{\Vert }_{\mathrm{2}}^{\mathrm{2}}}{\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}}$$

从而${ϵ}_k\Vert \mathit{A}{\Vert }_F^{\mathrm{2}}\ge \mathrm{1}$，因此

$$q\le \tilde{q}$$

由此可以得出稀疏贪婪随机Kaczmarz算法的收缩因子小于随机稀疏Kaczmarz算法的收缩因子。一般而言，收缩因子越小，收敛速度越快，因此理论分析表明稀疏贪婪随机Kaczmarz算法收敛速度会比原有的随机稀疏Kaczmarz算法的收敛速度更快。

3 数值实验

通过随机生成的高斯矩阵和矩阵市场中的矩阵2个数值实验算例来比较稀疏贪婪随机Kaczmarz（SGRK）算法、随机稀疏Kaczmarz（RaSK）算法和稀疏随机Kaczmarz（SRK）算法的收敛速度。为了能够使三者收敛到相同解上进行比较，在本次数值实验中，在稀疏随机Kaczmarz算法最后一步加上了软阈值函数$S_{\lambda }(\mathit{x})$参与迭代以保证求得稀疏解。对相同参数的同一个线性方程组$\mathit{A}\mathit{x}=\mathit{b}$做了20次试验，得到迭代步数（$\mathrm{I}\mathrm{T}$）和$\mathrm{C}\mathrm{P}\mathrm{U}$计算时间的平均值。解的相对误差（RSE）定义为

$$r_{\mathrm{R}\mathrm{S}\mathrm{E}}=\frac{\Vert {\mathit{x}}_k-\widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}{\Vert \widehat{\mathit{x}}{\Vert }_{\mathrm{2}}^{\mathrm{2}}}.$$

例1   利用Matlab软件中的randn函数随机生成系数矩阵$\mathit{A}$和${\mathit{x}}_{n\times \mathrm{1}}$，其中有$k\times n$个非零元，之后利用$\mathit{b}=\mathit{A}\times \mathit{x}$得到相容线性方程组，初始向量${\mathit{x}}_{\mathrm{0}}=\mathrm{0}$。取$\tilde{k}=\mathrm{2}\times k$，通过$k$来设置解的稀疏度，其中$\tilde{k}$是对稀疏度的初始估计值。

当解稀疏度为0.2、0.4、0.6以及0.8时，表1和表2分别给出了系数矩阵$\mathit{A}$的维数为$\mathrm{1}\mathrm{000}\times \mathrm{150}$和$\mathrm{4}\mathrm{000}\times \mathrm{300}$时的SGRK算法、RaSK算法和SRK算法的迭代步数和计算时间。

表1 m = 1 000、n = 150时SGRK、RaSK 和 SRK 的迭代步数和计算时间

Tab. 1 Iteration steps and computation time of SGRK, RaSK and SRK（m = 1 000、n = 150）

稀疏度	SGRK		RaSK		SRK
	迭代步数	计算时间	迭代步数	计算时间	迭代步数	计算时间
0.2 n	158.80	0.014 6	2 496.50	0.053 0	1 082.10	0.038 1
0.4 n	273.35	0.023 5	2 491.20	0.053 3	1 972.00	0.064 9
0.6 n	360.65	0.026 3	2 552.00	0.055 2	2 559.40	0.082 7
0.8 n	363.05	0.025 9	2 597.50	0.054 7	2 557.30	0.080 4

表 2 m = 4 000、n = 300时SGRK、RaSK 和 SRK 的迭代步数和计算时间

Tab. 2 Iteration steps and computation time of SGRK, RaSK and SRK（m = 4 000、n = 300）

稀疏度	SGRK		RaSK		SRK
	迭代步数	计算时间	迭代步数	计算时间	迭代步数	计算时间
0.2 n	259.95	0.094 0	4 224.40	0.226 4	2 057.00	0.152 6
0.4 n	418.45	0.146 8	4 302.50	0.229 9	3 736.00	0.306 7
0.6 n	522.90	0.188 2	4 344.60	0.245 1	4 372.70	0.330 1
0.8 n	523.30	0.190 9	4 435.90	0.237 3	4 442.40	0.321 0

当稀疏度为 0.2 和 0.8 时，图1和图2分别给出系数矩阵A的维数为1 000 × 150和4 000 × 300时3种算法近似解的相对误差随迭代步数变化的曲线。

图1 当矩阵A的维数为1 000 × 150时SGRK、RaSK和SRK算法的收敛曲线

Fig. 1 Convergence curves of SGRK, RaSK and SRK methods for Example 1 at a matrix A of 1 000 × 150

图2 当矩阵A的维数为4 000 × 300时SGRK、RaSK和SRK算法的收敛曲线

Fig. 2 Convergence curves of SGRK, RaSK and SRK methods for Example 1 at a matrix A of 4 000 × 300

通过表1和表2中的实验数据以及图1和图2中的变化曲线可以看出，随着稀疏解非零元个数的不断增加，SRK算法的收敛曲线不断向RaSK算法的收敛曲线靠拢，这是因为SRK算法在对应零元位置上乘以权重，加速减小零元位置上的元素，因此在零元较多的情况下，SRK算法的收敛速度更快。但是，由于SRK算法的计算过程较为复杂，因此在计算时间上一开始低于RaSK算法，后来在迭代步数不明显占优的情况下，计算时间要多于RaSK算法。SGRK算法在2种算法的基础之上，每次以贪婪的概率准则随机选取行指标进行迭代，因此SGRK算法的计算时间和迭代步数都要优于其他2种算法。

例2   选取了矩阵市场中的一些矩阵进行数值实验。为了得到超定的系数矩阵，将所有的欠定矩阵取转置之后再做数值实验，取稀疏度估计为 $\widehat{k}$ = 2k，稀疏度k=0.2 n。表3列出的是测试矩阵的相关信息。

表3 矩阵信息

Tab. 3 Matrix information for Example 2

矩阵名称	阶数	稠密度/%	秩	条件数
WorldCities	$315\times 100$	23.87	100	66.00
bibd_13_6	78×1 716	19.23	78	6.27
Crew1 Trec8	135 × 6 469 $23\times 84$	5.38 28.42	135 23	18.2 26.89

对于测试的矩阵，表4给出了SGRK算法、RaSK算法和SRK算法的迭代步数和运行时间。

表4 SGRK、RaSK 和 SRK 的迭代步数和计算时间

Tab. 4 Iteration steps and computation time of SGRK, RaSK and SRK

矩阵名称	SGRK		RaSK		SRK
	迭代步数	计算时间	迭代步数	计算时间	迭代步数	计算时间
bibd_13_6	134.40	0.015 0	1 681.80	0.078 9	753.15	0.039 4
Trec8	53.85	0.002 4	10 697.00	0.217 8	580.80	0.015 1
crew1	433.35	0.118 0	13 222.00	1.468 4	6 050.30	0.747 1
WorldCities	482.30	0.032 1	19 706.00	0.654 5	2 909.10	0.116 6

图3对应于表4，给出了3种算法近似解的相对误差随着迭代步数的变化曲线。通过对比可以发现，在无噪声干扰的情况下，SGRK算法的迭代步数和CPU运行时间都优于原来的RaSK算法和SRK 算法。

图3 SGRK、RaSK 和 SRK 算法在稀疏度 k = 0.2 n时的收敛曲线

Fig. 3 Convergence curves of SGRK, RaSK and SRK methods convergence curve for Examples 2 at a sparsity k = 0.2 n

图4和图5描述SGRK算法、SRK算法和RaSK算法在有噪声干扰的系统中的一些数值实验结果。用Matlab软件中的randn随机生成高斯矩阵和范数为0.02的独立高斯噪声进行数值实验。

图4 SGRK、RaSK 和 SRK 算法在稀疏度k = 0.2 n时误差阈值和实际误差比较

Fig. 4 Comparison of error threshold and actual error of SGRK, RaSK and SRK methods at a sparsity k = 0.2 n

图5 SGRK、RaSK 和 SRK 算法在稀疏度k = 0.6 n时误差阈值和实际误差比较

Fig. 5 Comparison of error threshold and actual error of SGRK, RaSK and SRK methods at a sparsity k = 0.6 n

图4和图5中水平的实线是SGRK算法的相对误差阈值，水平的虚线是RaSK算法的相对误差阈值，图4是在有噪声干扰的情况下，解的稀疏度为0.2时3种算法的近似解的相对误差随迭代步数的变化曲线。其中图4a描述系数矩阵A的维数为1 000 × 150时的收敛情况，图4b描述的是系数矩阵A的维数为4 000×300时的收敛情况。

图5是在有噪声干扰的情况下，解的稀疏度为0.6时3种算法的近似解的相对误差随迭代步数的变化曲线。其中图5a和图5b分别画出的是系数矩阵A的维数为1 000 × 150和4 000×300时3种算法的收敛曲线。

由图4和图5可以看出，在有噪声干扰的情况下，SGRK算法优于其他2种算法最先达到稳定阈值。另外，在图4和图5中分别用水平的实线和虚线画出了SGRK算法的相对误差阈值和RaSK算法的相对误差阈值，通过数值实验表明，由定理2中 SGRK算法推导出来的阈值更接近实际情况。

4 结论

在随机稀疏Kaczmarz算法和稀疏随机Kaczmarz算法的基础上，受贪婪算法的启发，提出稀疏贪婪随机Kaczmarz算法，给出了新算法的收敛性分析，且在有噪声干扰和无噪声干扰的情况下，通过理论证明了新算法的收缩因子小于随机稀疏Kaczmarz算法的收缩因子。数值实验表明所提出的新算法在迭代步数和计算时间上均优于传统的随机稀疏Kaczmarz算法。

作者贡献声明

王 泽：算法设计者和算法研究的执行人，构造新的算法，给出收敛性证明，完成数值实验和数据分析、论文初稿的写作。

殷俊锋：研究的构思者及负责人，指导实验设计，数据分析，论文写作与修改。