压缩感知中的信号重构方法分析

鲁周迅，徐晓梅

（南京工业大学,江苏 南京 211800)

现代信息技术的飞速发展，使得人们对信息量的要求剧增，对信号带宽采样速度和处理速度的要求也越来越高。传统的奈奎斯特采样定律要求信号的采样速度至少要达到信号带宽的两倍才能重构原信号，这就为现代信息技术较高的要求设置了障碍。另外，在实际应用中，为了降低存储、处理和传输的成本，人们常采用压缩方式以较少的比特数表示信号，大量的非重要的数据被抛弃,这种高速采样在压缩的过程浪费了大量的采样资源。

为了解决这个问题,由Candes和Donoho等人提出了压缩感知理论CS(Compressive Sensing)[1-2]。该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源的浪费，即在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。压缩感知的核心概念在于试图从理论上降低对一个信号进行测量的成本。压缩感知理论包含了许多重要的数学理论，具有广泛的应用前景。

本文就压缩感知理论进行了分析，着重介绍了其重构方法，并对其效果进行了详细分析。

1 压缩感知概述

假设一个采样信号s,s∈RN。用一个与变换矩阵不相关的 M×N(M＜＜N)测量矩阵 Φ对信号进行线性投影,得到线性测量值 y=Φs。测量值 y是一个 M×1矩阵，这样使测量对象从N维降为M维，观测过程是非自适应的,即测量矩阵Φ的选择不依赖于信号s,测量矩阵的设计要求信号从f转换为y的过程中,所测量到的K个测量值不会破坏原始信号的信息,保证信号的精确重构。由于压缩感知要求信号是可稀疏表示的，且K＜＜M，所以满足有效等距的性质(RIC)，即对于任意的稀疏信号s和常数 δs，δs∈(0,1)。 满足：

其中，|T|≤S, 对于系数序列(cj)，j∈T。

根据 RIC性质可知，当 δ2s+δ3s＜1时，信号 s可由下式重构：

Φ 为高斯随机序列，Φi,j～N(0,1/M)。 如果满足式(3)信号可被准确地重构。

2 用户的压缩频谱感知

对信号进行直接采样时，要求高速度的模数转换器(ADC)并且要存储和传输大量的数据。模拟信号转换器(ADC)可以实现这样的功能。基带信号x(t)是经AIC采样得到的信号。根据参考文献[3-4]，AIC可以看作是工作于奈奎斯特定律下的ADC。ADC输入端的堆栈向量为：

压缩信号的N×N和 M×M自相关矩阵和式 (4)、式(5)有如下的关系：

其中：H指 Hermitian矩阵；[Ry]ij=ry(i-j)=ry*(j-i);[Rx]ij=rx(i-j)=rx*(j-i)。

根据式(4)、式(5)压缩信号的 2N×1和 2M×1自相关矩阵可以写成下面的形式：

其中，第一个0值是人为加入的，并且这些向量的第一排和第一列分别是自相关矩阵。为了得到CS的重构信号，根据式(8)、式(9)，应用矩阵的运算，可以得到：

[4]知：

其中，Zs是 2N×1 向量，G=(Γfw)-1。 2N×2N 矩阵 w 和 f分别指基带滤波和傅里叶变换，联合式(10)、式(11)可以得到CS信号边缘频谱重构的优化条件:

3 信息重构方法

目前为止出现的重构算法可以分为如下几类：

(1)贪婪追踪算法:这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号。这些算法包括MP算法、OMP算法、分段OMP算法和正则化OMP算法。

(2)凸松弛法:这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，如BP算法、内点法、梯度投影方法和迭代阈值法。

(3)组合算法：这类方法要求信号的采样支持通过分组测试快速重建,如傅里叶采样、链式追踪和HHS(Heavg Hitters on Steroids)追踪等。

每种算法都有其固有的缺点，凸松弛法重构信号所需的观测次数最少，但往往计算负担很重。贪婪追踪算法在运行时间和采样效率上都位于另两类算法之间。由此可知，重构算法和所需的观测次数密切相关。当前，压缩感知理论的信号重构问题的研究主要集中在如何构造稳定的、计算复杂度较低的、对观测数量要求较少的重构算法来精确地恢复原信号。本文将用梯度投影算法(GP)和 Projected Barzilai-Borwein(PBB)来重构信号，并对这两种算法进行仿真分析。

3.1 GP算法介绍

根据前面的压缩感知理论，假设A=ΦG,即

在第j个感知用户中，引进向量uj和vj来代替zs。zs,j=uj-vj，uj≥0，vj≥0，j=1，…，J。 其中，对于所有的 i=1,…,2N,都 有 uj(i)=(zs,j(i))+=max{0,zs,j(i)}，vj(i)=(-zs,j(i))+=max{0,-zs,j(i)}(a)+=max(0,a)。于是，可以得到其中 12N=[1,1,…,1]T。 式(12)可以写成下面的形式：

式(14)可以写成带约束二次规划的形式（BCQP）:

3.2 基本GP算法

3.3 GBB重构算法

4 仿真结果分析

根据上面的理论，文章对这两种方法进行了仿真分析，并作出了比较。仿真结果如图1、图2所示。

图1表明：在压缩感知中，当压缩率减小的时候，MSE增加。如果考虑多用户的频谱感知机制，MSE也会随着用户的减少而增加。因此，可以采用降低压缩率，而增加感知用户的方法来进行压缩感知，不会降低重构的性能。同时，PBB算法比基本GP算法效果更好一点。

图2表明：当用户增加时，检测概率增加，虚警概率减小。PBB算法和基本GP算法的结论是基本一致的。

为了更好地重构信号，压缩感知是很有必要的，而且压缩感知可以降低硬件消耗，减少存储空间的浪费。在压缩感知理论的信号重构方法中，梯度投影算法和PBB算法会取得比较好的效果。在未来的研究中，将尝试改进这种算法，使压缩感知理论更加完善。

参考文献

[1]DONOHO D.Compressed sensing[J].IEEE Trans.Information Theroy,2006,52(4):1289-1306.

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

[3]KIROLOS S,RAGHEB T,LASKA J et al.Practial issues in implementing analog-to-information conventers[J].in The 6thInternational Workshop on System-on-Chip for Real-Time Applications,2006:141-146.

[4]LASKA J N,KIROLOS S,DUARTE M F,et al.Theory and implementation of an analog-to-information converter using random demodulation[J].In IEEE international symposium on Circuits and Systems(ISCAS),2007:1959-1962.

[5]傅迎华.可压缩感知重构算法与近似QR分解[J].计算机应用，2008,28（9）：2300-2302.