2024年3月8日发(作者：德念柏)
L0范数平滑逼近的稳健求解算法王 峰*①② 向 新② 易克初① 熊 磊②
【摘 要】该文研究基于代理函数和先验概率密度的L0范数平滑逼近问题的稳健求解。首先，分析了平滑逼近函数的凹凸特性，给出提高恢复性能的参数调整策略与改进的SL0和FOCUSS算法。其次，将噪声背景下L0范数逼近过程进行正则化表示，并基于牛顿方向推导其迭代重加权形式的求解框架，给出一种新的代理函数。最后，使用数值仿真证实了所提算法可以提高此类问题的求解的稳健性，具有实用价值。
【期刊名称】电子与信息学报
【年(卷),期】2015(000)010
【总页数】6
【关键词】非凸压缩感知；L0范数平滑逼近；迭代重加权算法
1 引言
压缩感知[1]恢复算法，其核心是求解问题，其中,, 是一个满足RIP(Restricted
Isometry Property)准则的测量矩阵。因为L0范数最小化是N-P难的，所以发展出了贪婪算法、凸松弛算法(使用L1范数替代L0)、贝叶斯压缩感知等恢复方法。
除上述算法外，研究者还考虑使用代理函数来实现对L0范数的逼近，典型代表有SL0和ISL0等[2,3]。此处的代理函数，是指某一类参数化平滑可微的连续函数，通过调整其参数，可以逼近，从而使得这一N-P难问题变得可以规划求解。SL0算法提出后引起广泛关注，文献[4]设计了改进的SL0，并将其应用于ISAR(Inverse Synthetic Aperture Radar)成像。文献[5]发展了序贯SL0，用
以对机动目标进行ISAR成像。文献[6]开展了类似工作，使用SL0进行SAR图像重建。文献[7]基于SL0设计短时压缩感知，并用于微多普勒分析。文献[8,9]将SL0拓展至通信领域，用于稀疏信道估计与均衡。国内学者对L0范数逼近算法的研究，多以SL0算法框架为基础，使用新的代理函数和新的计算方向。应用方面，文献[15]将SL0应用于高分辨雷达1维成像，取得良好效果。
仿真表明，虽然计算效率较高，但SL0算法的性能并不占优势，尤其在引入噪声后，需要寻求更为稳健的求解方法。而且，目前尚未在SL0类算法和其他主流算法之间建立关联，其研究有待深化。
本文开展了如下工作：(1)分析了L0范数平滑逼近过程中目标函数的凹凸特性；(2)梳理了SL0类算法，FOCUSS[16]算法以及最近提出的[17]之间的内在关联，并给出改进算法，新算法在逼近过程中可避开一部分局部解，降低了提前收敛在非全局最优解上的风险；(3)基于牛顿方向和CCCP (ConCave-Convex
Procedure)[18]推导了一种迭代重加权恢复算法框架，对相同稀疏度的信号，同样的恢复效果下，需要较少的测量值，且具有较强的抗噪声能力；(4)提出一种新的代理函数，代入本文框架计算可获得性能提升。
论文组织如下：第2节基于代理函数和先验概率密度分析了SL0与FOCUSS，指出二者是L0范数平滑逼近的不同途径；第3节对L0范数逼近过程中目标函数的凹凸特性进行了分析，并据此提出改进算法；第4节基于牛顿方向推导了L0范数逼近的迭代求解算法，并且给出了一种新的代理函数；第5节说明了所提算法的收敛性与复杂度；第6节和第7节分别是数值仿真与总结展望。
2 L0范数的平滑逼近与正则化表达
2.1 基于代理函数的逼近
在SL0中，每个定义代理逼近函数为
足够小时，，实现了对的逼近。
除SL0外，文献[17]提出近似p范数，所使用的代理函数为
同样当与参数p足够小时，得到L0范数的平滑逼近。
2.2基于先验概率密度的逼近
考虑噪声时，压缩感知恢复问题转化为
其中是高斯噪声序列，且。使用贝叶斯准则，有
为正则化因子，用以调节恢复的误差和稀疏度。当服从高斯先验分布时，就得到岭回归问题(其中与的方差相关)。
岭回归无法得到稀疏解，可以构造一种迭代算法，令，并求解
此即正则化的FOCUSS算法，当，且算法收敛时，有。
2.3 使用代理函数的正则化表达
存在噪声时，恢复算法的目标函数均可以表示为2.2节的正则化形式，该式具有如下的性质：
其中是正则化项，对应稀疏约束。可以看出，正则化手段实现了更为广义的表达方式。
2.1节中分析了无噪情况下基于代理函数的优化目标，相应地，考虑噪声的情况下，该优化目标的正则化形式可写作式(3)所示的无约束函数：
其正则化项同2.1节，而非FOCUSS中的。
3 基于参数调整策略的改进算法
3.1目标函数的凹凸特性分析
命题1 任何平滑可微的单变量L0范数逼近代理函数，都是分段凹凸的。
证明 L0范数的定义为，要求，这意味着，且有，其中是一个随参数变化的较大值，可见，平滑可微的要求令有一个从0到非0，然后再接近0的过程，该过程中势必会出现拐点令，即该函数是分段凹凸的。 证毕
以SL0的高斯函数为例，在区间，目标函数是凸的。对于近似p范数，在区间
目标函数是凸的。
图1以SL0的高斯函数为例，揭示了取不同值时的局部解特性(归一化)。其中 ，高斯随机矩阵 ，假设，则表示反问题的解，表示尺度因子变量。
从图1中可以观察出，当时目标函数为凸函数，类似L2范数，所以不存在局部解，但是目标函数的最小值并没有对应最稀疏解处。当时，目标函数呈现凹性，局部解出现，最优解仍不在处。直到时，目标函数最小值才对应于最稀疏解，但此时局部解也最多。
若将目标函数换为FOCUSS对应的，也有类似图1的结果。无论哪种逼近方法，都存在陷入局部解的风险，为此必须寻求合适的策略避免提早收敛。
3.2改进策略
(1)对基于代理函数的算法，假设需更新的参数为(若以近似p范数为代理函数，p也可使用类似更新方法)，使用来更新，有，且。
(2)对基于先验概率密度的算法，也使用的方法更新参数，其物理意义是通过平滑调整不同分量的先验高斯分布的方差，获得稀疏解。事实上，经典FOCUSS算法对应于固定的，如果引入更新过程，获得了“变范数FOCUSS”，在不增加运算量的同时，求解更为稳健。
4 基于牛顿方向的求解框架及算法
4.1基于牛顿方向的算法框架
本部分基于2.3节的正则化表达实现。将式(3) 两边同时除以(不影响其解特性)，令，并分别对求一阶和二阶梯度。
则的牛顿方向可以表示为
其中，因为未必正定，所以无法直接使用牛顿法求解，为此，将该问题考虑为一个CCCP(ConCave-Convex Procedure)过程，转化为如下形式：
其中，而表示的正定部分。进一步推导有
其中且可以表示为
将式(5)代入式(4)即可得到
当算法达到收敛时，牛顿方向，即
或者有。
4.2一阶迭代求解算法IRSL0_1
时，相当于，求解得到
式(7)两边均有，无法直接求解，可令
则得到迭代重加权形式的求解算法IRSL0_1
此处为便于表达，记作了。与FOCUSS等算法不同之处在于，IRSL0_1的第k次反馈权值不仅依赖，同时还依赖。若使用近似Lp函数，则还需要更新。
4.3二阶迭代求解算法IRSL0_2
在式(6)两边右乘，同时考虑到所有的解均应位于内，于是有
其中，为表达方便，下面记作。与4.2节类似，式(8)隐含着一种迭代重加权算法。
可以看出，IRSL0_2算法需要计算代理逼近函数的Hess矩阵，并用其正定部分构成反馈权值矩阵，且同步更新平滑参数与。限于篇幅，4.2节并未给出常用代理函数的一阶梯度。在此给出文献中几种代理函数的IRSL0_2反馈权值矩阵。
(1)高斯函数[2]：
(2)双曲正切函数[11]：
其中，且有
(3)反正切函数[10]：
(4)近似Lp函数[17]：
在迭代过程中更新和两个参数。
(5)高斯和函数：
受部分响应波形构造的启发，设计平移相加的高斯函数来抵消波形的旁瓣起伏，达到减小凹区间影响的目的。单变量高斯和函数的表达式为：
该函数的Hess矩阵正定部分构成的权值矩阵为
5 对算法的说明
5.1复杂度
(1)改进的SL0复杂度是T的线性函数，T表示SL0算法的参数空间维数。(2)对变范数FOCUSS，若总的迭代次数不变，则复杂度不变，每次迭代复杂度约为。(3)IRSL0_2仅使用正定部分，而IRSL0_1使用了的全部分量，后者复杂度较大，且和使用函数有关，实验结论见6.4节。
5.2参数设定与收敛性
参数和信噪比SNR有密切的关系[16]，为此，假设SNR(dB) 已知，使用来计
算。对于IRSL0_1，其收敛性的证明可以参考文献[19]的收敛性研究方法，只需要将正则化部分替换为SL0的代理函数即可。对于IRSL0_2，因为此时将其考虑为一个CCCP过程，其收敛性已有结论。
6 数值仿真与稳健性说明
如无特别说明，仿真条件设定如下：, ，信号稀疏度，产生随机支撑的信号。运行平台为ThinkPad T420笔记本，Winxp系统，2G内存，仿真软件为MatlabR2011a。恢复成功是指。每种算法均仿真200次，求其平均恢复成功率，算法停止规则为到达最小参数值即停止。
6.1平滑逼近效果度量
图2给出了使用参数调整策略后算法性能提升效果，可以看出，增大参数维度，即经过平滑处理后，SL0和变范数FOCUSS算法(对每个p固定迭代向下取整的60/T次)均获得了明显的性能提升。其中SL0的, FOCUSS的。信噪比定义为
图2同时给出了IRSL0_1和IRSL0_2在不同信噪比下的恢复概率。为公平起见，和SL0一样，此二者也使用高斯代理函数，且使用最大的参数维度。结论是，本文所提出的迭代算法虽然复杂度有所提升，但在恢复性能上明显要优于平滑后SL0和变范数FOCUSS。
6.2 使用不同代理函数的IRSL0算法
本实验的目的是为了揭示不同代理函数对本文所提出算法的性能影响。图3给出的是本文所提出算法分别使用反正切函数(arctan)，高斯函数(gauss)，双曲正切函数(tangent)以及高斯和函数(sumgauss)和近似p范数(alp)情况下的恢复概率。从仿真结果看，反正切函数和本文所提出的高斯和函数表现最佳，其
他函数表现稍差。对IRSL0_2也有类似结论，限于篇幅，其仿真结果未给出。
为解释图3中各函数仿真结果的差异，图4给出了时的4类函数二阶导数。
观察图4，得到的结论是，对于本文所提出的算法，应尽量选择“凹度”较小，即二阶导数负区间中函数绝对值较小的代理函数。
6.3稀疏度的影响
已经知道，局部解的数目和信号的稀疏度K密切相关[16]，K值越大，就会出现越多的局部解，为了研究K值对算法性能的影响，设定SNR=100 dB，在这种近似无噪的条件下仿真了3种算法使用本文提出的高斯和函数时的恢复概率，如图5所示。
从图5中可以看出，当K<15时，IRSL0_1和IRSL0_2可以完全恢复信号，但SL0不能。整体上看，本文算法有能力处理更为“稠密”的信号，而且IRSL0_1略有优势。
6.4运算时间
仿真条件为，，信号稀疏度, ，每种算法运行100次，记录其累计运行时间(其中包括产生随机稀疏信号的运算时间)。结果如表1所示。结合前面仿真结果，本文所提出的高斯和函数与反正切函数在IRSL0_2中恢复概率高且运算量适当，具有实用价值。
6.5 关于稳健性的说明
数值仿真证实，本文工作提高了L0范数平滑逼近的稳健性，这种性能增益的获得，本质上来自3个方面：(1)对2.1节和2.2节的两种逼近方式，设计了参数平滑改进策略，使用平滑参数的算法可以有效避免提前陷入局部解的风险，性能提升效果见6.1节仿真。(2)4.2节和4.3节所获得的两种迭代重加权运算框
架，具有较强的抗噪能力，且在相同稀疏度下，需要较少的测量值，性能远优于原始SL0类算法，见6.1节和6.3节仿真。(3)所设计的代理函数，其凹凸特性优良，且运算量适当，尤其适合于本文所提出的迭代重加权框架，实用性强于其它函数，见6.2节和6.4节仿真。
7 结束语
本文将L0范数平滑逼近问题划分为基于代理函数和基于先验概率密度两类，分别对其目标函数的凹凸特性进行分析，以此为基础提出了基于参数调整策略的改进算法，仿真表明改进策略可明显提升恢复能力。另一个贡献在于，基于牛顿方向推导了一个运算框架，形成两种迭代重加权形式的恢复算法，见诸文献的代理函数均可代入本文的框架进行运算。数值运算证实，本文算法虽然运算量有所提高，但抗噪声性能明显高于SL0，具有很好的应用潜力。事实上，如果将高斯代理函数代入本文的IRSL0_2，就得到了ISL0，所以本文工作是ISL0的广义形式。
此外，通过数值仿真，比较了不同代理函数对恢复性能的影响，本文所提出的高斯和函数表现优良。最后，给出了代理函数的初步选择准则，关于“好”的代理函数的设计准则与理论上深入的性能分析，有待进一步研究。
参考文献：
[1] Candès E J and Wakin M B. An introduction to compressive
sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 21-30.
[2] Mohimani H, Zadeh M, and Jutten C. A fast approach for
overcomplete sparse decomposition based on smoothed L0 norm[J].
IEEE Transactions on Signal Processing, 2009, 57(1): 289-301.
[3] Hyder M M and Mahata K. An improved smoothed L0 approximation
algorithm for sparse representation[J]. IEEE Transactions on Signal
Processing, 2010, 58(4): 2194-2205.
[4] Lv J, Huang L, Shi Y, et al.. Inverse synthetic aperture radar imaging
via modified smoothed L0 norm[J]. IEEE Antennas and Wireless
Propagation Letters, 2014, 13(7): 1235-1238.
[5] Liu Z, You P, Wei X, et al.. Dynamic ISAR imaging of maneuvering
targets based on sequential SL0[J]. IEEE Geoscience and Remote
Sensing Letters, 2013, 10(5): 1041-1045.
[6] Guo L and Wen X. SAR image compression and reconstruction based
on compressed sensing[J]. Journal of Information & Computational
Science, 2014, 11(2): 573-579.
[7] Liu Z, Wei X, and Li X. Aliasing-free micro-Doppler analysis based on
short-time compressed sensing[J]. IET Signal Processing, 2013, 8(2):
176-187.
[8] Liu T and Zhou J. Improved smoothed L0 reconstruction algorithm
for ISI sparse channel estimation[J]. The Journal of China Universities of
Posts and Telecommunications, 2014, 21(2): 40-47.
[9] Ye X and Zhu W. Sparse channel estimation of pulse-shaping
multiple-input-multiple-output
multiplexing systems with
orthogonal
an
frequency
gradient
division
L2-SL0 approximate
reconstruction algorithm[J]. IET Communications, 2014, 8(7): 1124-1131.
[10] 王军华, 黄知涛, 周一宇, 等. 基于近似L0 范数的稳健稀疏重构算法[J]. 电子学报, 2012, 40(6): 1185-1189.
Wang Jun-hua, Huang Zhi-tao, Zhou Yi-yu, et al.. Robust sparse
recovery based on approximate L0 norm[J]. Acta Electronica Sinica, 2012,
40(6): 1185-1189.
[11] 赵瑞珍, 林婉娟, 李浩, 等. 基于光滑L0范数和修正牛顿法的压缩感知重建算法[J]. 计算机辅助设计与图形学学报, 2012, 24(4): 478-484.
Zhao Rui-zhen, Lin Wan-juan, Li Hao, et al.. Reconstruction algorithm for
compressive sensing based on smoothed L0 norm and revised newton
method[J]. Journal of Computer- Aided Design & Computer Graphic,
2012, 24(4): 478-484.
[12] 杨良龙, 赵生妹, 郑宝玉, 等. 基于SL0 压缩感知信号重建的改进算法[J]. 信号处理, 2012, 28(6): 834-841.
Yang Liang-long, Zhao Sheng-mei, Zheng Bao-yu, et al.. The improved
reconstruction algorithm for compressive sensing on SL0[J]. Signal
Processing, 2012, 28(6): 834-841.
[13] 余付平, 沈堤. 基于拟牛顿方向的改进平滑L0 算法[J]. 计算机工程与应用,
2013, 49(22): 215-218.
Yu Fu-ping and Shen Di. Improved smoothed L0 approximation
algorithm based on Quasi-Newton direction[J]. Computer Engineering
and Applications, 2013, 49(22): 215-218.
[14] 贺亚鹏, 庄珊娜, 张燕洪, 等. 一种基于交叉验证的稳健SL0目标参数提取算
法[J]. 系统工程与电子技术, 2012, 34(1): 64-68.
He Ya-peng, Zhuang Shan-na, Zhang Yan-hong, et al.. Cross validation
based robust-SL0 algorithm for target parameter extraction[J]. Systems
Engineering and Electronics, 2012, 34(1): 64-68.
[15] 邱伟, 赵宏钟, 陈建军, 等. 基于平滑L0 范数的高分辨雷达一维成像研究[J].
电子与信息学报, 2011, 33(12): 2869-2874.
Qiu Wei, Zhao Hong-zhong, Chen Jian-jun, et al.. High- resolution radar
one-dimensional imaging based on smoothed L0 norm[J]. Journal of
Electronics & Information Technology, 2011, 33(12): 2869-2874.
[16] Gorodnitsky I F and Rao B D. Sparse signal reconstruction from
limited data using FOCUSS: a reweighted minimum norm algorithm[J].
IEEE Transactions on Signal Processing, 1997, 45(3): 600-616.
[17] Pant J K, Lu W, and Antoniou A. New improved algorithms for
compressive sensing based on Lp norm[J]. IEEE Transactions on Circuits
and Systems-II: Express Briefs, 2014, 61(3): 198-202.
[18] Yuille A L and Rangarajan A. The concave-convex procedure [J].
Neural Computer, 2003, 15(4): 915-936.
[19] Rao B D, Engan K, Cotter S F, et al.. Subset selection in noise based
on diversity measure minimization[J]. IEEE Transactions on Signal
Processing, 2003, 51(3): 760-770.
网络出版：2015-07-06
基金项目：国家自然科学基金(61379104)和陕西省自然科学基金(2014JM2-
6106)
2024年3月8日发(作者：德念柏)
L0范数平滑逼近的稳健求解算法王 峰*①② 向 新② 易克初① 熊 磊②
【摘 要】该文研究基于代理函数和先验概率密度的L0范数平滑逼近问题的稳健求解。首先，分析了平滑逼近函数的凹凸特性，给出提高恢复性能的参数调整策略与改进的SL0和FOCUSS算法。其次，将噪声背景下L0范数逼近过程进行正则化表示，并基于牛顿方向推导其迭代重加权形式的求解框架，给出一种新的代理函数。最后，使用数值仿真证实了所提算法可以提高此类问题的求解的稳健性，具有实用价值。
【期刊名称】电子与信息学报
【年(卷),期】2015(000)010
【总页数】6
【关键词】非凸压缩感知；L0范数平滑逼近；迭代重加权算法
1 引言
压缩感知[1]恢复算法，其核心是求解问题，其中,, 是一个满足RIP(Restricted
Isometry Property)准则的测量矩阵。因为L0范数最小化是N-P难的，所以发展出了贪婪算法、凸松弛算法(使用L1范数替代L0)、贝叶斯压缩感知等恢复方法。
除上述算法外，研究者还考虑使用代理函数来实现对L0范数的逼近，典型代表有SL0和ISL0等[2,3]。此处的代理函数，是指某一类参数化平滑可微的连续函数，通过调整其参数，可以逼近，从而使得这一N-P难问题变得可以规划求解。SL0算法提出后引起广泛关注，文献[4]设计了改进的SL0，并将其应用于ISAR(Inverse Synthetic Aperture Radar)成像。文献[5]发展了序贯SL0，用
以对机动目标进行ISAR成像。文献[6]开展了类似工作，使用SL0进行SAR图像重建。文献[7]基于SL0设计短时压缩感知，并用于微多普勒分析。文献[8,9]将SL0拓展至通信领域，用于稀疏信道估计与均衡。国内学者对L0范数逼近算法的研究，多以SL0算法框架为基础，使用新的代理函数和新的计算方向。应用方面，文献[15]将SL0应用于高分辨雷达1维成像，取得良好效果。
仿真表明，虽然计算效率较高，但SL0算法的性能并不占优势，尤其在引入噪声后，需要寻求更为稳健的求解方法。而且，目前尚未在SL0类算法和其他主流算法之间建立关联，其研究有待深化。
本文开展了如下工作：(1)分析了L0范数平滑逼近过程中目标函数的凹凸特性；(2)梳理了SL0类算法，FOCUSS[16]算法以及最近提出的[17]之间的内在关联，并给出改进算法，新算法在逼近过程中可避开一部分局部解，降低了提前收敛在非全局最优解上的风险；(3)基于牛顿方向和CCCP (ConCave-Convex
Procedure)[18]推导了一种迭代重加权恢复算法框架，对相同稀疏度的信号，同样的恢复效果下，需要较少的测量值，且具有较强的抗噪声能力；(4)提出一种新的代理函数，代入本文框架计算可获得性能提升。
论文组织如下：第2节基于代理函数和先验概率密度分析了SL0与FOCUSS，指出二者是L0范数平滑逼近的不同途径；第3节对L0范数逼近过程中目标函数的凹凸特性进行了分析，并据此提出改进算法；第4节基于牛顿方向推导了L0范数逼近的迭代求解算法，并且给出了一种新的代理函数；第5节说明了所提算法的收敛性与复杂度；第6节和第7节分别是数值仿真与总结展望。
2 L0范数的平滑逼近与正则化表达
2.1 基于代理函数的逼近
在SL0中，每个定义代理逼近函数为
足够小时，，实现了对的逼近。
除SL0外，文献[17]提出近似p范数，所使用的代理函数为
同样当与参数p足够小时，得到L0范数的平滑逼近。
2.2基于先验概率密度的逼近
考虑噪声时，压缩感知恢复问题转化为
其中是高斯噪声序列，且。使用贝叶斯准则，有
为正则化因子，用以调节恢复的误差和稀疏度。当服从高斯先验分布时，就得到岭回归问题(其中与的方差相关)。
岭回归无法得到稀疏解，可以构造一种迭代算法，令，并求解
此即正则化的FOCUSS算法，当，且算法收敛时，有。
2.3 使用代理函数的正则化表达
存在噪声时，恢复算法的目标函数均可以表示为2.2节的正则化形式，该式具有如下的性质：
其中是正则化项，对应稀疏约束。可以看出，正则化手段实现了更为广义的表达方式。
2.1节中分析了无噪情况下基于代理函数的优化目标，相应地，考虑噪声的情况下，该优化目标的正则化形式可写作式(3)所示的无约束函数：
其正则化项同2.1节，而非FOCUSS中的。
3 基于参数调整策略的改进算法
3.1目标函数的凹凸特性分析
命题1 任何平滑可微的单变量L0范数逼近代理函数，都是分段凹凸的。
证明 L0范数的定义为，要求，这意味着，且有，其中是一个随参数变化的较大值，可见，平滑可微的要求令有一个从0到非0，然后再接近0的过程，该过程中势必会出现拐点令，即该函数是分段凹凸的。 证毕
以SL0的高斯函数为例，在区间，目标函数是凸的。对于近似p范数，在区间
目标函数是凸的。
图1以SL0的高斯函数为例，揭示了取不同值时的局部解特性(归一化)。其中 ，高斯随机矩阵 ，假设，则表示反问题的解，表示尺度因子变量。
从图1中可以观察出，当时目标函数为凸函数，类似L2范数，所以不存在局部解，但是目标函数的最小值并没有对应最稀疏解处。当时，目标函数呈现凹性，局部解出现，最优解仍不在处。直到时，目标函数最小值才对应于最稀疏解，但此时局部解也最多。
若将目标函数换为FOCUSS对应的，也有类似图1的结果。无论哪种逼近方法，都存在陷入局部解的风险，为此必须寻求合适的策略避免提早收敛。
3.2改进策略
(1)对基于代理函数的算法，假设需更新的参数为(若以近似p范数为代理函数，p也可使用类似更新方法)，使用来更新，有，且。
(2)对基于先验概率密度的算法，也使用的方法更新参数，其物理意义是通过平滑调整不同分量的先验高斯分布的方差，获得稀疏解。事实上，经典FOCUSS算法对应于固定的，如果引入更新过程，获得了“变范数FOCUSS”，在不增加运算量的同时，求解更为稳健。
4 基于牛顿方向的求解框架及算法
4.1基于牛顿方向的算法框架
本部分基于2.3节的正则化表达实现。将式(3) 两边同时除以(不影响其解特性)，令，并分别对求一阶和二阶梯度。
则的牛顿方向可以表示为
其中，因为未必正定，所以无法直接使用牛顿法求解，为此，将该问题考虑为一个CCCP(ConCave-Convex Procedure)过程，转化为如下形式：
其中，而表示的正定部分。进一步推导有
其中且可以表示为
将式(5)代入式(4)即可得到
当算法达到收敛时，牛顿方向，即
或者有。
4.2一阶迭代求解算法IRSL0_1
时，相当于，求解得到
式(7)两边均有，无法直接求解，可令
则得到迭代重加权形式的求解算法IRSL0_1
此处为便于表达，记作了。与FOCUSS等算法不同之处在于，IRSL0_1的第k次反馈权值不仅依赖，同时还依赖。若使用近似Lp函数，则还需要更新。
4.3二阶迭代求解算法IRSL0_2
在式(6)两边右乘，同时考虑到所有的解均应位于内，于是有
其中，为表达方便，下面记作。与4.2节类似，式(8)隐含着一种迭代重加权算法。
可以看出，IRSL0_2算法需要计算代理逼近函数的Hess矩阵，并用其正定部分构成反馈权值矩阵，且同步更新平滑参数与。限于篇幅，4.2节并未给出常用代理函数的一阶梯度。在此给出文献中几种代理函数的IRSL0_2反馈权值矩阵。
(1)高斯函数[2]：
(2)双曲正切函数[11]：
其中，且有
(3)反正切函数[10]：
(4)近似Lp函数[17]：
在迭代过程中更新和两个参数。
(5)高斯和函数：
受部分响应波形构造的启发，设计平移相加的高斯函数来抵消波形的旁瓣起伏，达到减小凹区间影响的目的。单变量高斯和函数的表达式为：
该函数的Hess矩阵正定部分构成的权值矩阵为
5 对算法的说明
5.1复杂度
(1)改进的SL0复杂度是T的线性函数，T表示SL0算法的参数空间维数。(2)对变范数FOCUSS，若总的迭代次数不变，则复杂度不变，每次迭代复杂度约为。(3)IRSL0_2仅使用正定部分，而IRSL0_1使用了的全部分量，后者复杂度较大，且和使用函数有关，实验结论见6.4节。
5.2参数设定与收敛性
参数和信噪比SNR有密切的关系[16]，为此，假设SNR(dB) 已知，使用来计
算。对于IRSL0_1，其收敛性的证明可以参考文献[19]的收敛性研究方法，只需要将正则化部分替换为SL0的代理函数即可。对于IRSL0_2，因为此时将其考虑为一个CCCP过程，其收敛性已有结论。
6 数值仿真与稳健性说明
如无特别说明，仿真条件设定如下：, ，信号稀疏度，产生随机支撑的信号。运行平台为ThinkPad T420笔记本，Winxp系统，2G内存，仿真软件为MatlabR2011a。恢复成功是指。每种算法均仿真200次，求其平均恢复成功率，算法停止规则为到达最小参数值即停止。
6.1平滑逼近效果度量
图2给出了使用参数调整策略后算法性能提升效果，可以看出，增大参数维度，即经过平滑处理后，SL0和变范数FOCUSS算法(对每个p固定迭代向下取整的60/T次)均获得了明显的性能提升。其中SL0的, FOCUSS的。信噪比定义为
图2同时给出了IRSL0_1和IRSL0_2在不同信噪比下的恢复概率。为公平起见，和SL0一样，此二者也使用高斯代理函数，且使用最大的参数维度。结论是，本文所提出的迭代算法虽然复杂度有所提升，但在恢复性能上明显要优于平滑后SL0和变范数FOCUSS。
6.2 使用不同代理函数的IRSL0算法
本实验的目的是为了揭示不同代理函数对本文所提出算法的性能影响。图3给出的是本文所提出算法分别使用反正切函数(arctan)，高斯函数(gauss)，双曲正切函数(tangent)以及高斯和函数(sumgauss)和近似p范数(alp)情况下的恢复概率。从仿真结果看，反正切函数和本文所提出的高斯和函数表现最佳，其
他函数表现稍差。对IRSL0_2也有类似结论，限于篇幅，其仿真结果未给出。
为解释图3中各函数仿真结果的差异，图4给出了时的4类函数二阶导数。
观察图4，得到的结论是，对于本文所提出的算法，应尽量选择“凹度”较小，即二阶导数负区间中函数绝对值较小的代理函数。
6.3稀疏度的影响
已经知道，局部解的数目和信号的稀疏度K密切相关[16]，K值越大，就会出现越多的局部解，为了研究K值对算法性能的影响，设定SNR=100 dB，在这种近似无噪的条件下仿真了3种算法使用本文提出的高斯和函数时的恢复概率，如图5所示。
从图5中可以看出，当K<15时，IRSL0_1和IRSL0_2可以完全恢复信号，但SL0不能。整体上看，本文算法有能力处理更为“稠密”的信号，而且IRSL0_1略有优势。
6.4运算时间
仿真条件为，，信号稀疏度, ，每种算法运行100次，记录其累计运行时间(其中包括产生随机稀疏信号的运算时间)。结果如表1所示。结合前面仿真结果，本文所提出的高斯和函数与反正切函数在IRSL0_2中恢复概率高且运算量适当，具有实用价值。
6.5 关于稳健性的说明
数值仿真证实，本文工作提高了L0范数平滑逼近的稳健性，这种性能增益的获得，本质上来自3个方面：(1)对2.1节和2.2节的两种逼近方式，设计了参数平滑改进策略，使用平滑参数的算法可以有效避免提前陷入局部解的风险，性能提升效果见6.1节仿真。(2)4.2节和4.3节所获得的两种迭代重加权运算框
架，具有较强的抗噪能力，且在相同稀疏度下，需要较少的测量值，性能远优于原始SL0类算法，见6.1节和6.3节仿真。(3)所设计的代理函数，其凹凸特性优良，且运算量适当，尤其适合于本文所提出的迭代重加权框架，实用性强于其它函数，见6.2节和6.4节仿真。
7 结束语
本文将L0范数平滑逼近问题划分为基于代理函数和基于先验概率密度两类，分别对其目标函数的凹凸特性进行分析，以此为基础提出了基于参数调整策略的改进算法，仿真表明改进策略可明显提升恢复能力。另一个贡献在于，基于牛顿方向推导了一个运算框架，形成两种迭代重加权形式的恢复算法，见诸文献的代理函数均可代入本文的框架进行运算。数值运算证实，本文算法虽然运算量有所提高，但抗噪声性能明显高于SL0，具有很好的应用潜力。事实上，如果将高斯代理函数代入本文的IRSL0_2，就得到了ISL0，所以本文工作是ISL0的广义形式。
此外，通过数值仿真，比较了不同代理函数对恢复性能的影响，本文所提出的高斯和函数表现优良。最后，给出了代理函数的初步选择准则，关于“好”的代理函数的设计准则与理论上深入的性能分析，有待进一步研究。
参考文献：
[1] Candès E J and Wakin M B. An introduction to compressive
sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 21-30.
[2] Mohimani H, Zadeh M, and Jutten C. A fast approach for
overcomplete sparse decomposition based on smoothed L0 norm[J].
IEEE Transactions on Signal Processing, 2009, 57(1): 289-301.
[3] Hyder M M and Mahata K. An improved smoothed L0 approximation
algorithm for sparse representation[J]. IEEE Transactions on Signal
Processing, 2010, 58(4): 2194-2205.
[4] Lv J, Huang L, Shi Y, et al.. Inverse synthetic aperture radar imaging
via modified smoothed L0 norm[J]. IEEE Antennas and Wireless
Propagation Letters, 2014, 13(7): 1235-1238.
[5] Liu Z, You P, Wei X, et al.. Dynamic ISAR imaging of maneuvering
targets based on sequential SL0[J]. IEEE Geoscience and Remote
Sensing Letters, 2013, 10(5): 1041-1045.
[6] Guo L and Wen X. SAR image compression and reconstruction based
on compressed sensing[J]. Journal of Information & Computational
Science, 2014, 11(2): 573-579.
[7] Liu Z, Wei X, and Li X. Aliasing-free micro-Doppler analysis based on
short-time compressed sensing[J]. IET Signal Processing, 2013, 8(2):
176-187.
[8] Liu T and Zhou J. Improved smoothed L0 reconstruction algorithm
for ISI sparse channel estimation[J]. The Journal of China Universities of
Posts and Telecommunications, 2014, 21(2): 40-47.
[9] Ye X and Zhu W. Sparse channel estimation of pulse-shaping
multiple-input-multiple-output
multiplexing systems with
orthogonal
an
frequency
gradient
division
L2-SL0 approximate
reconstruction algorithm[J]. IET Communications, 2014, 8(7): 1124-1131.
[10] 王军华, 黄知涛, 周一宇, 等. 基于近似L0 范数的稳健稀疏重构算法[J]. 电子学报, 2012, 40(6): 1185-1189.
Wang Jun-hua, Huang Zhi-tao, Zhou Yi-yu, et al.. Robust sparse
recovery based on approximate L0 norm[J]. Acta Electronica Sinica, 2012,
40(6): 1185-1189.
[11] 赵瑞珍, 林婉娟, 李浩, 等. 基于光滑L0范数和修正牛顿法的压缩感知重建算法[J]. 计算机辅助设计与图形学学报, 2012, 24(4): 478-484.
Zhao Rui-zhen, Lin Wan-juan, Li Hao, et al.. Reconstruction algorithm for
compressive sensing based on smoothed L0 norm and revised newton
method[J]. Journal of Computer- Aided Design & Computer Graphic,
2012, 24(4): 478-484.
[12] 杨良龙, 赵生妹, 郑宝玉, 等. 基于SL0 压缩感知信号重建的改进算法[J]. 信号处理, 2012, 28(6): 834-841.
Yang Liang-long, Zhao Sheng-mei, Zheng Bao-yu, et al.. The improved
reconstruction algorithm for compressive sensing on SL0[J]. Signal
Processing, 2012, 28(6): 834-841.
[13] 余付平, 沈堤. 基于拟牛顿方向的改进平滑L0 算法[J]. 计算机工程与应用,
2013, 49(22): 215-218.
Yu Fu-ping and Shen Di. Improved smoothed L0 approximation
algorithm based on Quasi-Newton direction[J]. Computer Engineering
and Applications, 2013, 49(22): 215-218.
[14] 贺亚鹏, 庄珊娜, 张燕洪, 等. 一种基于交叉验证的稳健SL0目标参数提取算
法[J]. 系统工程与电子技术, 2012, 34(1): 64-68.
He Ya-peng, Zhuang Shan-na, Zhang Yan-hong, et al.. Cross validation
based robust-SL0 algorithm for target parameter extraction[J]. Systems
Engineering and Electronics, 2012, 34(1): 64-68.
[15] 邱伟, 赵宏钟, 陈建军, 等. 基于平滑L0 范数的高分辨雷达一维成像研究[J].
电子与信息学报, 2011, 33(12): 2869-2874.
Qiu Wei, Zhao Hong-zhong, Chen Jian-jun, et al.. High- resolution radar
one-dimensional imaging based on smoothed L0 norm[J]. Journal of
Electronics & Information Technology, 2011, 33(12): 2869-2874.
[16] Gorodnitsky I F and Rao B D. Sparse signal reconstruction from
limited data using FOCUSS: a reweighted minimum norm algorithm[J].
IEEE Transactions on Signal Processing, 1997, 45(3): 600-616.
[17] Pant J K, Lu W, and Antoniou A. New improved algorithms for
compressive sensing based on Lp norm[J]. IEEE Transactions on Circuits
and Systems-II: Express Briefs, 2014, 61(3): 198-202.
[18] Yuille A L and Rangarajan A. The concave-convex procedure [J].
Neural Computer, 2003, 15(4): 915-936.
[19] Rao B D, Engan K, Cotter S F, et al.. Subset selection in noise based
on diversity measure minimization[J]. IEEE Transactions on Signal
Processing, 2003, 51(3): 760-770.
网络出版：2015-07-06
基金项目：国家自然科学基金(61379104)和陕西省自然科学基金(2014JM2-
6106)