一种压缩感知重构算法

甘 伟 许录平 苏 哲

(西安电子科技大学电子工程学院 西安 710071)

1 引言

近年来出现了一种新颖的理论——压缩感知[1,2](Compressed Sensing，CS)，它突破了传统的奈奎斯特采样定理，实现了采样方式的转变即从信号采样转变成信息采样。CS理论有3个核心问题[3]：信号稀疏变换、观测矩阵设计和恢复重构算法。其中恢复重构算法直接关系到重构精度的大小，运算时间的长短，决定着CS理论是否切实可行。一些学者致力于压缩感知的恢复重构问题提出了贝叶斯[4](BCS)，匹配追踪[5](MP)，正交匹配追踪[6](OMP)和分段正交匹配追踪[7](StOMP)算法。为了提高运算速度，另一些学者另辟蹊径提出了梯度追踪算法[8](GP)，但其精度较低。在GP的基础上，Blumensath等人为了提高重构精度引入了共轭方向和弱阈值原子选择策略，提出分段弱阈值共轭梯度追踪算法[9,10](StWCGP)，但重构精度仍不够理想。

针对StWCGP重构精度比较低的缺点，本文在其方向和输出上进行改进，明确地给出了停止迭代准则。改进后的算法称为分段弱阈值修正共轭梯度追踪算法(Stagewise Weak selection Modifying approximation Conjugate Gradient Pursuit,StWMCGP)。仿真结果表明StWMCGP能够有效地提高重构精度。

2 CS模型

CS理论指出，只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得的高维信号投影到一个低维空间上，然后通过求解一个优化问题从这些少量的投影中以高概率重构出原信号。在CS模型中并不是直接测量信号f本身，而是将信号f投影到观测矩阵上得到观测向量y。用矩阵表示：

式中y是M×1的观测向量，Φ是M×N(M＜＜N)的观测矩阵。其中信号f为长度为N的离散实值信号且在基ψ=[ψ1, ψ2,…,ψN]上是稀疏的即

式中x是N×1的系数向量且仅有k＜＜N个非零系数，ψ是N×N的稀疏矩阵。将式(2)代入式(1)得

式中A=ΦψT

为CS信息算子，其列向量称为原子。因观测维数M远远小于信号维数N,所以无法直接从y的M个观测值中解出信号f。由于式(3)中x是稀疏的，这就为求解信号f提供了可能。根据信号稀疏分解理论中的稀疏分解算法，可以通过求解式(3)的逆问题解得x,然后将x代入式(2)，求得信号f。CS理论重构问题的实质就是在已知观测向量y和观测矩阵Φ的条件下，如何快速、准确地重构出信号f。

3 StWMCGP算法

3.1 传统的StWCGP算法

由于OMP应用于大尺度问题时，它所需的存储空间很大且其运算速度不够理想，为了提高OMP的运算速度、减少存储空间，Blumensath等人提出了方向追踪算法[8]。其流程如下：

步骤1 初始化：r0=y，x0=0，Γ0={}。

步骤2 for n=1; n=n+1直到停止条件满足为止。

(1)gn=ATrn−1；

(2)原子下标选取原则：in=argimax|gni|；

(3) 下标集更新：Γn=Γn−1∪in；

(4)计算方向向量：dΓn；

(5) cn=AΓndΓn；

其中Γn表示第n次迭代时算法已选取的原子其下标所组成的集合；AΓn表示矩阵A的子矩阵，且该子矩阵仅由那些位于下标集Γn中的下标所对应的原子组成；同理：表示x的子向量，且该子向量仅由那些位于下标集Γn中下标所对应的元素组成；rn表示第n次迭代时的残余量；的元素其下标位于集合Γn−1内的与向量的元素完全相同，其余的为0。

StWCGP是在方向追踪算法的框架下将第n次迭代时的方向向量取为并将原子选择策略变为：||}。其中：α表示阈值参数(α≤1)，Γ=ng表示梯度，与是G共轭的，即与的内积为0，GΓn=的关系类似于

