块稀疏信号重构的广义正交匹配追踪算法研究

Research on Generalized Orthogonal Matching Pursuit for Block Sparse Signals Reconstruction

摘要

在压缩感知理论中，将信号进行分块能够有效减少数据的处理量，提高信号的重构速度，因此块稀疏信号的稳定重构得到广泛研究。在l_{\mathrm{\infty }}有界噪声环境下，研究得到了广义正交匹配追踪（Block generalized Orthogonal Matching Pursuit,BgOMP)算法下稳定重构块稀疏信号的停止迭代准则，并对其误差进行了分析，得到了迭代重构的信号非零块的有界性结果。

Abstract

In compressed sensing theory, dividing signals into blocks can effectively reduce data processing requirements and improve signal reconstruction speed. Therefore, the stable recovery of block sparse signals has been widely studied in recent years. In this paper, we examine the stopping iteration criterion for stable recovery of block sparse signals using the Block generalized Orthogonal Matching Pursuit(BgOMP) algorithm when l_{\mathrm{\infty }} bound noise and discuss recovery errors； furthermore we get the boundedness results of nonzero blocks generated by the iteration.

Graphical abstract

关键词

块稀疏 / 块限制等距性 /

\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}

算法 /

l_{\mathrm{\infty }}

有界噪声

Key words

block sparse / block restricted isometry property /

\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}

algorithm /

l_{\mathrm{\infty }}

bound noise

0　 引 言

压缩感知(Compressed Sensing, CS)是一种新的采样理论,自从2004年提出来后，广泛应用于成像、无线通信、模拟信息转换和生物传感等领域。目前压缩感知理论的研究方向主要分为信号的稀疏性、测量矩阵和重构。有别于传统的\mathrm{N}\mathrm{y}\mathrm{q}\mathrm{i}\mathrm{u}\mathrm{s}\mathrm{t}采样理论，压缩感知理论指出，若一个信号是稀疏信号或者可以在某个变换域上表现为稀疏信号，那么可以通过一个与变换基不相关的矩阵将此信号投影到低维空间上，且此投影过程不会损失原信号中的信息，因此通过该投影可以精确地重构出原信号。压缩感知中的采样过程相对简单，但重构过程非常复杂，所以对于重构算法的研究是压缩感知中相当重要的一方面。

压缩感知理论经过十几年的快速发展，已产生了许多不同的复杂性和性能特征的有效算法，其中贪婪算法因其结构简单、易于实现而得到广泛关注，例如正交匹配追踪（Orthogonal Matching Pursuit, OMP）算法^[1]，压缩采样匹配追踪(Compressive Sampling MP, CoSaMP)算法^[2]等。近些年来,除了标准的稀疏信号的情况，块稀疏信号^[3]受到很多研究者的关注。因此人们针对块稀疏信号重构问题提出了许多改进算法。例如：块正交匹配追踪(Block Orthogonal MP, BOMP)算法^[4]和BgOMP（Block generalized Orthogonal Matching Pursuit）算法^[5]等。

\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法是\mathrm{B}\mathrm{O}\mathrm{M}\mathrm{P}算法的一种自然推广。\mathrm{B}\mathrm{O}\mathrm{M}\mathrm{P}算法每次迭代只选择一个正确的块索引，而\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法每次迭代选取N\left(N\ge \mathrm{1}\right)个块索引，其中至少包含一个正确的块索引，因此具有降低计算复杂度和提高精确重构概率的优越性。Manoj在文献[6]中提出\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法重构块稀疏信号迭代次数的上界，并在文献[7]中对该上界进行了优化。文献[8]，[9]和[10]利用不同方法讨论了BgOMP算法稳定重构块稀疏信号的充分条件，并且Chen等^[9,10]举出一个\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法重构K块稀疏信号失败的例子，进一步说明其充分条件也是必要的。

针对上述情况，基于块稀疏信号理论，本文展示了在l_{\mathrm{\infty }}有界噪声水平下块广义正交匹配追踪算法稳定重构块稀疏信号的重要成果，并通过数值模拟进行分析。

1　 预备知识

压缩感知的基本框架是从噪声测量方程组

\mathit{y}=\mathit{\Phi }\mathit{x}+\mathit{v}（1）

中重构出未知的最稀疏向量\mathit{x}\in {\mathbb{R}}^n，其中，\mathit{y}\in {\mathbb{R}}^m为测量向量，\mathit{\Phi }\in {\mathbb{R}}^{m\times n}\left(m\ll n\right)为测量矩阵，\mathit{v}表示噪声向量。若向量\mathit{x}中最多含有K个非零元素，那么这个向量\mathit{x}就被称作是K稀疏的。

