基于压缩感知的加速前向后向匹配追踪算法

王锋; 孙桂玲; 张健平; 何静飞

doi:10.11999/JEIT151422

基于压缩感知的加速前向后向匹配追踪算法

doi: 10.11999/JEIT151422

1.
(南开大学电子信息与光学工程学院天津 300350) ②(上海交通大学电子信息与电气工程学院上海 200030)

基金项目:

国家自然科学基金(61171140)，高等学校博士学科点专项科研基金(20130031110032)

计量
- 文章访问数: 1587
- HTML全文浏览量: 117
- PDF下载量: 528
- 被引次数: 0
出版历程
- 收稿日期: 2015-12-14
- 修回日期: 2016-05-05
- 刊出日期: 2016-10-19

Acceleration Forward-backward Pursuit Algorithm Based on Compressed Sensing

1.
(College of Electronic Information and Optical Engineering, Nankai University, Tianjin 300350, China)
2.
(School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200030, China)

Funds:

The National Natural Science Foundation of China (61171140), The Doctoral Program of Higher Education (20130031110032)

摘要

摘要: 前向后向匹配追踪(FBP)算法作为一个新颖的两阶段贪婪逼近算法，因为较高的重构精度和不需要稀疏度作为先验信息的特点，受到了人们的广泛关注。然而，FBP算法必须运行更多的时间才能得到更高的精度。鉴于此，该文提出加速前向后向匹配追踪(AFBP)算法。该算法利用每次迭代中候选支撑集的信息，实现对已删除原子的再次加入，以此减少算法迭代次数。通过不同非零项分布的稀疏信号和稀疏图像的仿真结果表明，相对于FBP算法，该文提出的方案在不降低重构精度的同时，大幅降低了算法运行时间。
- 压缩感知 /
- 贪婪算法 /
- 前向后向搜索 /
- 稀疏信号重构
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.
- Compressed Sensing (CS) /
- Greedy algorithms /
- Forward-backward search /
- Sparse signal reconstruction

HTML全文

参考文献(19)

DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52 (4): 1289-1306. doi: 10.1109/TIT.2006.871582.

CANDS E J, ROMBERG J, and TAO T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509. doi: 10.1109/TIT.2005.862083.

李鹏,王建新,曹建农. 无线传感器网络中基于压缩感知和GM(1,1)的异常检测方案[J]. 电子与信息学报, 2015, 37(7): 1586-1590. doi: 10.11999/JEIT141219.

LI Peng, WANG Jianxin, and CAO Jiannong. Abnormal event detection scheme based on compressive sensing and GM (1,1) in wireless sensor networks[J]. Journal of Electronics Information Technology, 2015, 37(7): 1586-1590. doi: 10.11999/JEIT141219.

蒋明峰, 刘渊, 徐文龙, 等. 基于全变分扩展方法的压缩感知磁共振成像算法研究[J]. 电子与信息学报, 2015, 37(11): 2608-2612. doi: 10.11999/JEIT150179.

JIANG Mingfeng, LIU Yuan, XU Wenlong, et al. The study of compressed sensing MR image reconstruction algorithm based on the extension of total variation method[J]. Journal of Electronics Information Technology, 2015, 37(11): 2608-2612. doi: 10.11999/JEIT150179.

QU X, HOU Y, FAN L, et al. Magnetic resonance image reconstruction from undersampled measurements using a patch-based nonlocal operator[J]. Medical Image Analysis, 2014, 18(6): 843-856. doi: 10.1016/j.media.2013.09.007.

MALLAT S G and ZHANG Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1994, 41(12): 3397-3415. doi: 10.1109/78.258082.

TROPP J and GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666. doi: 10.1109/TIT.2007.909108.

DONOHO D L, TSAIG Y, DRORI I, et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2012, 58(2): 1094-1121. doi: 10.1109/ TIT.2011.2173241.

DAI W and MILENKOVIC O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249. doi: 10.1109/TIT.2009.2016006.

NEEDELL D and TROPP J A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2009, 26(3): 301-321. doi: 10.1016/j.acha.2008.07.002.

DO T T, GAN L, NGUYEN N, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]. 42nd IEEE Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2008: 581-587. doi: 10.1109/ACSSC.2008.5074472.

CHATTERJEE S, SUNDMAN D, and SKOGLUND M. Look ahead orthogonal matching pursuit[C]. 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, 2011: 4024-4027. doi: 10.1109/ICASSP.2011.5947235.

KARAHANOGLU N B and ERDOGAN H. Compressed sensing signal recovery via forward-backward pursuit[J]. Digital Signal Processing, 2013, 23(5): 1539-1548. doi: 10.1016/j.dsp.2013.05.007.

AMBAT S K and HARI K V S. An iterative framework for sparse signal reconstruction algorithms[J]. Signal Processing, 2015, 108: 351-364. doi: 10.1016/j.sigpro.2014.09.023.

AMBAT S K, CHATTERJEE S, and HARI K V S. Progressive fusion of reconstruction algorithms for low latency applications in compressed sensing[J]. Signal Processing, 2014, 97(7): 146-151. doi: 10.1016/j.sigpro.2013. 10.019.

AMBAT S K, CHATTERJEE S, and HARI K V S. A committee machine approach for compressed sensing signal reconstruction[J]. IEEE Transactions on Signal Processing, 2014, 62(7): 1705-1717. doi: 10.1109/TSP.2014.2303941.

DEEPA K G, AMBAT S K, and HARI K V S. Modified greedy pursuits for improving sparse recovery[C]. Twentieth IEEE National Conference on Communications (NCC), Kanpur, 2014: 1-5. doi: 10.1109/NCC.2014.6811370.

施引文献

资源附件(0)

访问统计