孙娜;刘继文;肖东亮
【摘 要】平滑l0范数(SL0)算法是一种基于近似l0范数的压缩感知信号重构算法,采用最速下降法和梯度投影原理,通过选择一个递减序列来逐步逼近最优解,具有匹配度高、计算量低、不需要已知信号稀疏度等优点.但是,其迭代方向为负梯度方向,使得在迭代过程中产生\"锯齿现象\",导致在最优解附近收敛速度较慢.牛顿法具有较快的收敛速度,但是对初值的要求较高,并且需要计算Hesse矩阵.拟牛顿法则克服了这个缺点,利用BFGS公式计算Hesse矩阵的近似矩阵,只需要计算1阶导数信息.该文在SL0算法的基础上,结合BFGS拟牛顿法,提出一种改进的压缩感知信号重构算法.首先采用最速下降法迭代得到信号的某个估计值,然后将此估计值作为拟牛顿法的初值继续迭代,直至得到最优解.计算机仿真结果表明,在相同的条件下,该算法在重构精度、峰值信噪比和重建匹配度等方面均有较大提高. 【期刊名称】《电子与信息学报》
【年(卷),期】2018(040)010
【总页数】7页(P2408-2414)
【关键词】压缩感知;重构算法;平滑l0范数;BFGS
【作 者】孙娜;刘继文;肖东亮
【作者单位】中国农业大学信息与电气工程学院 北京 100083;中国农业大学信息与电气工程学院 北京 100083;中国农业大学信息与电气工程学院 北京 100083
【正文语种】双城记电视剧中 文
【中图分类】TN911.7
1 引言
传统的奈奎斯特采样定理要求采样频率至少为信号带宽的两倍时才可以不失真地重构出原始信号，该理论需要较高的采样率，并且采样所得到的信息中，绝大多数都是冗余的，造成了采样资源的严重浪费。压缩感知(Compressive Sensing,CS)[1–3]理论是基于信号稀疏性或可压缩性而提出的一种全新的信号处理理论。该理论表明，通过少量的测量值就可以
实现稀疏或可压缩信号的精确重构，克服了采样数据量大，采样时间以及数据存储空间等物理资源严重浪费的问题。现已在图像处理，认知无线电通信，无线传感器网络，雷达成像等领域[4–7]得到广泛应用。该理论主要包括信号的稀疏表示、编码测量以及重构算法3个方面。其中，重构算法是压缩感知的核心，关键问题是如何用较少的低维测量值来快速、稳定、精确或最大程度地恢复出原始信号。目前已有的重构算法从广义上主要分为两类：一类是基于l0范数最小化的贪婪迭代匹配追踪系列算法[8–11]，另一类是基于l1范数最小化的松弛算法[12,13]。
平滑l0范数(Smoothedl0Norm,SL0)算法是Mohimani等人[14]于2009年提出的，是一种基于过完备稀疏分解的快速算法。该算法使用带参数的平滑函数去逼近向量的最小l0范数，将求解最小l0范数问题转化为求解平滑函数的极值问题。2011年林婉娟等人[15]用双曲正切函数替代高斯函数，利用牛顿法更新迭代方向，提出了NSL0算法； 2012年杨良龙等人[16]用近似双曲正切函数替代高斯函数，提出了ANSL0(Almost Newton Smoothedl0Norm)算法，同年，王军华等人[17]通过利用快速不动点构造下降方向，提出了ISL0(Iterative SL0)算法，2013年Ye等人[18]将压缩感知用于稀疏信道估计，提出了l2-SL0算法；2014年Mohammadi等人[19]将压缩感知用于求解非负条件下的稀疏分解，提出了CSL0(Constrain ed SL0)算法；2015年李颖等人[20]利用反正切函数近似高斯函数，提出了L0AM(l0Norm Approximation Minimization)算法。本文在SL0算法的基础上，结合BFGS拟牛顿法，提出了一种改进的压缩感知信号重构算法(以下简称BFGSSL0算法)。首先利用最速下降法迭代得到一个估计值，然后将此估计值作为拟牛顿法的初值继续迭代，用BFGS公式更新迭代方向，结合不精确1维搜索求取步长，直至得到最优解。经过计算机仿真，验证了该算法在重构精度、峰值信噪比(Peak Signal to Noise Ratio,PSNR)和重建匹配度[21](Reconstruction Matching Degree,ReMD)等方面均有较大提高。sis 6326
本文第2节介绍了SL0算法基础，第3节详细给出了BFGS-SL0算法的步骤，第4节进行了计算机仿真，并对结果进行了分析和比较，最后给出了结论。
2 SL0算法
压缩感知重构算法的基本模型是求解式(1),SL0算法通过选取平滑的连续函数去逼近矢量的l0范数，利用凸优化算法中的最速下降法和梯度投影原理，求出使l0范数最小的量。
定义标准高斯函数：
其中，σ＞0。可以推出½：
假设有式(4)定义：
其中，xi表示向量 中的第i个分量。由以上性质可得
σ的取值决定了函数的光滑程度：σ值越大，函数越光滑，越容易求得极小值；σ值越小，函数越粗糙，局部极小值越多，越接近向量 的l0范数。当σ=0时，，但这是不存在的，只能选择一个σ递减序列来逐步逼近l0范数。
SL0算法利用最速下降法即负梯度方向来更新迭代方向，仅需要计算1阶导数信息，计算量较小，但是在迭代过程中存在“锯齿现象”，使得收敛速度减慢并且不容易收敛到最优解。牛顿法具有较快的收敛速度，但是需要计算2阶偏导数，而且目标函数的Hesse矩阵可能非正定，计算量增大的同时可能导致求解问题为病态的。拟牛顿法则克服了这个缺点，用不包含2阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵[22]，从而减小了计算量。因此，本文针对SL0算法的不足，结合BFGS拟牛顿法，提出了BFGS-SL0算法。
3 BFGS-SL0算法
3.1 BFGS拟牛顿法
牛顿法的迭代公式为
其中，是在点处的牛顿方向，
λk是从出发沿牛顿方向的最优步长。
设在第k次迭代后，得到点，将目标函数在点展开为Taylor级数，并取2阶近似，得到
由此可知，在附近有
3.2 BFGS-SL0算法
张博树4 计算机仿真
伊犁师范学院学报为了验证该算法的有效性，本文基于MATLAB R2012a平台进行了计算机仿真。实验所用测量矩阵均为高斯随机测量矩阵。以下对1维信号重构、重构误差对比、稀疏度对重构性能的影响以及2维图像重构进行仿真与分析。
时空曲率
4.1 1维信号的重构
图1给出了1维信号的重构仿真图。信号长度N=256，测量值个数M=128，稀疏度K=30,σ终值设为 1×10-2。可以看出，重构信号与原始信号基本吻合，计算得到重构误差为5.4112×10-4，可见本文算法能够实现对原始信号的重构。
图1 1维信号的重构仿真图
4.2 重构误差对比
图2给出了本文算法与SL0算法在重构误差上的对照仿真图，基本参数与前述设置相同，进行50次独立重复实验。可以看出，本文算法重构误差远小于SL0算法，验证了本文算法在重构精度上有较大提高。
图2 重构误差对照仿真图
4.3 稀疏度对重构性能的影响
图3给出了稀疏度对重构性能的影响仿真图。信号长度N=256，测量值个数M=128,σ终值设
为1×10-2，独立重复500次实验，并与SL0算法、NSL0算法、ISL0算法、L0AM算法进行对照。可以看出，当测量值一定时，对于每种算法，稀疏度增加到某个值时重构概率开始降低。相比于其他算法，当稀疏度增加到50时，BFGS-S L0算法依然可以以较高的概率重构原始信号。
图3 稀疏度对重构性能的影响仿真图
4.4 图像重构对照
图4和图5分别给出了不同算法下Lena图像和Cameraman图像的重构仿真图，表1和表2分别给出了不同算法下Lena图像和Cameraman图像的重构参数对照。仿真所用图像大小均为 2 56×256，采样率均为0.5,Lena图像和Cameraman图像分别为BMP格式和TIF格式，代表不同格式的图像重构效果。对于Lena图像，由图4可以看出，BFGSSL0算法的重构图像最清晰。由表1可知，ISL0算法相比于SL0算法重构精度略有提高，却有较慢的重构速度。本文提出的BFGS-SL0算法相比于SL0算法PSNR提高了大约2.5 dB，重构时间较SL0算法和NSL0算法略有增加，却远小于ISL0算法和L0AM算法。图5中，从直观上来看，L0AM算法的恢复图像最不清晰，BFGS-SL0算法最清晰。由表2可以看出，BFGS-SL0算法相比于
经典SL0算法PSNR提高了大约3 dB，重构时间略有增加，却仍属于同一数量级。因此，本文算法在图像处理中具有较好的效果。
5 结论
本文针对SL0算法求最优解时存在“锯齿现象”的问题，结合BFGS拟牛顿法，提出了一种改进的压缩感知信号重构算法，即BFGS-SL0算法。该算法首先利用最速下降法对初值要求不高的特点进行迭代，得到信号的某个估计值，然后将此估计值作为拟牛顿法的初值继续迭代，利用BFGS公式更新迭代方向，同时采用不精确1维搜索求取步长，从而减小了计算复杂度。经过计算机仿真，验证了该算法在重构精度、峰值信噪比和重建匹配度等方面均有较大提高。
图4 Lena图像重构仿真图
图5 Cameraman图像重构仿真图
表1 Lena图像重构参数对照表算法 相对误差 峰值信噪比(dB) 重建匹配度 重构时间(s)SL0 0.070720 28.408407 0.988565 1.520847 NSL0 0.060162 29.754635 0.990416 1.162797
沈长富ISL0 0.062446 29.423168 0.989117 35.939030 L0AM 0.079117 27.436772 0.985986 78.190602 BFGS-SL0 0.051846 30.963193 0.991374 5.106042
表2 Cameraman图像重构参数对照表算法 相对误差 峰值信噪比(dB) 重建匹配度 重构时间(s)SL0 0.074593 25.717452 0.980426 1.362892 NSL0 0.063440 27.123689 0.985850 1.018830 ISL0 0.069222 26.414663 0.983943 35.028154 L0AM 0.082170 25.002774 0.982677 68.704621 BFGS-SL0 0.053996 28.604430 0.990689 8.143261
参 考 文 献
【相关文献】
[1]CANDES E J,ROMBERG J,and TAO T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489–509.doi:10.1109/TIT.2005.862083.