当信号\mathit{x}\in {\mathbb{R}}^n中的非零元素成区域显现，可以将其分解为：

\mathit{x}=[\underset{\mathit{x}[\mathrm{1}]}{\underbrace{x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_{d_{\mathrm{1}}}}},\underset{\mathit{x}[\mathrm{2}]}{\underbrace{x_{d_{\mathrm{1}}+\mathrm{1}},x_{d_{\mathrm{1}}+\mathrm{2}},\cdots ,x_{d_{\mathrm{1}}+d_{\mathrm{2}}}}},

{\cdots \underset{\mathit{x}[L]}{\underbrace{x_{n-d_L+\mathrm{1}},\cdots ,x_n}}]}^{*}

\mathit{x}[i]表示信号\mathit{x}的第i块，d_i表示每块的长度。若：

{\displaystyle \sum _{i=\mathrm{1}}^L}I\left({‖\mathit{x}[i]‖}_{\mathrm{2}}\ge \mathrm{0}\right)\le K

则称\mathit{x}\in {\mathbb{R}}^n是K块稀疏^[3，7，8]，其中I\left(\bullet \right)是指标函数：

I\left({‖\mathit{x}[i]‖}_{\mathrm{2}}\ge \mathrm{0}\right)=\left\{\begin{array}{c}\mathrm{1},{‖\mathit{x}[i]‖}_{\mathrm{2}}>\mathrm{0}\\ \mathrm{0},{‖\mathit{x}[i]‖}_{\mathrm{2}}=\mathrm{0}\end{array}\right.

此时信号\mathit{x}的支撑集定义为非零块的索引集，标记为：

S=\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}\left(\mathit{x}\right)=\left\{i\in \left[\mathrm{1},L\right]:{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}\ne \mathrm{0}\right\}

那么相应的测量矩阵\mathit{\Phi }也可以分解成：

\mathit{\Phi }=[\underset{\mathit{\Phi }[\mathrm{1}]}{\underbrace{{\mathit{\Phi }}_{\mathrm{1}},{\mathit{\Phi }}_{\mathrm{2}},\cdots ,{\mathit{\Phi }}_{d_{\mathrm{1}}}}},\underset{\mathit{\Phi }[\mathrm{2}]}{\underbrace{{\mathit{\Phi }}_{d_{\mathrm{1}}+\mathrm{1}},{\mathit{\Phi }}_{d_{\mathrm{1}}+\mathrm{2}},\cdots ,{\mathit{\Phi }}_{d_{\mathrm{1}}+d_{\mathrm{2}}}}},

{\cdots \underset{\mathit{\Phi }[L]}{\underbrace{{\mathit{\Phi }}_{n-d_L+\mathrm{1}},\cdots ,{\mathit{\Phi }}_n}}]}^{*}

本文考虑d_i=d时的均匀分块且对测量矩阵\mathit{\Phi }进行预处理，使得{‖{\mathit{\Phi }}^{*}[i]‖}_{\mathrm{2}}=\mathrm{1}。

为了便于下文叙述，首先介绍本文所需用到的符号。K块稀疏信号\mathit{x}的支撑集记为S，\left|S\right|\le K，且其补集记为S^c。算法迭代选定的索引集合记为{\Lambda }^k且记S\backslash {\Lambda }^k=\left\{i|i\in S,i\notin {\Lambda }^k\right\},W=\left\{j|j\in S^c\right\}。设\mathit{\Phi }\left[S\right]是\mathit{\Phi }的子矩阵，只包含由S索引的列块；同理\mathit{x}\left[S\right]是\mathit{x}的子向量，只包含由S索引的块。例如：若S=\left\{\mathrm{1,2},\mathrm{3}\right\},则\mathit{\Phi }\left[S\right]=\left[\mathit{\Phi }\left[\mathrm{1}\right],\mathit{\Phi }\left[\mathrm{2}\right],\mathit{\Phi }\left[\mathrm{3}\right]\right]，\mathit{x}\left[S\right]={\left[{\mathit{x}}^{\mathit{*}}\left[\mathrm{1}\right],{\mathit{x}}^{\mathit{*}}\left[\mathrm{2}\right],{\mathit{x}}^{\mathit{*}}\left[\mathrm{3}\right]\right]}^{\mathit{*}}。对任意的满秩矩阵\mathit{\Phi }\left[{\Lambda }^k\right]，其转置矩阵为{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]，逆矩阵为{\mathit{\Phi }}^{-\mathrm{1}}\left[{\Lambda }^k\right]。记投影为\mathit{P}\left[{\Lambda }^k\right]=\mathit{\Phi }\left[{\Lambda }^k\right]({\mathit{\Phi }}^{\mathit{*}}{\left[{\Lambda }^k\right]\mathit{\Phi }\left[{\Lambda }^k\right])}^{-\mathrm{1}}\mathit{\Phi }\left[{\Lambda }^k\right]，正交投影为{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]=\mathit{I}-\mathit{P}\left[{\Lambda }^k\right]。

