引用本文

周洁容, 李海洋, 凌军, 陈浩, 彭济根. 基于非凸复合函数的稀疏信号恢复算法. 自动化学报, 2022, 48(7): 1782−1793 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(7): 1782−1793 doi: 10.16383/j.aas.c200666

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200666

关键词

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

摘要

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

文章导读

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

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

其中, ∥x∥0表示向量x中非零元素的个数[7].

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

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

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

图 1  4种函数在σ=0.1时的一元函数分布

图 3  待定数α对NCCS算法运行时间的影响

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

本文运用MM优化、外点罚函数法、共轭梯度法等方法, 借鉴文献[23]提出的SCSA算法思想, 提出了一种新的稀疏信号重构算法, 称为NCCS算法. 该算法利用逼近性能更优的非凸复合指数函数实现对L0范数的逼近. 仿真实验表明, 本文所提出的NCCS算法不仅有效可行, 而且在无噪声情况下, 对比SL0、IRLS、BP、SCSA这4种算法, NCCS算法在稀疏信号恢复实验中表现出更优越的重构性能.

作者简介

周洁容

广州大学机器生命与智能研究中心硕士研究生. 广州大学数学与信息科学学院硕士研究生. 2014 年获得岭南师范学院数学学士学位. 主要研究方向为稀疏信息处理. E-mail: jrzhouzoe@163.com

李海洋

广州大学机器生命与智能研究中心教授. 广州大学数学与信息科学学院教授. 2008 年获得陕西师范大学基础数学博士学位. 主要研究方向为量子逻辑理论, 机器学习理论和稀疏信息处理. E-mail: fplihaiyang@126.com; fplihaiyang@126.com

凌军

广州大学机器生命与智能研究中心博士研究生. 广州大学数学与信息科学学院博士研究生. 2019 年获得南昌大学概率论与数理统计硕士学位. 主要研究方向为小目标运动检测, 算子半群理论和人工智能. E-mail: gdalingjun@163.com

陈浩

广州大学机器生命与智能研究中心硕士研究生. 广州大学数学与信息科学学院硕士研究生. 2015 年获得广州大学数学学士学位. 主要研究方向为小目标运动检测, 人工智能和计算神经学. E-mail: gdchenhao@126.com

彭济根

广州大学机器生命与智能研究中心教授. 广州大学数学与信息科学学院教授. 1998 年获得西安交通大学计算数学博士学位. 主要研究方向为非线性泛函分析, 机器学习理论, 稀疏优化和碰撞检测的数学理论与方法. 本文通信作者. E-mail: jgpeng@gzhu.edu.cn