A Perturbation Analysis of Block Sparse Signal Reconstruction with Block Orthogonal Matching Pursuit

压缩感知理论是建立在矩阵分析、统计概率、优化与运筹学、泛函分析等理论基础上的信息采样与重构的理论^[1-2].压缩感知是利用信号的稀疏表示，对信号进行有效压缩采样，通过压缩采样与非线性重构算法完美地重构信号.这一理论为信号恢复带来了新的处理方法，被广泛应用于医学成像、雷达探测、无线通信等诸多领域^[3-5].在信号x∈$\mathbb{R}$ⁿ稀疏或近似稀疏的条件下，压缩感知理论转化为如下欠定线性模型：

其中：y∈$\mathbb{R}$^m为观测信号，A∈$\mathbb{R}$^m×n(m < < n)为测量矩阵，x∈$\mathbb{R}$ⁿ为待重构的信号.实际观测中，加性噪音v时常影响信号y，上述压缩感知模型常转化为下述模型：

此外，实际应用中测量矩阵常常受外界测量或其他因素的影响，导致测量矩阵A受扰动矩阵E的影响，即实际测量矩阵$\mathit{\boldsymbol{\widehat A}} = \mathit{\boldsymbol{A}} + \mathit{\boldsymbol{E}}$，其中A称为理想测量矩阵.本文将扰动矩阵E与加性噪音v同时存在的压缩感知问题称之为完全扰动问题^[6-7]，该问题对应的模型为：

从欠定线性模型中求解一个最稀疏的解是压缩感知的核心问题，该问题实际上是一个l₀问题.由于l₀问题在多项式时间内不能有效求解^[8]，文献[9]研究了如下l₁完全扰动问题：

其中ε′_A，K，y为全噪音参数.文献[9]中研究了信号鲁棒重构的限制等容条件(restricted isometrics property，RIP).信号重构条件为压缩感知的发展提供了重要研究意义.

在实际应用中，自然信号的结构丰富多彩.非零元素以块的结构方式出现的信号称为块稀疏信号^[10]，例如DNA-微阵列^[11]、彩色图像处理^[12]和源定位^[13]等.块稀疏压缩感知实际是单独处理重构信号的每一小块.块稀疏压缩感知使块信号重构与采样的速度更快，且占用存储空间更少.若块稀疏信号用数学模型来表示，则在分块$\mathscr{I}$ ={d₁，…，d_N}给定情况下，可以将任意向量x∈$\mathbb{R}$ⁿ描述为如下形式

相应地，测量矩阵A∈$\mathbb{R}$^n×N也可以描述为如下形式

其中向量x的第i个子块为x[i]，第i块的大小为d_i.如果在给定分块$\mathscr{I}$下，信号x至多有K个非零块，即$||\mathit{\boldsymbol{x}}|{|_{2, 0}} = \sum\limits_{i = 1}^N I \left({||\mathit{\boldsymbol{x}}[i]|{|_2}} \right) \le K$，则称x为块K稀疏信号，其中I(·)表示指示函数^[14].实际上，当d_i=1(i=1，…，N)时，块稀疏信号x为传统稀疏信号.此外，信号x的$\frac{{{\mathit{\boldsymbol{l}}_2}}}{{{\mathit{\boldsymbol{l}}_1}}}$范数$||\mathit{\boldsymbol{x}}|{|_{2, 1}} = \sum\limits_{i = 1}^N I ||\mathit{\boldsymbol{x}}[i]|{|_2}$；信号x的$\frac{{{\mathit{\boldsymbol{l}}_2}}}{{{\mathit{\boldsymbol{l}}_\infty }}}$范数‖x‖_2，∞=max{‖x^[1]‖₂，…，‖x[N]‖₂}；规定信号x的范数‖x‖_2，2=‖x‖₂.

实际上，在稀疏信号的重构中，测量矩阵要求满足限制性等容条件或相干性等重构条件.特别地，在不引起混淆的情况下，本文记矩阵A的块限制等容常数δ_BK=δ_K.为了重构块稀疏信号，文献[15]引入了$\mathit{\boldsymbol{\widehat A}}$的块限制性等容条件(BRIP).设测量矩阵A的块限制性等容常数为δ_K(K=1，2，…)，ε_A^(K)为相对误差上限，且$\frac{{||\mathit{\boldsymbol{E}}||_2^{(K)}}}{{||\mathit{\boldsymbol{A}}||_2^{(K)}}} \le \varepsilon _A^{(K)}$，若${\hat \delta _{K, \max }} = \left({1 + {\delta _K}} \right){\left({1 + \varepsilon _\mathit{\boldsymbol{A}}^{(K)}} \right)^2} - 1$，对于任意块K稀疏信号x∈$\mathbb{R}$ⁿ，矩阵$\mathit{\boldsymbol{\widehat A}}$=A+E的块限制性等容常数(BRIC)为满足

的最小常数${\hat \delta _K} \le {\hat \delta _K}, \max $，则称矩阵$\mathit{\boldsymbol{\widehat A}}$满足块限制性等容条件(BRIP).类似于文献[9]，有如下不等式成立：

通过研究l₁问题，学者获得了大量的充分条件：文献[16]得到了信号重构的RIPδ_2k < 0.453 1；文献[17]将RIP重构条件放松为δ_2k < 0.465 2；文献[18]将RIP改进为${\delta _{2k}} < \frac{{\sqrt 2 }}{2}$.

压缩感知的重构理论与重构算法具有重要的应用价值^[19-22].

本文借鉴文献[22]延展了一类完全扰动的块压缩感知问题.令噪音上界为l₂范数与$\frac{{{\mathit{\boldsymbol{l}}_2}}}{{{\mathit{\boldsymbol{l}}_\infty }}}$范数，其问题具体形式可分别表示为如下形式：

其中ε″_A，K，y=‖A‖₂(1+ε_A)ε′_A，K，y.近年来压缩感知基本是以RIP为理论基础，但是验证RIP理论是一个在多项式时间内不能有效解决的问题，因此，利用RIP理论获得的结论，在实际应用中很难实行.本文针对问题(5)，建立了处理块稀疏信号的扰动BOMP算法，根据扰动BOMP算法建立了各项仿真实验，验证了扰动BOMP算法的鲁棒性和稳定性.