基于压缩感知的加速前向后向匹配追踪算法
第38卷第10期电子与信息学报 Vol.38No.10 2016年10月Journal of Electronics & Information Technology Oct. 2016
基于压缩感知的加速前向后向匹配追踪算法
王锋①孙桂玲*①张健平②何静飞①
①(南开大学电子信息与光学工程学院天津300350)
②(上海交通大学电子信息与电气工程学院上海 200030)
摘要：前向后向匹配追踪(FBP)算法作为一个新颖的两阶段贪婪逼近算法，因为较高的重构精度和不需要稀疏度作为先验信息的特点，受到了人们的广泛关注。然而，FBP算法必须运行更多的时间才能得到更高的精度。鉴于此，该文提出加速前向后向匹配追踪(AFBP)算法。该算法利用每次迭代中候选支撑集的信息，实现对已删除原子的再次加入，以此减少算法迭代次数。通过不同非零项分布的稀疏信号和稀疏图像的仿真结果表明，相对于FBP 算法，该文提出的方案在不降低重构精度的同时，大幅降低了算法运行时间。
关键词：压缩感知；贪婪算法；前向后向搜索；稀疏信号重构
中图分类号：TN911.72 文献标识码：A 文章编号：1009-5896(2016)10-2538-08 DOI: 10.11999/JEIT151422
Acceleration Forward-backward Pursuit Algorithm
Based on Compressed Sensing
WANG Feng① SUN Guiling① ZHANG Jianping② HE Jingfei①
①(College of Electronic Information and Optical Engineering, Nankai University, Tianjin 300350, China)
②(School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200030, China)
Abstract: The Forward-Backward Pursuit (FBP) algorithm, a novel two stage greedy approach, receives wide attention due to the high reconstruction accuracy and the feature without prior information of the sparsity.
However, FBP has to run more time to get a higher precision. To alleviate this drawback, this paper proposes the Acceleration Forward-Backward Pursuit (AFBP) algorithm based on Compressed Sensing (CS). In order to reduce the number of iterations, the algorithm exploits the information available in the support estimate to add the deleted atoms again. The run time of AFBP is sharply shorter than that of FBP, while the precision of AFBP is not lower than FBP. The efficacy of the proposed scheme is demonstrated by simulations using random sparse signals with different nonzero coefficient distributions and a sparse image.
Key words: Compressed Sensing (CS); Greedy algorithms; Forward-backward search; Sparse signal reconstruction
1引言
压缩感知(Compressed Sensing, CS)[1, 2]将稀疏信号的采样和压缩进行结合，从而降低测量系统的采样率和计算复杂度。这一特性使得压缩感知在无线传感器网络[3]、核磁共振成像等领域[4, 5]有广泛应用前景。压缩感知重构算法可以分为3大类：贪婪算法，凸松弛算法和贝叶斯框架。其中，贪婪算法因为有较快的速度和简单的框架而被广泛应用。贪婪算法主要包括匹配追踪(MP)算法[6]，正交匹配追踪(OMP)算法[7]，分段正交匹配追踪(StOMP)算
收稿日期：2015-12-14；改回日期：2016-05-05；网络出版：2016-07-04 *通信作者孙桂玲sungl@https://www.wendangku.net/doc/8f9036562.html,
基金项目：国家自然科学基金(61171140)，高等学校博士学科点专项科研基金(20130031110032)
Foundation Items: The National Natural Science Foundation of China (61171140), The Doctoral Program of Higher Education (20130031110032)法[8]，子空间追踪(SP)算法[9]，压缩采样匹配追踪(CoSaMP)算法[10]，稀疏度自适应匹配追踪(SAMP)算法[11]，前向预测正交匹配追踪(LAOMP)算法[12]和前向后向匹配追踪(Forward-Backward Pursuit, FBP)算法[13]。为了进一步提高算法性能，许多迭代[14]和融合[1517]
的改进策略被应用于这些贪婪算法。
由于OMP算法没有回溯机制，而SP算法又需要稀疏度作为先验信息，文献[13]提出了FBP算法。在FBP算法中，每一步迭代主要包含两个阶段：前向阶段和后向阶段。前向阶段通过前向步长 扩大估计支撑集，后向阶段通过后向步长 减小估计支撑集。本文提出的加速前向后向匹配追踪(Acceleration Forward-Backward Pursuit, AFBP)算法，克服了FBP算法每次迭代只能以固定步长扩大支撑集、忽视被删除原子质量的缺点，利用前向阶段支撑集中原子的信息，对后向阶段被删除原子
万方数据