周洁容, 李海洋, 凌军, 陈浩, 彭济根. 基于非凸复合函数的稀疏信号恢复算法. 自动化学报, 2022, 48(x): 1−12 doi: 10.16383/j.aas.c200666    

Zhou Jie-Rong, Li Hai-Yang, Ling Jun, Chen Hao, Peng Ji-Gen. Sparse signal reconstruction algorithm based on non-convex composite function. Acta Automatica Sinica, 2022, 48(x): 1−12 doi: 10.16383/j.aas.c200666   

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200666?viewType=HTML

压缩感知, 稀疏信号重构, MM技术, 外点罚函数法, 共轭梯度法

基于泛函深度作用的思想, 通过将两种非凸稀疏泛函进行复合, 构造了一种新的稀疏信号重构模型, 实现了对0范数的深度逼近. 综合运用MM (Majorize minimization)技术、外点罚函数法和共轭梯度法, 提出一种求解该模型的算法, 称为NCCS (Non-convex composite sparse)算法. 为降低重构信号陷入局部极值的可能性, 提出在算法的每步迭代中以BP (Basis pursuit)模型的解作为初始迭代值. 为验证所建模型和所提算法的有效性, 进行了多项数值实验. 实验结果表明, 相较于SL0 (Smoothed L_0)算法、IRLS (Iterative reweighed least squares)算法、SCSA (Successive concave sparsity approximation)算法以及BP 算法等经典算法, 提出的算法在重构误差、信噪比、归一化均方差、支撑集恢复成功率等方面都有更优的表现.

根据奈奎斯特(Nyquist)采样定律, 想要实现信号的无失真输出, 采样频率必须在信号带宽的两倍以上. 然而, 在大多数情形下, 按此定律采样所获得的信息是冗余的, 这不仅造成采样的浪费, 而且处理较大带宽的信号时会给硬件系统带来巨大压力. 压缩感知(Compressed sensing, CS)的出现使该问题的解决成为可能. 压缩感知是一种新型的信号采样及重构理论, 利用少量的测量值就可以实现稀疏或可压缩信号的精确重构. 而稀疏信号的重构在众多科学研究和工程应用中十分重要, 如物理学中的量子态层析成像、天体物理学成像、磁共振成像、信号处理、雷达成像等, CS理论的引入加快了上述应用的研究和发展.

数学上, 稀疏信号重构是指从欠定线性系统b=Ax中恢复原始信号x, 其中b∈R^n是测量向量, A∈R^{n×m} (n<m)为感知矩阵, x∈R^m是未知的稀疏向量. 最稀疏信号的重构模型是:

其中, ||x||_0表示向量x中非零元素的个数.

已经证明, (P_0)模型的直接求解是NP (Non-deterministic polynomial)难的, 其计算量会随着稀疏向量维数的增加而增大, 模型的抗噪能力也很差. 为此人们提出了多种方法对(P_0)模型进行求解, 主要方法可归类于启发式方法、凸松弛方法、非凸松弛方法三种类型. 典型的启发式算法有正交匹配追踪、阈值算法、子空间追踪算法、分级正交匹配追踪等, 这些算法重构理论简单、速度较快, 但往往需要更多观测, 算法的重构精度较低、收敛速度较慢, 并且在有噪声情况下信号的恢复精度较低, 因此其应用范围有限. 典型的凸松弛算法有梯度投影算法、BP (Basis pursuit)算法、BPDN (Basis pursuit denoising)算法、IRLS (Iterative reweighed least squares)算法、Bregma迭代法等, 其中最经典的是BP算法, 文献[18]证明了在测量矩阵满足有限等距性质的条件下BP模型与(P_0)模型等价, 但在多种情形下BP模型中的L1范数不能充分反映信号的稀疏性特征, 往往难以获得稀疏解. 为此, 人们提出了用非凸泛函替代L_0范数的方法, 称之为非凸松弛方法.

相较于L_1范数, 许多非凸泛函能更好地近似L_0范数, 从而更好地反映信号的稀疏性特征. 典型的非凸松弛算法有NSL0 (Newt-on smooth L_0 norm)算法、SL0 (Smoothed L_0)算法、CTNRAL0 (Composite trigono-metric function null-space reweighted appro-ximate L_0 norm)算法、SCSA (Successive concave sparsity approximation)算法等. 易见, 松弛方法的核心是寻找L_0范数的逼近函数, 通过极小化该逼近函数寻得最稀疏解. 显然这种近似模型对(P_0)模型的逼近性能取决于所选取的近似函数对L_0范数的逼近程度. 因此, 如何构造具有更优逼近性能的近似函数已成为稀疏信号重构问题研究中的重要问题.

最近, 文献[23−24]分别构造了两种近似函数g_σ(x)=1−e^{−|x|/σ}、h_σ(x)=|x|/(|x|+σ)以实现对L0范数的逼近, 取得了较好的重构效果. 一个有趣的想法是, 如果将上述每个泛函对信号的作用看成是一次前向(Forward)处理过程, 那么我们是否可以通过泛函的复合实现对信号的深度作用, 从而提高信号重构的性能? 基于这种想法, 本文将上述两个泛函进行复合, 构建一种新的非凸松弛模型, 给出该模型的理论分析, 对该模型提出一种新的近似算法, 并通过数值实验验证算法的有效性以及相较于SL0算法、IRLS算法、BP算法、SCSA算法等经典算法的优越性.

图 5  SL0、IRLS、BP、SCSA、NCCS 5种算法的重构误差和稀疏度的变化关系

图 6  SL0、IRLS、BP、SCSA、NCCS 5种算法的重构信噪比和稀疏度的变化关系

图 7  SL0、IRLS、BP、SCSA、NCCS 5种算法的运行时间和稀疏度的变化关系

图 8  SL0、IRLS、BP、SCSA、NCCS 5种算法的支撑集恢复成功率和稀疏度的变化关系

图 9  SL0、IRLS、BP、SCSA、NCCS 5种算法的归一化均方差和稀疏度的变化关系