下面给出一些定义与引理。

为了研究算法重构块稀疏信号的性能，引入块限制等距特性^{[3，11，12]}（Restricted Isometry Property, RIP）的概念用于表征测量矩阵恢复块稀疏信号的充分性。

定义1 对任意的K块稀疏信号\mathit{x},若存在最小的正数{\delta }_{\mathrm{B}\mathrm{K}}\in \left(\mathrm{0,1}\right)使得：

\left(\mathrm{1}-{\delta }_{\mathrm{B}\mathrm{K}}\right){‖\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖\mathit{\Phi }\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}}\le \left(\mathrm{1}+{\delta }_{\mathrm{B}\mathrm{K}}\right){‖\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}}（2）

则称测量矩阵\mathit{\Phi }满足块RIP，其中，{\delta }_{\mathrm{B}\mathrm{K}}被定义为块限制等距常数（Restricted Isometry Constant, RIC）。

定义2 若\mathit{x}\in {\mathbb{R}}^n，l_{\mathrm{2}}∕l_p混合范数^[13]：

{‖\mathit{x}‖}_{\mathrm{2},p}={‖\mathit{\varpi }‖}_p（3）

其中，p=\mathrm{1,2},\mathrm{\infty }，当\mathit{\varpi }\in {\mathbb{R}}^L以及\mathrm{1}\le i\le L，有{\varpi }_l={‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}。注意到当p=\mathrm{2}时，{‖\mathit{x}‖}_{\mathrm{2,2}}={‖\mathit{x}‖}_{\mathrm{2}}，故下文不区分这两个范数。若d=\mathrm{1}，有{‖\mathit{x}‖}_{\mathrm{2},p}={‖\mathit{x}‖}_p\left(p=\right.\left.\mathrm{1,2},\mathrm{\infty }\right)。

引理 1^[13，14] 若测量矩阵\mathit{\Phi }在K_{\mathrm{1}}和K_{\mathrm{2}}阶下都满足块\mathrm{R}\mathrm{I}\mathrm{P}，当时，那么。

引理2^[15] 令S_{\mathrm{1}}和S_{\mathrm{2}}是两个任意集合，若测量矩阵\mathit{\Phi }在\left|S_{\mathrm{1}}\bigcup S_{\mathrm{2}}\right|阶下满足块\mathrm{R}\mathrm{I}\mathrm{P}，则对任意向量\mathit{x}\in {\mathbb{R}}^{\left|S_{\mathrm{1}}\setminus S_{\mathrm{2}}\right|\times d}都满足：

\left(\mathrm{1}-{\delta }_{\left|S_{\mathrm{1}}\bigcup S_{\mathrm{2}}\right|}\right){‖\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖{\mathit{P}}^{\perp }\left[S_{\mathrm{1}}\right]\mathit{\Phi }\left[\left|S_{\mathrm{1}}\backslash S_{\mathrm{2}}\right|\right]\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}}\le \left(\mathrm{1}+{\delta }_{\left|S_{\mathrm{1}}\bigcup S_{\mathrm{2}}\right|}\right){‖\mathit{x}‖}_{\mathrm{2}}^{\mathrm{2}}

BgOMP算法如下：

2　 主要结论

定理1 对于正整数N，k，其中\mathrm{0}\le k\le K。在l_{\mathrm{\infty }}有界噪声水平下，测量矩阵\mathit{\Phi }满足，那么\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法在{‖{\mathit{\Phi }}^{*}{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}\le \left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon的停止准则下，当K块稀疏信号\mathit{x}满足：

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}>\frac{\mathrm{2}\left(\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}+\sqrt[]{KN}\right)\epsilon }{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}(\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}})}（4）

时，能确保在每次迭代中至少选择一个正确的块索引，直至稳定重构出K块稀疏信号，即S\subset {\Lambda }^k，且重构误差为：

{‖\widehat{\mathit{x}}-\mathit{x}‖}_{\mathrm{2}}\le \frac{\sqrt[]{KN}}{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}\epsilon（5）

