多路径支撑集回溯贪婪重构算法

doi:10.12305/j.issn.1001-506X.2024.10.05

系统工程与电子技术 ›› 2024, Vol. 46 ›› Issue (10): 3279-3284.doi: 10.12305/j.issn.1001-506X.2024.10.05

• 电子技术 • 上一篇

多路径支撑集回溯贪婪重构算法

田文飚¹^,²^,*, 芮国胜², 张嵩², 张海波², 王林²

1. 海军航空大学航空作战勤务学院, 山东烟台 264001
2. 海军航空大学信号与信息处理山东省重点实验室, 山东烟台 264001

收稿日期:2023-02-18 出版日期:2024-09-25 发布日期:2024-10-22
通讯作者: 田文飚
作者简介:田文飚(1987—), 男, 副教授, 博士, 主要研究方向为压缩感知、通信信号处理
芮国胜(1968—), 男, 教授, 博士研究生导师, 博士, 主要研究方向为压缩感知、现代滤波理论、微弱信号检测
张嵩(1979—), 男, 副教授, 博士, 主要研究方向为微弱信号检测、航空通信技术
张海波(1983—), 男, 副教授, 博士, 主要研究方向为多输入多输出通信、航空电子技术
王林(1985—), 男, 讲师, 博士, 主要研究方向为航空通信技术
基金资助:
国家自然科学基金(41606117);国家自然科学基金(41476089);国家自然科学基金(61671016)

Multipath backtracking greedy pursuit algorithm

Wenbiao TIAN¹^,²^,*, Guosheng RUI², Song ZHANG², Haibo ZHANG², Lin WANG²

1. School of Aviation Operations and Support, Naval Aviation University, Yantai 264001, China
2. Signal and Information Processing Provincial Key Laboratory in Shandong, Naval Aviation University, Yantai 264001, China

Received:2023-02-18 Online:2024-09-25 Published:2024-10-22
Contact: Wenbiao TIAN

摘要/Abstract

摘要：

针对现有压缩感知贪婪算法容易陷于局部最优、过拟合等问题, 提出一种稀疏恢复算法, 称为多路径支撑集回溯贪婪重构(multipath backtracking greedy pursuit, MBGP)算法。该算法以最小残差为重构目标, 对候选原子展开多条路径同时搜索, 且每次筛选多个原子, 通过回溯过程剔除误选的原子。基于有限等距性质给出MBGP算法重构信号的充分条件, 以确保其从测量值精确恢复任何K-稀疏信号, 并通过信号重构能力来评估MBGP算法的性能。数值实验结果表明, 该算法在相同信号条件下, 能够在采样数更少、稀疏度更大的场合下精确重构信号, 且性能更逼近理想Oracle-最小二乘估计器。

关键词: 压缩感知, 信号恢复, 匹配追踪, 子空间追踪, 剪枝, 回溯, 贪婪算法

Abstract:

For the existing compressed sensing (CS) greedy algorithm, it is easy to fall into problems such as local optimum and overfitting. A sparse recovery algorithm called multipath backtracking greedy pursuit (MBGP) is proposed. MBGP algorithm searches the signal support set and iteratively examines multiple candidate support set estimates at the same time, and finally selects the one that minimizes the reconstruction residual. Based on the restricted isometry property, the sufficient conditions for the MBGP algorithm to reconstruct the signal are given to ensure that it can accurately recover any K-sparse signal from the measured value. The performance of the MBGP algorithm is evaluated by the signal reconstruction ability. Numerical experimental results show that the algorithm can accurately reconstruct signals with fewer samples and greater sparsity under the same signal conditions, and its performance is closer to the ideal Oracle-least square estimator.

Key words: compressed sensing (CS), signal recovery, matching pursuit, subspace pursuit, pruning, backtracking, greedy algorithm

中图分类号:

田文飚, 芮国胜, 张嵩, 张海波, 王林. 多路径支撑集回溯贪婪重构算法[J]. 系统工程与电子技术, 2024, 46(10): 3279-3284.

Wenbiao TIAN, Guosheng RUI, Song ZHANG, Haibo ZHANG, Lin WANG. Multipath backtracking greedy pursuit algorithm[J]. Systems Engineering and Electronics, 2024, 46(10): 3279-3284.

图/表 5

参考文献 27