由于StWCGP的方向向量只取了一个与当前方向共轭的方向，并且其输出并不是第n次迭代时方程：=xy的最小二乘解，因此StWCGP的重构精度并不理想。

3.2 针对StWCGP算法的改进

StWMCGP流程如下：

步骤1 初始化：r0=y，x0=0，Γ0={}。

步骤2 for n=1；=+1 nn直到Γn中的原子下标个数大于2k 时停止迭代。

(1)gn=ATrn−1；

(2)原子下标选取原则：set = {i :| gi|≥ para×max |gj|} ；

(3)下标集更新：ΓΓ−=1[set]nn；

(4) If(n=1)(n=1；n=2时都要经过特殊处理)

(b)Γ=nncA

步骤3 由于Step2得到的集合Γn中可能有相同的元素，所以首先剔除集合Γn中相同的元素，得到新的集合Γn，然后采用最小二乘法反求x，此时x用x表示即

因为当Γn中的元素个数大于等于2k 时，Γn以很高概率包含x全部非零元素的下标[11]。故文中将停止迭代准则定义为：当Γn中的元素个数大于等于2k 时停止迭代，其中k 代表稀疏度。由于实际中对一个稀疏信号重构时，稀疏度是未知的，因此使用本算法首先需要对稀疏度进行估计。本文中所有试验都将稀疏度k估计成N/3(经验值)。

文中取两个与当前方向共轭的方向，是因为相比取1个共轭方向来讲，其精度要高，仅增加了2次矩阵和向量的乘积，并且其共轭方向所对应的系数b1，b2没有涉及到矩阵运算，只需在算法流程中进行一次特殊处理。若取3个或3个以上的共轭方向，其共轭方向所对应的系数就会涉及到矩阵的运算，会增加计算复杂度。输出采用x代替原来的，是因为不是最小二乘解。

4 试验结果及分析

4.1 StWMCGP与StWCGP对稀疏信号重构的比较

采用StWCGP和StWMCGP对长度为N=300，k=30的稀疏信号进行重构，观测值数目M取150，信息算子A的各原子是从M维空间的单位球上均匀采样而得。

由图1(a)可以看出原稀疏信号用StWCGP在上述条件下进行重构，其中有3个位置不能重构并且有些位置的圆心和十字心不重合，即这些位置没有被精确重构。由图1(b)可以看出StWMCGP在同样的条件下能对原稀疏信号实现精确重构。证实了StWMCGP比StWCGP的重构精度高。

图1 StWCGP与StWMCGP对稀疏信号的重构比较

4.2 不同算法精确重构所需观测值数目比较

从M维空间的单位球上均匀采样得到信息算子A的各原子，以1维k 稀疏，长度为N=400的信号f为例，来测试同一稀疏度下不同算法要实现精确重构对观测值数目M(M＜N)的要求。重构信号用来表示，当时，重构信号与信号f重合没有视觉差异，认定算法实现了精确重构，其中0.004从大量的试验中获得。

对同一稀疏度k，依次采用MP，StOMP-FAR[7]，StOMP-FDR[7]，BCS，StWMCGP对信号f进行重构，记录下刚好精确重构时的M，其中MP的最大迭代次数maxIter设为10000次；StOMP-FDR算法中最大迭代次数S=30，参数q=0.9；BCS中参数sigma=y的方差/100；StWMCGP中参数para=0.98。StOMP-FAR中的最大迭代次数S=10、参数q=M/(NS)(1−k/N)，式中M表示A的行数，N表示A的列数，k是稀疏度，S是最大迭代次数。

从图2可知：对于长度为N=400的信号当稀疏度小于120时，StWMCGP实现精确重构所需的观测值数目最少且比MP，StOMP-FDR所需的观测值个数少20%，比BCS，StOMP-FAR少3%。证实了相同的观测值个数条件下，StWMCGP的重构精度最高。综上可知：实际应用中采用StWMCGP对信号进行重构是理想的选择。

图2 精确重构时稀疏度k与观测值数目M之间的关系曲线

4.3 StWMCGP算法对2维图像的处理