证 根据{\left({\mathit{P}}^{\perp }\right)}^{*}{\mathit{P}}^{\perp }={\mathit{P}}^{\perp }，可以发现：

{‖\mathit{P}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}^{\mathrm{2}}=〈\mathit{P}\left[{\Lambda }^k\right]\mathit{v},\mathit{P}\left[{\Lambda }^k\right]\mathit{v}〉={\mathit{v}}^{\mathit{*}}{\mathit{P}}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{P}\left[{\Lambda }^k\right]\mathit{v}={\mathit{v}}^{\mathit{*}}\mathit{P}\left[{\Lambda }^k\right]\mathit{v}=

{\mathit{v}}^{\mathit{*}}\mathit{\Phi }\left[{\Lambda }^k\right]{\left({\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{\Phi }\left[{\Lambda }^k\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{v}\le

\begin{array}{l}\frac{\mathrm{1}}{\mathrm{1}-{\delta }_{NK}}{‖{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}^{\mathrm{2}}\le \\ \frac{\mathrm{1}}{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}{‖{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}^{\mathrm{2}}\le \frac{KN{\epsilon }^{\mathrm{2}}}{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}\end{array}（6）

同理可得：

{‖\mathit{P}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}^{\mathrm{2}}\ge \frac{{\epsilon }^{\mathrm{2}}}{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}（7）

因为

\widehat{\mathit{x}}\left[{\Lambda }^k\right]={\left({\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{\Phi }\left[{\Lambda }^k\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{y}

根据\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法的迭代步骤得到：

{\mathit{r}}^k=\mathit{y}-\mathit{\Phi }\left[{\Lambda }^k\right]\widehat{\mathit{x}}\left[{\Lambda }^k\right]={\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]

\mathit{x}\left[S\backslash {\Lambda }^k\right]+{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}（8）

令{\beta }_{\mathrm{1}}^{k+\mathrm{1}}={‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}表示残差{\mathit{r}}^k与未被选择的正确块索引对应测量列之间的最大相关性;{\alpha }_N^{k+\mathrm{1}}=\underset{j\in W}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{r}}^k‖}_{\mathrm{2}}\right\}表示残差{\mathit{r}}^k与错误块索引对应测量列之间的最小相关性。假设\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法在前k\left(\mathrm{0}\le k\le K-\mathrm{1}\right)次迭代都是成功的，要保证\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法在第k+\mathrm{1}次迭代选择的块索引也是成功的，即证：

{\beta }_{\mathrm{1}}^{k+\mathrm{1}}>{\alpha }_N^{k+\mathrm{1}}

将（8）式带入{\beta }_{\mathrm{1}}^{k+\mathrm{1}}和{\alpha }_N^{k+\mathrm{1}}，可以得到：

{\beta }_{\mathrm{1}}^{k+\mathrm{1}}=

‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]\left({\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]+\right.

{\left.{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}\right)‖}_{\mathrm{2},\mathrm{\infty }}\ge

{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2},\mathrm{\infty }}-

{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}

\begin{array}{l}{\alpha }_N^{k+\mathrm{1}}=\underset{j\in W}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{r}}^k‖}_{\mathrm{2}},j\in W\right\}\le \\ \frac{\mathrm{1}}{N}\sum _{j\in W}{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}\le \end{array}

\begin{array}{l}\frac{\mathrm{1}}{N}\sum _{j\in W}{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{P}}^{\perp }\left[{\mathrm{\Lambda }}^k\right]\mathit{\Phi }\left[S\backslash {\mathrm{\Lambda }}^k\right]\mathit{x}\left[S\backslash {\mathrm{\Lambda }}^k\right]‖}_{\mathrm{2}}+\\ \frac{\mathrm{1}}{N}\sum _{j\in W}{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{P}}^{\perp }\left[{\mathrm{\Lambda }}^k\right]\mathit{v}‖}_{\mathrm{2}}\le \end{array}

