压缩感知(compressive sensing)由DONOHO[1]等提出，是一种基于稀疏信号采样和处理的新理论.该理论创造性地将数据压缩和采样同时进行，突破了Nyquist采样定理的限制，可以高概率地从少量压缩采样所得的信号中重构出全部信号[2-3].事实上，对于一个自然信号，大量系数都是冗余的，只有少量系数携带了信号的信息.如果将压缩感知应用于信号采样，以压缩的方式进行采样，在避免冗余的同时不丢失信息，这种采样方式无疑是高效的.
如何从测量信号中有效重构全部原始信号是自压缩感知理论建立以来一直希望解决的问题.以压缩形式降低采样成本的代价增加了信号重构的成本，因此，重构算法的优劣直接影响压缩感知理论的实用性.现有的重构算法主要分为以下4类：(1)贪婪类算法.通过选择与信号重构残差最匹配的原子向量来构建原信号的稀疏逼近，主要包括OMP算法[4]、CoSaMP算法[5]、迭代阈值法[6]等，其特点是复杂度低但精度和稳定性不高；(2)凸优化算法.将非凸问题转化为凸问题[7]，从而可利用凸优化方法求解，常用的有BP算法、SpaRSA算法[8]等，其特点是重构精度高但复杂度也较高；(3)统计类算法.主要是基于贝叶斯框架提出的重构算法，包括：贝叶斯压缩感知算法[9-11]、EM算法[12]、基于模型的压缩感知方法[13]，这类算法着重于信号在时间上的相关性，通过分析其统计特性获得更高的重构精度；(4)组合类算法.通过对信号分组测试，快速恢复原信号的支撑集，有傅立叶追踪、链式追踪等算法.
GPSR算法[14]属于凸优化算法，通过投影梯度方法解决界约束优化问题，虽然能够有效降低算法的复杂度，但也损失了算法性能.针对此问题，本文通过给重构模型添加惩罚系数，以在计算复杂度和精度之间寻找最佳平衡点，并引入自适应思想，在迭代过程中自适应调整惩罚系数，从而使算法更加灵活.通过实验仿真，验证了该方法在不增加计算复杂度的前提下可大幅度提高算法性能.
1 压缩感知背景和GPSR重构算法 1.1 压缩感知背景压缩感知主要包括信号的稀疏表示、观测值的采集和原始信号的重构三部分[15].
信号稀疏是压缩感知能够实现的先决条件，所谓信号稀疏指对于一个N维离散实信号f，若只有S(S＜N)个非零分量，就定义该信号是S-稀疏的.在自然条件下所采集的信号通常没有稀疏性，若信号f在某个稀疏变换基Ψ下可表示成一个S -稀疏的向量，则认为该信号是S -可稀疏化的，表示为
| $ f = \mathit{\boldsymbol{ \boldsymbol{\varPsi} x}}, $ |
其中，Ψ=[Ψ1, Ψ2, …, ΨN]∈RN×N为稀疏变换基，x∈RN×1是f在基Ψ下展开的稀疏向量，是S -稀疏的.
观测值的采集又称信号随机投影过程，是压缩感知理论降低信号采集率的关键步骤.用公式表示：
| $ y = \mathit{\boldsymbol{ \boldsymbol{\varPhi} }}f = \mathit{\boldsymbol{ \boldsymbol{\varPhi} \boldsymbol{\varPsi} x}} = \mathit{\boldsymbol{Ax, }} $ |
其中，Φ∈RM×N是随机投影矩阵，需满足与稀疏变换基Ψ不相关性的特性，高斯随机投影矩阵满足任何矩阵的不相关性[16]，常被用作随机投影矩阵；y∈RM×1为观测值，这里M < N，故若对y进行采样，其采样次数小于直接对x采样；A∈RM×N常被称为压缩感知信息矩阵，需满足限制等容性的要求.限制等容性是指对于矩阵A，若其满足限制等容性[17]，则存在一个限制等距常数δ(0 < δ < 1)，使得：
| $ 1 - \delta \leqslant \frac{{\left\| {\mathit{\boldsymbol{Ax}}} \right\|_2^2}}{{\left\| \mathit{\boldsymbol{x}} \right\|_2^2}} \leqslant 1 + \delta, $ |
其中x为任意阶稀疏向量.
信号的重构过程是从观测值y中恢复得到原始信号x的过程，也是本文主要要解决的问题.由于M < N是一个线性欠定方程组求解问题，无确定解，x只有S个非零元素，从y中恢复x比解f容易得多.信号重构问题的数学模型为
| $ \mathop {{\rm{min}}}\limits_x {\left\| \mathit{\boldsymbol{x}} \right\|_o}\;\;\;\;\;{\rm{s}}{\rm{.t}}.\;\;\;\mathit{\boldsymbol{y}} = \mathit{\boldsymbol{Ax}}. $ |
在满足Φ与Ψ不相关性和A限制等容性条件下，有研究表明此模型等价于
| $ \mathop {{\rm{min}}}\limits_x {\left\| \mathit{\boldsymbol{x}} \right\|_1}\;\;\;\;\;{\rm{s}}{\rm{.t}}.\;\;\;\mathit{\boldsymbol{y}} = \mathit{\boldsymbol{Ax}}. $ |
这样就把优化问题转化为凸优化问题，以便利用现有方法求解.
1.2 GPSR重构算法由于在自然条件下，采集的信号通常是有噪声的，信号的采集过程应该改写为
| $ \mathit{\boldsymbol{y}} = \mathit{\boldsymbol{Ax}} + n, $ |
其中，n∈NM×1代表方差为σ2的高斯白噪声.可以通过求解以下凸优化问题得到x的估计值[18]：
| $ \begin{array}{l} \mathop {{\rm{min}}}\limits_x \tau {\left\| \mathit{\boldsymbol{x}} \right\|_1} + \frac{1}{2}\left\| {\mathit{\boldsymbol{Ax}} - \mathit{\boldsymbol{y}}} \right\|_2^2, {\rm{ }} \end{array} $ |
其中，l1范数可以使x的微小分量收缩至0，从而保证解的稀疏度；l2范数控制着噪声水平；τ>0为可由用户选择的正则化参数，控制模型两部分之间的平衡[19].
对于所有i=1, 2, …, N，记ui=(xi)+，vi=(-xi)+，其中(xi)+=max{0, x}，将向量x的正数分量和负数分量按下式分开：
| $ \mathit{\boldsymbol{x}} = \mathit{\boldsymbol{u}} - \mathit{\boldsymbol{v}}, {\rm{ }}\;\;\;\mathit{\boldsymbol{u}} \geqslant 0, {\rm{ }}\;\;\mathit{\boldsymbol{v}} \geqslant 0.{\rm{ }} $ |
于是，‖x‖1=INTu+INTv，其中，IN=[1, 1, …, 1]T∈RN×1，最终可表示为界约束二次规划问题：
| $ \begin{array}{l} \mathop {{\rm{min}}}\limits_{u, v} \tau \mathit{\boldsymbol{I}}_N^{\rm{T}}\mathit{\boldsymbol{u}} + \tau \mathit{\boldsymbol{I}}_N^{\rm{T}}\mathit{\boldsymbol{v}} + \frac{1}{2}\mathit{\boldsymbol{y}} - \left\| {\mathit{\boldsymbol{A}}\left( {\mathit{\boldsymbol{u}} - \mathit{\boldsymbol{v}}} \right)} \right\|_1^1\\ \;\;\;\;\;\;\;\;\;{\rm{s}}{\rm{.t}}{\rm{. }}\;\;\;\mathit{\boldsymbol{u}} \geqslant 0, \mathit{\boldsymbol{v}} \geqslant 0 \end{array} $ |
将其写成标准界约束二次规划问题：
| $ \mathop {{\rm{min}}}\limits_z {\rm{ }}{\mathit{\boldsymbol{c}}^\rm{T}}\mathit{\boldsymbol{z}} + \frac{1}{2}{\mathit{\boldsymbol{z}}^{\rm{T}}}\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{z}}^{\rm{T}}} \equiv F\left( z \right){\rm{ }}\;\;\;\;{\rm{s}}{\rm{.t}}{\rm{. }}\;\;\mathit{\boldsymbol{z}} \geqslant 0 $ |
其中，
| $ \begin{array}{l} g_i^{(k)} = {\rm{ }}\\ \left\{ \begin{array}{l} {(\nabla F({\mathit{\boldsymbol{z}}^{(k)}}))_i},\,\,\,{\rm{ if }}\,\,\,z_{_i}^{^{(k)}} > 0\,\,\,{\rm{ or}}\;\;{(\nabla F({\mathit{\boldsymbol{z}}^{(k)}}))_i} < 0, \\ 0, {\rm{ }}\;\;{\rm{else}}{\rm{.}} \end{array} \right.{\rm{ }} \end{array} $ |
GP算法的重要步骤的伪代码如表 1所示.
|
表 1 GPSR-Basic算法 Table 1 The GPSR-Basic algorithm |
为提高压缩感知凸优化重构模型的重构效果，用一个加权的l1范数来替换原有的l1范数[20]：
| $ \mathop {{\rm{min}}}\limits_x {\rm{ }}\sum\limits_{i = 1}^N {{w_i}\left| {{x_i}} \right| + \frac{1}{2}\left\| {\mathit{\boldsymbol{Ax}} - \mathit{\boldsymbol{y}}} \right\|_2^2, } {\rm{ }} $ |
其中，wi>0为稀疏向量x的第i个分量xi.
可以有选择地调整解的不同分量的权值wi自适应改变权值，即给xi添加不同的惩罚项，以达到自适应惩罚的效果，这样做的好处不仅可以减小噪声对重构过程的影响，而且可以得到具有与原始信号相同稀疏结构的重构信号.如果在位置i，原信号的分量为0，而在迭代过程中，当
| $ {w_i} = \left\{ \begin{array}{l} \frac{1}{{|{x_i}| + \varepsilon }}, {\rm{ }}i \in \mathit{\Gamma },\\ \frac{1}{{\mathop {{\rm{max}}}\limits_{i \in \mathit{\Gamma }} }}|{x_i}|, {\rm{ }}i \notin \mathit{\Gamma }, \end{array} \right. $ |
其中，Γ为x的支撑集.所谓支撑集是指给定向量中所有非零向量的指标的集合.
在实际情况中，由于无原信号的先验信息，只能根据上次迭代的信息来改变权值.本文在GP算法中根据前次迭代的解z(k)自适应迭代产生权重w(k).对于GP算法的每一次迭代，迭代开始于由上次迭代得到的问题的解x(k-1)以及w(k-1)，然后更新x(k)←x(k-1)，接着更新x的支集Γ(k)←Γ(k-1)，最后更新w(k).具体地，在试验中对于∀i∈Γ，有
| $ w_i^{(k)} = \frac{{w_i^{(k - 1)}}}{{\beta |x_i^{(k - 1)}| + \xi }} $ |
其中，
|
|
表 2 自适应权重GPSR算法 Table 2 Adaptive reweighting via GPSR algorithm |
自适应权重GPSR算法的计算量主要在step 1的
本节将通过实验从重构精度和计算复杂度两方面来验证所提出的自适应权重GPSR算法(ARGP)的优越性.较于凸优化算法的GPSR系列算法以及近期较看好的自适应凸优化算法ARW-H[18]，ARGP可以较低的计算复杂度得到较高质量的重构信号.
考虑一个典型的压缩感知方案.本实验选择稀疏度S=160的0-1信号作为模拟信号进行仿真实验，原始信号长度N=4 096，测量信号长度K=1 024，同时为了模拟有噪声的自然信号的特点，对产生的观测信号添加方差为0.01的高斯白噪声，测量矩阵为高斯随机矩阵.实验环境为Matlab7.10.0 (R2010a).
本文采用的GPSR系列算法有：GPSR-Basic、单调线搜索GPSR-BB(GPSR-BB-mono)以及非单调线搜索GPSR-BB(GPSR-BB-notmono).GPSR-BB算法即在GPSR算法中使用Barzilai-Borwein步长作为迭代步长.基于文献[14]设置以上算法参数：β=0.5，μ=0.1，τ=0.1‖ATy‖∞.基于文献[18]设置ARW-H算法的参数：
图 1为原始信号以及利用ARGP算法、ARW-H算法和GPSR系列算法得到的重构信号的比较图，可以看出：ARGP算法不仅能够准确找到原始稀疏信号的尖端位置(即信号分量±1的位置)，而且在尖端位置的估计值与原始信号极为近似.ARGP得到的重构信号关于原始信号的均方误差(MSE)为3.16×10-5，ARW-H算法的重构MSE为2.3×10-4，与GPSR系列算法的重构MSE相差不大，约为2.45×10-3.本文提出的ARGP算法的MSE明显低于其他算法.
|
图 1 信号重构效果 Fig. 1 The performance of signal reconstruction |
选择重构信号较好的ARW-H算法作为其他算法的代表与ARGP算法做进一步比较，结果见图 2. ARGP算法在信号尖端位置表现非常好，几乎与原始信号尖端位置的值一致；且重构信号的稀疏结构(即0分量位置)与原始信号也较为一致.而ARW-H算法尖端位置的值通常比原始信号小，且其稀疏结构也与原始信号相差较大.同时在此次试验中，ARGP的CPU时间为0.702 0 s，而ARW-H算法需要的CPU时间为20.670 8 s.所以，无论是重构精度还是时间复杂度，本文设计的ARGP算法均表现更好，特别在时间复杂度上，优势更为明显.
|
图 2 重构效果比较 Fig. 2 Comparison of reconstruction performance |
图 3显示了目标函数值随迭代次数下降的情况，可以看出迭代至第3步，ARGP仍有较大的下降空间，而上文提及的另外3个GPSR算法却已趋于平缓.由图 4可知，ARGP算法比其余3种算法的精度更高.总体来说, ARGP算法更为有效.
|
图 3 目标函数值的比较 Fig. 3 Comparison of objective function |
|
图 4 重构误差的比较 Fig. 4 Comparison of reconstruction MSE |
以上是凸优化类重构算法的比较，下文将对自适应权重的GPSR算法和典型贪婪类重构算法OMP算法在性能上做比较，详见表 3，表中值均为运行100次得到的平均值.
|
|
表 3 算法性能比较 Table 3 The comparison of algorithm performance |
经对原始信号分析知，‖x‖1越接近160越好.由表 3知，在cpu时间上，ARGP算法较ARW-H算法具有明显的优势；在重构误差和‖x‖1上，ARGP算法明显优于GPSR-Basic算法，重构误差降低了99.9%，和‖x‖1的接近程度提高了41.0%，虽然cpu时间比GPSR-Basic增加了0.374 s，但是以较小的时间复杂度换取误差率降低99.9%，是很值得的选择.总之，ARGP算法在cpu时间、重构误差和‖x‖1上都较OMP算法优势明显.
4 结论通过给压缩感知重构模型添加惩罚系数的方式优化了传统的l1重构模型，并根据新的模型，在每步GPSR迭代过程中，添加自适应改变权重的步骤，对GPSR算法进行了改进.实验结果证明，与其他投影梯度算法和典型贪婪算法相比，该算法无论在信号重构精度上还是在运行时间上，均具显著优势.但本文仅使用了一种自适应改变权重的方法，是否可以将2种自适应改变权重的方法组合使用来提高重构效果，有待进一步研究.
| [1] | DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289–1306. DOI:10.1109/TIT.2006.871582 |
| [2] | GEORGE S N, AUGUSTINE N, PATTATHIL D P. Audio security through compressive sampling and cellular automata[J]. Multimedia Tools and Applications, 2015, 74(23): 10393–10417. DOI:10.1007/s11042-014-2172-2 |
| [3] | LIU Z, LI Z, LI M, et al. Path reconstruction in dynamic wireless sensor networks using compressive sensing[J]. IEEE/ACM Transactions on Networking, 2016, 24(4): 1948–1960. DOI:10.1109/TNET.2015.2435805 |
| [4] | TROPP J A, GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655–4666. DOI:10.1109/TIT.2007.909108 |
| [5] | 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 |
| [6] | BLUMENSATH T, DAVIES M E. Iterative hard thresholding for compressed sensing[J]. Applied and Computational Harmonic Analysis, 2009, 27(3): 265–274. DOI:10.1016/j.acha.2009.04.002 |
| [7] |
李珅, 马彩文, 李艳, 等. 压缩感知重构算法综述[J].
红外与激光工程, 2013, 42(S1): 225–232.
LI K, MA C W, LI Y, et al. Survey on reconstruction algorithm based on compressive sensing[J]. Infrared and Laser Engineering, 2013, 42(S1): 225–232. |
| [8] | WRIGHT S J, NOWAK R D, FIGUEIREDO M A T. Sparse reconstruction by separable approximation[J]. IEEE Transactions on Signal Processing, 2009, 57(7): 2479–2493. DOI:10.1109/TSP.2009.2016892 |
| [9] | BABACAN S D, NAKAJIMA S, DO M N. Bayesian group-sparse modeling and variation an inference[J]. IEEE Transactions on Signal Processing, 2014, 62(11): 2906–2921. DOI:10.1109/TSP.2014.2319775 |
| [10] | OLIVERI G, CARLIN M, MASSA A. Complex-weight sparse linear array synthesis by Bayesian compressive sampling[J]. IEEE Transactions on Antennas and Propagation, 2012, 60(5): 2309–2326. DOI:10.1109/TAP.2012.2189742 |
| [11] | YU L, WEI C, JIA J, et al. Compressive sensing for cluster structured sparse signals:Variational Bayes approach[J]. Let Signal Processing, 2016, 10(7): 770–779. |
| [12] | ZAYYANI H, BABAIE-ZADEH M, JUTTEN C. Decoding real-field codes by an iterative expectation-maximization (EM) algorithm[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. Las Vegas: IEEE, 2008: 3169-3172. |
| [13] | BARANIUK R G, CEVHER V, DUARTE M F, et al. Model-based compressive sensing[J]. IEEE Transactions on Information Theory, 2010, 56(4): 1982–2001. DOI:10.1109/TIT.2010.2040894 |
| [14] | FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586–597. DOI:10.1109/JSTSP.2007.910281 |
| [15] | FOUCART S, RAUHUT H. A mathematical introduction to compressive sensing[C]//Applied and Numerical Analysis. NewYork: Spring, 2013. |
| [16] | CAI T T, JIANG T. Limiting laws of coherence of random matrices with applications to testing covariance structure and construction of compressed sensing matrices[J]. The Annals of Statistics, 2011, 39(3): 1496–1525. DOI:10.1214/11-AOS879 |
| [17] | CANDÈES E J, PLAN Y. A probabilistic and RIPless theory of compressed sensing[J]. IEEE Transactions on Information Theory, 2011, 57(11): 7235–7254. DOI:10.1109/TIT.2011.2161794 |
| [18] | ASIF M S, ROMBERG J. Fast and accurate algorithms for re-weighted L1-norm minimization[J]. IEEE Transactions on Signal Processing, 2013, 61(23): 5905–5916. DOI:10.1109/TSP.2013.2279362 |
| [19] |
刘建伟, 崔立鹏, 刘泽宇, 等. 正则化稀疏模型[J].
计算机学报, 2015, 38(7): 1307–1325.
LIU J W, CUI L P, LIU Z Y, et al. Survey on the regularized sparse models[J]. Chinese Journal of Computers, 2015, 38(7): 1307–1325. DOI:10.11897/SP.J.1016.2015.01307 |
| [20] | CHEN W, RODRIGUES M R D, WASSELL I. A fréchet mean approach for compressive sensing date acquisition and reconstruction in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2012, 11(10): 3598–3606. DOI:10.1109/TWC.2012.081612.111908 |