1	ZHANG D , SUN Y M , ZHANG F R , et al. Phase retrieval for signals with block sparsity using BOMP: algorithms and recovery guarantees[J]. Digital Signal Processing, 2022, 129 (3): 103656.
2	SIEGEL J W , XU J . Optimal convergence rates for the orthogonal greedy algorithm[J]. IEEE Trans. on Information Theory, 2022, 68 (5): 3354- 3361. doi: 10.1109/TIT.2022.3147984
3	PALI M , RUETZ S , SCHNASS K . Average performance of OMP and thresholding under dictionary mismatch[J]. IEEE Signal Processing Letters, 2022, 29 (4): 1077- 1081.
4	MORALES-PEREZ C , RANGEL-MAGDALENO J , PEREGRI-NA-BARRETO H , et al. Noise reduction in electrical signal using OMP algorithm based on DCT and DSC dictionaries[J]. IEEE Trans. on Instrumentation and Measurement, 2022, 71 (12): 6500811.
5	CHENG C M , BAI E W , PENG Z K . Identification of sparse Volterra systems: an almost orthogonal matching pursuit approach[J]. IEEE Trans. on Automatic Control, 2022, 67 (4): 2027- 2032. doi: 10.1109/TAC.2021.3070027
6	WEN J M , WANG J , ZHANG Q Y . Nearly optimal bounds for orthogonal least squares[J]. IEEE Trans. on Signal Processing, 2017, 65 (20): 5347- 5356. doi: 10.1109/TSP.2017.2728502
7	FU T , ZONG Z Y , YIN X Y . Generalized orthogonal matching pursuit with singular value decomposition[J]. IEEE Geoscience and Remote Sensing Letters, 2022, 19 (6): 8013405.
8	DENG Q Y , ZENG H Q , ZHANG J , et al. Compressed sensing for image reconstruction via back-off and rectification of greedy algorithm[J]. Signal Processing, 2019, 157 (4): 280- 287.
9	KWON S , WANG J , SHI M B . Multipath matching pursuit[J]. IEEE Trans. on Information Theory, 2014, 60 (5): 2986- 3001. doi: 10.1109/TIT.2014.2310482
10	TAO J , QI C H , HUANG Y M . Regularized multipath match-ing pursuit for sparse channel estimation in millimeter wave massive MIMO system[J]. IEEE Wireless Communications letters, 2019, 8 (1): 169- 172. doi: 10.1109/LWC.2018.2865472
11	ZHAO J , BAI X , TAO R . RIP-based analysis of multipath matching pursuit in noisy case[J]. Electronics Letters, 2019, 55 (21): 1133- 1135. doi: 10.1049/el.2018.7932
12	ZHAO J , BAI X , TAO R . Improved RIP-based performance guarantees for multipath matching pursuit[J]. Science China Information Sciences, 2018, 61 (10): 102303. doi: 10.1007/s11432-017-9289-2
13	LI H F , WANG J , YUAN X . On the fundamental limit of multipath matching pursuit[J]. IEEE Journal of Selected Topics in Signal Processing, 2018, 12 (5): 916- 927. doi: 10.1109/JSTSP.2018.2842732
14	PARK D . Sufficient condition analysis of multipath matching pursuit[J]. Electronics Letters, 2018, 54 (4): 244- 246. doi: 10.1049/el.2017.2918
15	吴梦行, 伍飞云, 杨坤德, 等. 改进的稀疏度自适应多路径匹配追踪算法[J]. 哈尔滨工程大学学报, 2021, 42 (11): 1611- 1617.
	WU M X , WU Y F , YANG K D , et al. An improved multipath matching pursuit algorithm with sparsity self-adaption[J]. Journal of Harbin Engineering University, 2021, 42 (11): 1611- 1617.
16	SUN Q , WU F Y , YANG K D , et al. Sparse signal recovery from noisy measurements via searching forward OMP[J]. Electronics Letters, 2022, 58 (3): 124- 126. doi: 10.1049/ell2.12365
17	GENG P B , WANG J , CHEN W G . Multipath least squares algorithm and analysis[J]. Signal Processing, 2020, 174 (9): 107633.
18	MEIR E , ROUTTENBERG T . Cramér-Rao bound for estimation after model selection and its application to sparse vector estimation[J]. IEEE Trans. on Signal Processing, 2021, 69 (3): 2284- 2301.
19	ORTELLI F , GEER S . Oracle inequalities for square root ana-lysis estimators with application to total variation penalties[J]. Information and Inference: a Journal of the IMA, 2021, 10 (2): 483- 514. doi: 10.1093/imaiai/iaaa002
20	ADCOCK B , BOYER C , BRUGIAPAGLIA S . On oracle-type local recovery guarantees in compressed sensing[J]. Information and Inference: a Journal of the IMA, 2021, 10 (1): 1- 49. doi: 10.1093/imaiai/iaaa007
21	ELSENER A , GEER S . Sharp oracle inequalities for stationary points of nonconvex penalized M-estimators[J]. IEEE Trans. on Information Theory, 2019, 65 (3): 1452- 1472. doi: 10.1109/TIT.2018.2863700
22	SHAH N B , BALAKRISHNAN S , WAINWRIGHT M J . Feeling the Bern: adaptive estimators for Bernoulli probabilities of pairwise comparisons[J]. IEEE Trans. on Information Theory, 2019, 65 (8): 4854- 4874. doi: 10.1109/TIT.2019.2903249
23	YAZIDI A , OOMMEN B J . Novel discretized weak estimators based on the principles of the stochastic search on the line problem[J]. IEEE Trans. on Cybernetics, 2016, 46 (12): 2732- 2744. doi: 10.1109/TCYB.2015.2487338
24	MALEK-MOHAMMADI M , KOOCHAKZADEH A , BABAIE-ZADEH M , et al. Successive concave sparsity approximation for compressed sensing[J]. IEEE Trans. on Signal Processing, 2016, 64 (21): 5657- 5671. doi: 10.1109/TSP.2016.2585096
25	NEEDELL D , TROPP J A . CoSaMP: iterative signal recovery from incomplete and inaccurate samples[J]. Communications of the ACM, 2010, 53 (12): 93- 100. doi: 10.1145/1859204.1859229
26	GIRYES R , ELAD M . RIP-based near-oracle performance guarantees for SP, CoSaMP, and IHT[J]. IEEE Trans. on Signal Processing, 2012, 60 (3): 1465- 1468. doi: 10.1109/TSP.2011.2174985
27	WEI D , MILENKOVIC O . Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Trans. on Information Theory, 2009, 55 (5): 2230- 2249. doi: 10.1109/TIT.2009.2016006

