1. 引言
传统的数据采集需要满足奈奎斯特采样定理,即为了不失真的恢复信号,采样频率必须大于信号最高带宽的两倍。但在这一理论指导下所获得的信息是冗余的,极大的影响了信息领域的发展。压缩感知(Compressive Sensing, CS) [1] 是一种新型的信号采集与重构理论,它可通过远低于奈奎斯特标准的方式进行数据采样,并仍能够精确地恢复稀疏信号。该理论提出后,在阵列信号处理 [2]、医学影像 [3] 和雷达探测 [4] 等领域受到高度关注,展现出了巨大的应用价值。压缩感知理论主要包括三部分:信号的稀疏表示、测量矩阵的设计和稀疏信号重构。其中,稀疏信号重构是指从较少的测量值中精确地恢复原始信号,是CS理论中最重要的一部分。信号的重构精度主要取决于重构算法的性能,设计高效的重构算法是提高稀疏信号重构精度的关键。因此,稀疏信号重构算法具有重要的研究意义。
从数学的角度来看,通常使用以下最小化方法对稀疏信号重构问题进行建模 [5]:
(1)
其中
是感知矩阵,
是测量向量,
是未知的稀疏向量,
是实向量x的零范数。
然而,由于l0范数的不连续性,使得基于l0范数的重构模型的直接求解是NP (Non-deterministic Polynomial)难的 [6],其计算量会随稀疏向量维数的增加而增大,且模型的抗噪能力较差。为此学者们提出了很多方法对最小化l0范数进行近似求解,如贪婪方法、凸松弛方法和非凸松弛方法等。贪婪算法通过选择与信号重构残差最匹配的原子进行信号重构,传统的贪婪算法有正交匹配追踪算法 [7]、广义正交匹配追踪算法 [8] 和子空间追踪算法 [9] 等,这类算法重构理论简单、计算速度较快,但重构精度较低,需要更多观测值。凸松弛方法将最小化l0范数转化为最小化l1范数,其中典型的算法有基追踪算法 [10]、迭代阈值算法 [11] 和梯度投影法 [12] 等,这类算法重构精度较高、所需测量值较少,但计算复杂度较高,不适合求解大规模问题。因此这两类算法应用范围有限。
近年来,利用非凸松弛方法近似求解l0范数受到了广泛关注。常见的非凸松弛方法使用lp范数、高斯类函数或分式类函数近似l0范数,其中高斯类函数是一种最常见的近似函数。最早Mohimani等人提出了光滑l0 (Smoothed l0 norm, SL0)算法 [13],该算法利用标准高斯函数近似l0范数,并结合最速下降法寻求最优解;随后林婉娟等人提出了利用双曲正切函数和修正牛顿法的牛顿光滑l0 (Newton Smoothed l0 norm, NSL0)算法 [14];张巍等人通过引入近似双曲正切函数和混合优化方法提出了近似阻尼牛顿光滑l0 (Almost- Hybird Newton Smoothed l0 norm, A-HNSL0)算法 [15];2020年,周洁容等人提出的非凸复合稀疏基(Non-convex Composite Sparse bases, NCCS)算法 [16] 中采用复合指数函数近似l0范数,并结合外点罚函数法和共轭梯度法求得最优解。这类方法对稀疏信号的恢复性能由所使用的函数对l0范数的逼近程度以及对该函数的求解方法所决定。
SL0算法具有重构速度快,算法简单等优点,但该算法采用的高斯函数的陡峭性不大,不能更好地逼近l0范数,且利用最速下降法进行求解会产生“锯齿现象”,不能求得全局最优解,从而导致算法重构精度不高。针对以上不足,本文利用一种陡峭性更强的非凸光滑函数逼近l0范数,并通过外点罚函数法和共轭梯度法求得稀疏解,提出了一种改进的近似l0范数的稀疏信号重构算法,即INCS (Improved non-convex sparse bases)算法。最后通过仿真实验验证了本文算法在重构误差、信噪比和恢复成功率等方面较于SL0算法、基追踪算法和NCCS算法的优越性。
2. SL0算法
压缩感知中稀疏信号重构算法是求解最优化问题(1),对任意的
,
可表示为
,其中
。
由于l0范数是不连续的,SL0算法中Mohimani等人首次提出利用连续函数
来逼近
,其中
为控制参数,显然有:
(2)
令
,对任意的
,可得到
。故最小化l0范数问题(1)可转化为
以下优化问题:
(3)
SL0算法利用最速下降法和梯度投影原理求解该优化问题。该算法具有重构速度快,算法简单等优点,但采用的连续函数的陡峭性不大,使得近似l0范数的估计不准确;且最速下降法会出现“锯齿现象”,不能求得全局最优解,从而导致算法的重构精度不高。
3. 基于改进的近似l0范数的稀疏信号重构算法
3.1. 改进的近似l0范数
为了提高近似函数对l0范数的逼近程度,本文采用一种改进的非凸光滑函数近似l0范数:
(4)
其中c为大于等于1的常数,
为控制参数。
文献 [13] 和 [16] 中分别采用了以下两种函数来近似l0范数:
、
下面从几何图像和理论分析上说明本文提出的函数
比函数
和
更逼近l0范数。
1) 几何图像分析
函数
、
和
的几何图像如图1所示,可以看出,函数
的图像曲线相比于其他两种函数更陡峭,即函数
对l0范数的逼近效果更好。
![](//html.hanspub.org/file/17-1542252x39_hanspub.png?20210902075851635)
Figure 1. Comparison chart of the three functions at
图1.
时三种函数的对比图
2) 理论分析
假定
,则对区间内任意
有
、
、
,
因为
(5)
所以比较函数
和
的大小只需要比较他们的指数大小,易得:
(6)
因此
;
同理
(7)
因为
(8)
所以
。
利用函数对称性,
时也可类似讨论。因此可以得到
,即当
时,函数
对应的函数值比其他两种函数对应的函数值更加接近于1,这意味着函数
比其他两种函数更逼近l0范数。
3.2. 算法实现
下面基于所改进的函数
对(3)式进行求解。令
,其中
,u为x中所有的正元,其余元素为零;v为x中所有负元的绝对值,其余元素也为零,利用
表示拼接向量。
经过替换,可得:
(9)
此时约束条件
转化为
,所以(3)式转化为:
(10)
为了方便求解(10)式,利用非凸函数
的一阶判别条件及优化最小化(Majorize-Minorize, MM)方法 [17] 对目标函数
进行放缩,可得:
(11)
记
(12)
其中
为可行域中的点,
为常值,则
为
的一个上界函数。
忽略常值后,则(10)式的解由下式迭代求得:
(13)
其中
为可行域中的点,取值与
有关。
令
则(13)可简记为:
(14)
因此,(3)式的优化问题转化为(14)式的优化问题。
本文利用外点罚函数法 [18] 和共轭梯度法迭代求解(14)式,具体步骤如下:
利用外点罚函数法引入正数M,本文取
,放大倍数为5,将(14)式转化为以下无约束问题:
(15)
其中
(16)
式中I为
的单位向量,
,
,则函数
有关z的一阶、二阶次梯度 [19] 分别为:
(17)
(18)
其中
。
再利用共轭梯度法迭代求解(15)式的
,其迭代更新格式为:
(19)
其中步长因子为:
(20)
下降方向为:
(21)
其中令
,
,
。
综上所述,本文所提出的INCS算法的流程如下:
Step 1输入:矩阵A、测量向量b,
;
Step 2初始化:
1) 设置递减序列
,
,其中
,
为
的递减因子,本文设置
,
;
2) 设置初始值:
,
;
Step 3算法迭代:
1)
,
;
2) while
do
1:{
,
,
,
2:while
do
3:{
,
4:
,
5:
}
6:
,
7:
,
8:
},
9:
,
10:
,
11:
;
Step 4输出稀疏向量:
。
其中Step 3由内、外两部分循环构成。外循环由步骤1~2及6~8组成,通过参数
实现函数
对
范数的逐次逼近;内循环为步骤3~5,利用外点罚函数法和共轭梯度法迭代求解步骤4;并将求得的解利用加权
范数最小化 [20] 进行稀疏化处理。
和
分别表示外、内循环连续迭代的解之间的相对误差,并用于判断循环是否停止。
4. 仿真实验与结果分析
为验证本文所提出的INCS算法在重构性能上的优越性,本节设计了几组有关SL0算法、基追踪(Basis Pursuit, BP)算法、NCCS算法和INCS算法的对比实验。对于每个实验,我们重复进行100次测试,给出平均结果,并取
。仿真实验结果是在MatlabR2014a的条件下获得的。
在仿真实验中,矩阵A的大小为
,其中矩阵元素服从零均值、单位方差的高斯分布,矩阵的列具有单位l2范数;稀疏原信号x的维数为256,非零项服从正态分布;信号稀疏度k取值区间为
。
实验中所涉及到的性能指标包括:
1) 重构误差(mean squared error):
2) 信噪比(signal noise ratio):
3) 算法运行时间
4) 恢复成功率(recovery success rate):当
时,
说明算法在该点处重构成功,
其中
表示稀疏原信号,
表示算法的恢复信号;
图2为各算法的重构误差MSE和稀疏度的变化关系,实验结果如图2及表1所示。由图2和表1可见,BP算法、NCCS算法和INCS算法都存在随着稀疏度的增加重构误差增大的趋势。在同一稀疏度下,相比于其他三种算法,INCS算法的重构误差略小。
![](//html.hanspub.org/file/17-1542252x141_hanspub.png?20210902075851635)
Figure 2. The relationship between the reconstruction error and sparsity of the SL0 algorithm, BP algorithm, NCCS algorithm and INCS algorithm
图2. SL0算法、BP算法、NCCS算法、INCS算法的重构误差和稀疏度的变化关系
![](Images/Table_Tmp.jpg)
Table 1. The numerical record of the reconstruction error of each algorithm changing with the sparsity k
表1. 各算法的重构误差随着稀疏度k变化的数值记录
图3为各算法的重构信噪比SNR和稀疏度的变化关系,实验结果如图3及表2所示。可以看出,在稀疏度区间
上,INCS算法和NCCS算法的信噪比变化不大且相差很小,但明显高于SL0算法和BP算法的信噪比;在稀疏度区间
上,各算法的信噪比随着稀疏度的增加而减小,但INCS算法的信噪比仍高于其他三种算法。
![](//html.hanspub.org/file/17-1542252x152_hanspub.png?20210902075851635)
Figure 3. The relationship between the signal-to-noise ratio and sparsity of the SL0 algorithm, BP algorithm, NCCS algorithm and INCS algorithm
图3. SL0算法、BP算法、NCCS算法、INCS算法的重构信噪比和稀疏度的变化关系
![](Images/Table_Tmp.jpg)
Table 2. The numerical record of the signal-to-noise ratio of each algorithm changing with the sparsity k
表2. 各算法的重构信噪比随着稀疏度k变化的数值记录
图4为各算法的运行时间和稀疏度的变化关系,实验结果如图4及表3所示。可以看出,SL0算法和BP算法的运行时间较短并能够保持在0.5秒以内。在稀疏度区间
上,INCS算法和NCCS算法的运行时间能保持在1秒以内,在稀疏度区间
上这两种算法的运行时间都有所增加,但对比NCCS算法,INCS算法的运行时间始终略短。
![](//html.hanspub.org/file/17-1542252x163_hanspub.png?20210902075851635)
Figure 4. The relationship between the running time and sparsity of the SL0 algorithm, BP algorithm, NCCS algorithm and INCS algorithm
图4. SL0算法、BP算法、NCCS算法、INCS算法的运行时间和稀疏度的变化关系
![](Images/Table_Tmp.jpg)
Table 3. The numerical record of the running time of each algorithm changing with the sparsity k
表3. 各算法的运行时间随着稀疏度k变化的数值记录
图5为各算法的恢复成功率RSS和稀疏度的变化关系,实验结果如图5及表4所示。可以看出,当稀疏度增加到一定程度时这四种算法的恢复成功率均开始降低。INCS算法的恢复成功率在稀疏度区间
上都能保持为1,也就是说在这个区间内该算法都能够实现信号的完全恢复。在稀疏度区间
上,INCS算法的恢复成功率始终略高于其他三种算法,所以利用INCS算法恢复信号时精确度有一定的提高。
![](//html.hanspub.org/file/17-1542252x174_hanspub.png?20210902075851635)
Figure 5. The relationship between the recovery success rate and sparsity of the SL0 algorithm, BP algorithm, NCCS algorithm and INCS algorithm
图5. SL0算法、BP算法、NCCS算法、INCS算法的恢复成功率和稀疏度的变化关系
![](Images/Table_Tmp.jpg)
Table 4. The numerical record of the recovery success rate of each algorithm changing with the sparsity k
表4. 各算法的恢复成功率随着稀疏度k变化的数值记录
综上所述,本文提出的INCS算法的综合重构性能优于实验中的对比算法,说明利用该算法能够更好的恢复稀疏信号。
5. 结论
本文提出了一种基于改进的近似l0范数的稀疏信号重构算法,即INCS算法。该算法利用一种逼近性能更优的非凸光滑函数实现对l0范数的逼近,并通过外点罚函数法和共轭梯度法求解基于该函数的稀疏解。实验结果表明:对比SL0算法、BP算法和NCCS算法,INCS算法在重构误差、信噪比和恢复成功率等方面表现出更优越的重构性能。
基金项目
长安大学中央高校基本科研业务费专项资金资助项目(编号:310812163504)。
参考文献
NOTES
*通讯作者。