\begin{array}{l}\frac{\mathrm{1}}{N}\sum _{j\in W}{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{P}}^{\perp }\left[{\mathrm{\Lambda }}^k\right]\mathit{\Phi }\left[S\backslash {\mathrm{\Lambda }}^k\right]\mathit{x}\left[S\backslash {\mathrm{\Lambda }}^k\right]‖}_{\mathrm{2}}+\\ {‖{\mathit{\Phi }}^{\mathit{*}}\left[W\right]{\mathit{P}}^{\perp }\left[{\mathrm{\Lambda }}^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\end{array}

要证{\beta }_{\mathrm{1}}^{k+\mathrm{1}}>{\alpha }_N^{k+\mathrm{1}}，即要证明：

\begin{array}{l}{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2},\mathrm{\infty }}-\\ \frac{\mathrm{1}}{N}\sum _{j\in W}{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}>\end{array}

{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}+{‖{\mathit{\Phi }}^{\mathit{*}}\left[W\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}（9）

其中，设i_{\mathrm{0}}\in S\backslash {\Lambda }^k，j_{\mathrm{0}}\in W使得：

{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}={‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}},

{‖{\mathit{\Phi }}^{\mathit{*}}\left[W\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}={‖{\mathit{\Phi }}^{\mathit{*}}\left[j_{\mathrm{0}}\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}

则（9）式的右边可变为：

{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}+{‖{\mathit{\Phi }}^{\mathit{*}}\left[W\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}=

{‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}+{‖{\mathit{\Phi }}^{\mathit{*}}\left[j_{\mathrm{0}}\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}=

{‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\bigcup j_{\mathrm{0}}\right]\left(I-\mathit{P}\left[{\Lambda }^k\right]\right)\mathit{v}‖}_{\mathrm{2,1}}\le

\sqrt[]{\mathrm{2}}\left({‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\bigcup j_{\mathrm{0}}\right]\mathit{v}‖}_{\mathrm{2}}+{‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\bigcup j_{\mathrm{0}}\right]\mathit{P}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}\right)\le

\sqrt[]{\mathrm{2}}\left({‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\bigcup j_{\mathrm{0}}\right]\mathit{v}‖}_{\mathrm{2}}+{‖{\mathit{\Phi }}^{\mathit{*}}\left[i_{\mathrm{0}}\bigcup j_{\mathrm{0}}\right]‖}_{\mathrm{2}}{‖\mathit{P}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}\right)\le

\mathrm{2}\left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon（10）

设前k次迭代已选取了l\left(k\le l\le K\right)个正确的块索引，则{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2,1}}^{\mathrm{2}}\le \left(K-l\right){‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}^{\mathrm{2}}且\left|S\bigcup \left(S\backslash {\Lambda }^k\right)\bigcup W\right|\le K+Nk-l+N\le \left(N-\mathrm{1}\right)k+K+N\le \left(N-\mathrm{1}\right)\left(K-\mathrm{1}\right)+K+N=NK+\mathrm{1}，其中\mathrm{0}\le k\le K-\mathrm{1}。根据文献[8]的引理4,（9）式的左边：

{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\mathrm{\Lambda }}^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2},\mathrm{\infty }}-\frac{\mathrm{1}}{N}\sum _{j\in W}{‖{\mathit{\Phi }}^{\mathit{*}}\left[j\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}\ge

\begin{array}{l}\frac{\left(\mathrm{1}-\sqrt[]{\frac{K-l}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}\right){‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}{\sqrt[]{K-l}}\ge \\ \frac{\left(\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}\right){‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}{\sqrt[]{K-l}}\end{array}（11）

结合(10)和(11)式，要证明(9)式成立，即要说明：

\begin{array}{l}\frac{\left(\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}\right){‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}{\sqrt[]{K-l}}>\\ \mathrm{2}\left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon \end{array}

为简化计算过程，记C=\left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon，因此当时，要保证：

{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}>\frac{\mathrm{2}C\sqrt[]{K-l}}{\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}}（12）

又因为：

{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}\ge \sqrt[]{K-l}\underset{i\in S\backslash {\mathrm{\Lambda }}^k}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}\ge

\sqrt[]{K-l}\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}

则(12)式可以转变为：

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}>\frac{\mathrm{2}C}{\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}}

即当时，稀疏信号\mathit{x}满足：

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}>\frac{\mathrm{2}\left(\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}+\sqrt[]{KN}\right)\epsilon }{\left(\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}\right)\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}

则可确保\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法在每次的迭代过程中至少选择一个正确的块索引，直到所有的正确块索引都被选择。