[1]	安孟昀, 殷加鹏, 黄建开, 李永祯, 王雪松. 一种基于谱连续的极化-多普勒气象雷达信号重构方法[J]. 系统工程与电子技术, 2024, 46(7): 2285-2293.
[2]	曹若石, 赵永波, 邱雨铖. 基于改进SP算法的多目标DOA估计方法[J]. 系统工程与电子技术, 2024, 46(7): 2294-2300.
[3]	刘刚, 李雨航, 杨庆鑫, 郭漪. 基于压缩感知的智能反射面信道估计[J]. 系统工程与电子技术, 2024, 46(7): 2490-2497.
[4]	吴敏, 黎子皓, 郝程鹏, 胡桥. 基于压缩感知的低复杂度超分辨角度估计方法[J]. 系统工程与电子技术, 2024, 46(6): 1831-1837.
[5]	蔡畅, 陈建峰, 闫青丽, 刘芬. 考虑特殊区域的离散区域划分方法[J]. 系统工程与电子技术, 2024, 46(5): 1656-1664.
[6]	陈子睿, 陈阿磊, 刘维建, 杨军, 陈文峰, 马晓岩. 天波超视距雷达非均匀采样信号频谱重构[J]. 系统工程与电子技术, 2024, 46(4): 1236-1246.
[7]	陈汪翔, 田鹤, 王吉儿, 田单. 基于散射模型的球头锥目标几何结构参数估计[J]. 系统工程与电子技术, 2024, 46(3): 892-897.
[8]	邵凯, 杜自群, 王光宇. 基于模型剪枝动态调整压缩率的CSI反馈方法[J]. 系统工程与电子技术, 2023, 45(8): 2615-2622.
[9]	李晓辉, 李欢洋, 吕思婷, 石明利. 毫米波通感一体化中的混合波束赋形算法[J]. 系统工程与电子技术, 2023, 45(5): 1512-1517.
[10]	季策, 田博彦, 耿蓉, 李伯群. 基于VSCBOMP算法的FBMC/OQAM系统信道估计[J]. 系统工程与电子技术, 2023, 45(4): 1193-1199.
[11]	朱晓秀, 刘利民, 胡文华, 郭宝锋, 史林, 朱瀚神. 基于GTD模型的多视角多频带ISAR融合成像[J]. 系统工程与电子技术, 2023, 45(3): 726-735.
[12]	胡杰, 鲍帆, 石潇竹. 基于贪婪-遗传算法的机场登机口分配策略[J]. 系统工程与电子技术, 2023, 45(11): 3555-3564.
[13]	李瑞泽, 张双辉, 刘永祥. 基于卷积ADMM网络的高效结构化稀疏ISAR成像方法[J]. 系统工程与电子技术, 2023, 45(1): 56-70.
[14]	田鹤, 董纯柱, 殷红成. 基于频域稀疏压缩感知的雷达目标三维散射中心反演方法[J]. 系统工程与电子技术, 2022, 44(9): 2783-2790.
[15]	谢艾伦, 刘晓斌, 赵锋, 艾小锋, 肖顺平. 辐射式仿真中PCM信号间歇收发回波重构方法[J]. 系统工程与电子技术, 2022, 44(3): 771-776.

多路径支撑集回溯贪婪重构算法

Multipath backtracking greedy pursuit algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 27

相关文章 15

编辑推荐

Metrics

本文评价