本实验以图像Mondrian为例其大小为512×512。为了与以往经典算法进行对比，仍然采用小波基“symmlet8”，将Mondrian在该基下进行展开。采用多尺度CS[4]来对该图像进行重构，其中粗尺度j0设为4，细尺度j设为6，信息算子A的各原子是从M维空间的单位球上均匀采样而得。图3(a)是原图像；图3(b)是采用小波变换得到的图像，所用样本数K=4096；图3(c)是采用StOMP-FDR进行多尺度重构后的图像，所用样本数为K=2713，参数q=0.9，最大迭代次数S=30；图3(d)是采用StOMP-FAR进行多尺度重构后的图像，所用样本数K=2713，参数q=0.4M/NS ，最大迭代次数S=30；图3(e)是采用BCS进行多尺度重构后的图像，所用样本数K=2713，参数sigma= y的方差/100；图3(f)是采用StWMCGP进行多尺度重构后的图像，所用样本数K=2713，参数para=0.95。各个算法的运算时间和重构精度见表1，其中重构精度以相对误差作为参考：其中f代表原图像信号，f代表重构信号。

图3 不同算法对Mondrian的重构比较

由表1可知：参数para=0.9时StWMCGP的运算时间最短，此时其重构精度与StOMP-FAR相当，参数para=0.95时StWMCGP的重构精度最高，此时的运算时间与BCS相当。StWMCGP对于不同参数para运算时间和重构精度不同，主要在于参数para越大，StWMCGP每次迭代所选原子就越少，那么错选原子的概率就会降低，迭代次数就会增多，这样便增加了重构精度但也增加了运算时间；相反参数para越小，每次迭代所选原子就越多，那么选错原子的概率就会增加，迭代的次数就会减少，这样便减少了运算时间但也降低了重构精度。所以在处理具体问题时，可通过选择参数para来决定是增加重构精度还是提高运算速度。由表1和图3可知：小波变换过于平滑且存在伪边缘，重构精度最差。用StOMP-FDR重构效果也比较差；而用StOMPFAR，BCS，StWMCGP重构从视觉上来讲没有太大差异，但StWMCGP的重构精度最高。

5 结论

针对StWCGP重构精度比较低的特点本文提出了StWMCGP，仿真结果表明该算法的重构精度比StWCGP，MP，StOMP-FDR高，也比StOMPFAR，BCS略高；并在重构精度可接受的情况下，通过调节参数还能提高运算速度。

表1 不同算法运算时间和重构精度(相对误差)

[1] Candès E, Romberg J, and Tao Terence. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[2] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[3] 石光明，刘丹华, 等. 压缩感知理论及研究进展[J]. 电子学报，2009, 37(5): 1070-1081.Shi Guang-ming and Liu Dan-hua, et al.. Advances in theory and application of compressed sensing[J]. Acta Electronica Sinica, 2009, 37(5): 1070-1081.

[4] Ji Shi-hao, Xue Ya, and Carin L. Bayesian compressive sensing[J]. IEEE Transactions Signal Processing, 2008, 56(6):2346-2356.

[5] Mallat S and Zhang Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3397-3415.

[6] Tropp J and Gilbert A. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12):4655-4666.

[7] Donoho D L, Tsaig Y, Drori I, and Starck J L. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. (Preprint, 2007) http:// www.dsp.ece.rice.edu/cs.

[8] Blumensath T and Davies M E. Gradient pursuits[J]. IEEE Transactions on Signal Processing, 2008, 56(6): 2370-2382.

[9] Blumensath T and Davies M E. Stagewise weak gradient pursuits. Part I Fundamentals and numerical studies.(Preprint, 2008) http://www.dsp.ece.rice.edu/cs.

[10] Blumensath T and Davies M E. Stagewise weak gradient pursuits. Part II Theoretical properties. (Preprint, 2008)http://www.dsp.ece.rice.edu/cs.

[11] Needell D and Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[OL]. 2007, http:// www. math. ucdavis. edu/～vershynin/papers/ROMP. pdf .