接着要验证算法的迭代停止准则为：{‖{\mathit{\Phi }}^{*}{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}\le \left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon。以下分为两种情况讨论。

若S\backslash {\Lambda }^k=\mathrm{\varnothing },则{\mathit{r}}^k={\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}，那么：

{‖{\mathit{\Phi }}^{*}{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}={‖{\mathit{\Phi }}^{*}{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\le \left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon（13）

若S\backslash {\Lambda }^k\ne \mathrm{\varnothing }，那么：

{‖{\mathit{\Phi }}^{*}{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}\ge {‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2},\mathrm{\infty }}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\frac{\mathrm{1}}{\sqrt[]{K-l}}{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\frac{\mathrm{1}}{\sqrt[]{K-l}}\frac{{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}{{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\frac{\mathrm{1}}{\sqrt[]{K-l}}\frac{〈\mathit{x}\left[S\backslash {\Lambda }^k\right],{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]〉}{{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\frac{\mathrm{1}}{\sqrt[]{K-l}}\frac{{‖{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{\Phi }\left[S\backslash {\Lambda }^k\right]\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}^{\mathrm{2}}}{{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\frac{\mathrm{1}}{\sqrt[]{K-l}}\frac{\left(\mathrm{1}-{\delta }_{K+Nk-l}\right){‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}^{\mathrm{2}}}{{‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\frac{\mathrm{1}}{\sqrt[]{K-l}}\left(\mathrm{1}-{\delta }_{NK+\mathrm{1}}\right){‖\mathit{x}\left[S\backslash {\Lambda }^k\right]‖}_{\mathrm{2}}-{‖{\mathit{\Phi }}^{\mathit{*}}\left[S\backslash {\Lambda }^k\right]{\mathit{P}}^{\perp }\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2},\mathrm{\infty }}\ge

\left(\mathrm{1}-{\delta }_{NK+\mathrm{1}}\right)\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}-\left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon >

\left(\mathrm{1}-{\delta }_{NK+\mathrm{1}}\right)\frac{\mathrm{2}\left(\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}+\sqrt[]{KN}\right)}{\left(\mathrm{1}-\sqrt[]{\frac{K}{N}+\mathrm{1}}{\delta }_{NK+\mathrm{1}}\right)\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}-\left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon >\left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon（14）

说明在未达到{‖{\mathit{\Phi }}^{*}{\mathit{r}}^k‖}_{\mathrm{2},\mathrm{\infty }}\le \left(\mathrm{1}+\frac{\sqrt[]{KN}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\right)\epsilon之前，\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法会继续迭代。当\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法停止迭代即K块稀疏信号被稳定地重构出，重构误差为：

{‖\widehat{\mathit{x}}-\mathit{x}‖}_{\mathrm{2}}\le \frac{\mathrm{1}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}{‖\mathit{\Phi }\left(\widehat{\mathit{x}}-\mathit{x}\right)‖}_{\mathrm{2}}\le

\frac{\mathrm{1}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}{‖\mathit{\Phi }\left[{\Lambda }^k\right]{\left({\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{\Phi }\left[{\Lambda }^k\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{y}-\mathit{\Phi }\mathit{x}‖}_{\mathrm{2}}\le

\frac{\mathrm{1}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}{‖\mathit{\Phi }\left[{\Lambda }^k\right]{\left({\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{\Phi }\left[{\Lambda }^k\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\left(\mathbf{\Phi }\mathit{x}+\mathit{v}\right)-\mathit{\Phi }\mathit{x}‖}_{\mathrm{2}}\le

\frac{\mathrm{1}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}{‖\mathit{\Phi }\left[{\Lambda }^k\right]{\left({\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{\Phi }\left[{\Lambda }^k\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[{\Lambda }^k\right]\mathit{v}+\mathbf{\Phi }\mathit{x}-\mathit{\Phi }\mathit{x}‖}_{\mathrm{2}}\le

\frac{\mathrm{1}}{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}{‖\mathit{P}\left[{\Lambda }^k\right]\mathit{v}‖}_{\mathrm{2}}\le \frac{\sqrt[]{KN}}{\mathrm{1}-{\delta }_{K+\mathrm{1}}}\epsilon（15）

定理2 测量矩阵\mathit{\Phi }满足且时，若\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法稳定重构出K块稀疏信号\mathit{x}，则：

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}-\frac{\sqrt[]{K}\epsilon }{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}}\le \underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\widehat{\mathit{x}}\left[i\right]‖}_{\mathrm{2}}\le \underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}+\frac{\epsilon }{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}（16）

证 此时K块稀疏信号被稳定重构，即：S\subset {\Lambda }^k，令{\left({\mathit{\Phi }}^{\mathit{*}}\left[S\right]\mathit{\Phi }\left[S\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[S\right]\mathit{v}=\mathit{Z}[S]，则：

\mathit{P}\left[S\right]\mathit{v}=\mathit{\Phi }\left[S\right]{\left({\mathit{\Phi }}^{\mathit{*}}\left[S\right]\mathit{\Phi }\left[S\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[\mathrm{S}\right]\mathit{v}=\mathit{\Phi }\left[S\right]\mathit{Z}[S]

且

\mathit{\Phi }\left[S\right]\widehat{\mathit{x}}\left[S\right]=\mathit{\Phi }\left[S\right]{\left({\mathit{\Phi }}^{\mathit{*}}\left[S\right]\mathit{\Phi }\left[S\right]\right)}^{-\mathrm{1}}{\mathit{\Phi }}^{\mathit{*}}\left[S\right]\mathit{y}=

\mathit{P}\left[S\right]\mathit{y}=\mathit{P}\left[S\right]\left(\mathit{\Phi }\mathit{x}+\mathit{v}\right)=

\mathit{\Phi }\left[S\right]\mathit{x}\left[S\right]+\mathit{P}\left[S\right]\mathit{v}=

\mathit{\Phi }\left[S\right]\mathit{x}\left[S\right]+\mathit{\Phi }\left[S\right]\mathit{Z}[S]

因此可得：\widehat{\mathit{x}}\left[S\right]=\mathit{x}\left[S\right]+\mathit{Z}\left[S\right]。

又因为：

\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}{‖\mathit{Z}[S]‖}_{\mathrm{2}}\le {‖\mathit{P}\left[S\right]\mathit{v}‖}_{\mathrm{2}}={‖\mathit{\Phi }\left[S\right]\mathit{Z}\left[S\right]‖}_{\mathrm{2}}\le \sqrt[]{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}{‖\mathit{Z}\left[S\right]‖}_{\mathrm{2}}（17）

根据（6）式，（7）式化简可以得到：

\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}{‖\mathit{Z}[S]‖}_{\mathrm{2}}\le {‖\mathit{P}\left[S\right]\mathit{v}‖}_{\mathrm{2}}\le \frac{\sqrt[]{K}\epsilon }{\sqrt[]{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}},

\frac{\epsilon }{\sqrt[]{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}}\le {‖\mathit{P}\left[S\right]\mathit{v}‖}_{\mathrm{2}}\le \sqrt[]{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}{‖\mathit{Z}\left[S\right]‖}_{\mathrm{2}}

即：

\frac{\epsilon }{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}\le {‖\mathit{Z}\left[S\right]‖}_{\mathrm{2}}\le \frac{\sqrt[]{K}\epsilon }{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\widehat{\mathit{x}}\left[i\right]‖}_{\mathrm{2}}=\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]+\mathit{Z}\left[i\right]‖}_{\mathrm{2}}\ge

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}-{‖\mathit{Z}\left[S\right]‖}_{\mathrm{2},\mathrm{\infty }}\ge

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}-\frac{\sqrt[]{K}\epsilon }{\mathrm{1}-{\delta }_{NK+\mathrm{1}}}

同理：

\underset{i\in S}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{x}\left[i\right]‖}_{\mathrm{2}}+\frac{\epsilon }{\mathrm{1}+{\delta }_{NK+\mathrm{1}}}\underset{i\in S}{\le \mathrm{m}\mathrm{i}\mathrm{n}}{‖\widehat{\mathit{x}}\left[i\right]‖}_{\mathrm{2}}

定理2证明完毕。

3　 数值模拟

本节给出了仿真数值模拟。实验模拟了在无噪声和l_{\mathrm{\infty }}有界噪声这两种环境下\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法重构块稀疏信号的精度。

图1的仿真实验在给定m=\mathrm{100}，n=\mathrm{256}，d=\mathrm{4}且l_{\mathrm{\infty }}有界噪声环境下进行。当K>\mathrm{4}时，\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法明显比\mathrm{B}\mathrm{O}\mathrm{M}\mathrm{P}算法重构块稀疏信号的性能好。当K>\mathrm{8}时，在相同块稀疏度下，N越大\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法的重构性能越弱。

由表1可观察到： 1） 信号的随机性会使得每次具体数值结果发生变化，经过多次实验发现，信号的随机性不会改变实验结果； 2） 每次迭代选择块数（N），块稀疏度（K），有无噪声都会对重构误差产生或多或少的影响，在没有噪声干扰情形下的误差远远小于l_{\mathrm{\infty }}有界噪声干扰情形下的误差是合理现象； 3） 当K相同时，N越大，重构误差就越大，这进一步说明通过\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法重构K块稀疏信号时选择合适N的重要性。

4　 结 语

本文在l_{\mathrm{2}}∕l_p混合范数的定义下，提出\mathrm{B}\mathrm{g}\mathrm{O}\mathrm{M}\mathrm{P}算法受有界噪声影响，在特定停止迭代准则下能稳定重构块稀疏信号并且对重构误差进行分析；给出算法迭代生成信号非零块的有界性约束。但在许多实际应用中，除了标准块稀疏还有某些信号也会以衰减块稀疏^[16]形式出现。一些学者提出了稳定重构此类块稀疏信号，测量矩阵应当满足块\mathrm{R}\mathrm{I}\mathrm{P}。同理可以将本文中的结论推广到在该块\mathrm{R}\mathrm{I}\mathrm{P}约束下衰减块稀疏信号的重构问题中。

参考文献

[1] LIU C， FANG Y， LIU J Z. Some new results about sufficient conditions for exact support recovery of sparse signals via orthogonal matching pursuit［J］. IEEE Transactions on Signal Processing， 2017， 65（17）： 4511-4524. DOI： 10.1109/TSP.2017.2711543 .

[2] NEEDELL D， TROPP J A. CoSaMP： Iterative signal recovery from incomplete and inaccurate samples［J］. Applied and Computational Harmonic Analysis， 2009， 26（3）： 301-321. DOI： 10.1016/j.acha.2008.07.002 .

[3] 卜京， 王金平. 混合最小化问题下重构块稀疏信号的充分条件［J］. 武汉大学学报（理学版）， 2021， 67（2）： 185-189. DOI： 10.14188/j.1671-8836.2020.0248 .

[4] BU J， WANG J P. A sufficient condition on recovery of block sparse signals via mixed minimization［J］. Journal of Wuhan University （Natural Science Edition）， 2021， 67（2）： 185-189. DOI： 10.14188/j.1671-8836.2020.0248（Ch ）.

[5] LI H F， WEN J M. A new analysis for support recovery with block orthogonal matching pursuit［J］. IEEE Signal Processing Letters， 2019， 26（2）： 247-251. DOI： 10.1109/LSP.2018.2885919 .

[6] XIA C Y， ZHOU Z L， GUO C B， et al. A new analysis for support performance with block generalized orthogonal matching pursuit［J］. Mathematical Problems in Engineering， 2021， 2021（12）： 1-7. DOI： 10.1155/2021/9438793 .

[7] MANOJ A， KANNU A P. Channel estimation strategies for multi-user mm wave systems［J］. IEEE Transactions on Communications， 2018， 66（11）： 5678-5690. DOI： 10.1109/TCOMM.2018.2854188 .

[8] MANOJ A， KANNU A P. Sinusoid signal estimation using generalized block orthogonal matching pursuit algorithm［C］//2018 International Conference on Signal Processing and Communications （SPCOM）. New York： IEEE Press， 2019： 60-64. DOI： 10.1109/SPCOM.2018.8724435 .

[9] QI R， YANG D W， ZHANG Y J， et al. On recovery of block sparse signals via block generalized orthogonal matching pursuit［J］. Signal Processing， 2018， 153： 34-46. DOI： 10.1016/j.sigpro.2018.06.023 .

[10] CHEN W G， GE H M. A sharp recovery condition for block sparse signals by block orthogonal multi-matching pursuit［J］. Science China Mathematics， 2017， 60（7）： 1325-1340. DOI： 10.1007/s11425-016-0448-7 .

[11] CHEN W G， GE H M. Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP［J］.Inverse Problems and Imaging， 2018， 12：153-174.DOI：10.3934/IPI.2018006 .

[12] GAO Y， PENG J G， YUE S G. Stability and robustness of l₂ /l_q -minimization for block sparse recovery［J］. Signal　Processing，2017，137：287-297. DOI：10.1016/j. sigpro.2017.02.012 .

[13] LIN J H， LI S. Block sparse recovery via mixed l₂/l₁ minimization［J］. Acta Mathematica Sinica， English Series， 2013， 29（7）： 1401-1412. DOI： 10.1007/s10114-013-1564-y .

[14] WEN J M， ZHOU Z C， LIU Z L， et al. Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit［J］. Applied and Computational Harmonic Analysis， 2019， 47（3）： 948-974. DOI： 10.1016/j.acha.2018.02.002 .

[15] HU R， FU Y， XIANG Y，et al.Performance guarantees of signal recovery via block-OMP with thresholding［J］.IET Signal Processing， 2017， 11（8）：952-960.DOI：10.1049/iet-spr.2017.0076 .

[16] SHEN Y， LI B， PAN W L， et al. Analysis of generalised orthogonal matching pursuit using restricted isometry constant［J］. Electronics Letters， 2014， 50（14）： 1020-1022. DOI： 10.1049/el.2014.1012 .

[17] WEN J， ZHANG R， YU W.Signal-dependent performance analysis of orthogonal matching pursuit for exact sparse recovery［J］. IEEE Transactions on Signal Processing， 2020. DOI：10.1109/TSP.2020.3016571 .

基金资助

国家自然科学基金(62071262)