A Review of Atom Recognition Strategies for Greedy Class Reconstruction Algorithms Based on Compressed Sensing

LIU Sujuan; CUI Chengkai; ZHENG Lili; JIANG Shuyang

doi:10.11999/JEIT211297

Volume 45 Issue 1

Jan. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(1): 361-370

LIU Sujuan, CUI Chengkai, ZHENG Lili, JIANG Shuyang. A Review of Atom Recognition Strategies for Greedy Class Reconstruction Algorithms Based on Compressed Sensing[J]. Journal of Electronics & Information Technology, 2023, 45(1): 361-370. doi: 10.11999/JEIT211297

Citation:

LIU Sujuan, CUI Chengkai, ZHENG Lili, JIANG Shuyang. A Review of Atom Recognition Strategies for Greedy Class Reconstruction Algorithms Based on Compressed Sensing[J]. Journal of Electronics & Information Technology, 2023, 45(1): 361-370. doi: 10.11999/JEIT211297

Citation:

PDF( 2422 KB)

A Review of Atom Recognition Strategies for Greedy Class Reconstruction Algorithms Based on Compressed Sensing

doi: 10.11999/JEIT211297

College of Microelectronics, Beijing University of Technology, Beijing 100124, China

Funds: The National Natural Sciences Foundation of China (62074010), Beijing Municipal Education Commission Science and Technology Project (KM201810005022)

Received Date: 2021-11-18
Rev Recd Date: 2022-03-28

Available Online: 2022-04-07

Publish Date: 2023-01-17

Abstract

Abstract

Among the Compressed Sensing(CS) reconstruction algorithms, greedy algorithm has been widely studied for its simple hardware implementation and excellent recovery accuracy. However, the diversity of algorithms also presents the problem of difficult algorithm selection. As the core of greedy algorithms, the difference of atomic recognition strategy often determines its recovery performance. In this paper, atomic recognition strategy, which is the most important part of greedy algorithm, is taken as the research object. Three one-step atom recognition strategies, eight advanced atom recognition strategies and three sparsity adaptive atom recognition strategies are summarized according to the applicable stages and characteristics. Finally, the recovery performance of the original algorithms corresponding to the atomic recognition strategies are simulated and compared. The sorted strategies are convenient for the selection of algorithms in practical application, and they provide references for the further optimization of greedy algorithms.
- Compressed Sensing(CS),
- Greedy class recovery algorithms,
- Atom recognition strategy

FullText(HTML)

References(43)

References

[1]	DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289–1306. doi: 10.1109/TIT.2006.871582
[2]	WEN Jinming, ZHANG Rui, and YU Wei. Signal-dependent performance analysis of orthogonal matching pursuit for exact sparse recovery[J]. IEEE Transactions on Signal Processing, 2020, 68: 5031–5046. doi: 10.1109/TSP.2020.3016571
[3]	CANDES E J and WAKIN M B. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 21–30. doi: 10.1109/MSP.2007.914731
[4]	MALLAT S G and ZHANG Zhifeng. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3397–3415. doi: 10.1109/78.258082
[5]	PATI Y C, REZAIIFAR R, and KRISHNAPRASAD P S. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[C]. 27th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, 1993: 40–44.
[6]	NEEDELL D and VERSHYNIN R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 310–316. doi: 10.1109/JSTSP.2010.2042412
[7]	GOYAL P and SINGH B. Sparse signal recovery through regularized orthogonal matching pursuit for WSNs applications[C]. 2019 6th International Conference on Signal Processing and Integrated Networks (SPIN), Noida, India, 2019: 461–465.
[8]	WANG Jian, KWON S, and SHIM B. Generalized orthogonal matching pursuit[J]. IEEE Transactions on Signal Processing, 2012, 60(12): 6202–6216. doi: 10.1109/TSP.2012.2218810
[9]	申滨, 吴和彪, 崔太平, 等. 基于最优索引广义正交匹配追踪的非正交多址系统多用户检测[J]. 电子与信息学报, 2020, 42(3): 621–628. doi: 10.11999/JEIT190270 SHEN Bin, WU Hebiao, CUI Taiping, et al. An optimal number of indices aided gOMP algorithm for multi-user detection in NOMA System[J]. Journal of Electronics &Information Technology, 2020, 42(3): 621–628. doi: 10.11999/JEIT190270
[10]	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
[11]	CHEN Jing, CHEN Yan, WU Lei, et al. An improved stagewise weak orthogonal matching pursuit method for electric power transmission tower evaluation using differential sar tomography[C]. IGARSS 2019 - 2019 IEEE International Geoscience and Remote Sensing Symposium, Yokohama, Japan, 2019: 3637–3640.
[12]	DO T T, GAN Lu, NGUYEN N, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]. 2008 42nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, 2008: 581–587.
[13]	吴新杰, 闫诗雨, 徐攀峰, 等. 基于稀疏度自适应压缩感知的电容层析成像图像重建算法[J]. 电子与信息学报, 2018, 40(5): 1250–1257. doi: 10.11999/JEIT170794 WU Xinjie, YAN Shiyu, XU Panfeng, et al. Image reconstruction algorithm for electrical capacitance tomography based on sparsity adaptive compressed sensing[J]. Journal of Electronics &Information Technology, 2018, 40(5): 1250–1257. doi: 10.11999/JEIT170794
[14]	李保珠, 邵建华, 聂梦雅, 等. 基于能量的稀疏自适应匹配追踪算法[J]. 计算机应用与软件, 2015, 32(11): 121–125. doi: 10.3969/j.issn.1000-386x.2015.11.028 LI Baozhu, SHAO Jianhua, NIE Mengya, et al. Energy-based sparsity adaptive matching pursuit algorithm[J]. Computer Applications and Software, 2015, 32(11): 121–125. doi: 10.3969/j.issn.1000-386x.2015.11.028
[15]	ZHANG Yi, VENKATESAN R, DOBRE O A, et al. Efficient estimation and prediction for sparse time-varying underwater acoustic channels[J]. IEEE Journal of Oceanic Engineering, 2020, 45(3): 1112–1125. doi: 10.1109/JOE.2019.2911446
[16]	朱延万, 赵拥军, 孙兵. 一种改进的稀疏度自适应匹配追踪算法[J]. 信号处理, 2012, 28(1): 80–86. doi: 10.3969/j.issn.1003-0530.2012.01.012 ZHU Yanwan, ZHAO Yongjun, and SUN Bing. A modified sparsity adaptive matching pursuit algorithm[J]. Signal Processing, 2012, 28(1): 80–86. doi: 10.3969/j.issn.1003-0530.2012.01.012
[17]	CHATTERJEE S, SUNDMAN D, VEHKAPERA M, et al. Projection-based and look-ahead strategies for atom selection[J]. IEEE Transactions on Signal Processing, 2012, 60(2): 634–647. doi: 10.1109/TSP.2011.2173682
[18]	HANG Jinwei and HUANG Yuanhao. A high-SNR projection-based atom selection OMP processor for compressive sensing[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2016, 24(12): 3477–3488. doi: 10.1109/TVLSI.2016.2554401
[19]	AMBAT S K, CHATTERJEE S, and HARI K V S. On selection of search space dimension in compressive sampling matching pursuit[C]. TENCON 2012 IEEE Region 10 Conference, Cebu, Philippines, 2012: 1–5.
[20]	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
[21]	CHENG Jiawei. An improved off-grid algorithm based on CoSaMP for ISAR imaging[C]. 2020 5th International Conference on Mechanical, Control and Computer Engineering (ICMCCE), Harbin, China, 2020: 1643–1646,
[22]	CHAE J and HONG S. Greedy algorithms for sparse and positive signal recovery based on Bit-Wise MAP detection[J]. IEEE Transactions on Signal Processing, 2020, 68: 4017–4029. doi: 10.1109/TSP.2020.3004700
[23]	DAI Wei 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
[24]	LIU Yizhong, SONG Tian, and ZHUANG Yiqi. A high-throughput subspace pursuit processor for ECG recovery in compressed sensing using square-root-free MGS QR decomposition[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2020, 28(1): 174–187. doi: 10.1109/TVLSI.2019.2936867
[25]	LIU Lufeng, DU Xinpeng, and CHENG Lizhi. Stable signal recovery via randomly enhanced adaptive subspace pursuit method[J]. IEEE Signal Processing Letters, 2013, 20(8): 823–826. doi: 10.1109/LSP.2013.2267796
[26]	LIU Guangcan, ZHANG Zhao, LIU Qingshan, et al. Robust subspace clustering with compressed data[J]. IEEE Transactions on Image Processing, 2019, 28(10): 5161–5170. doi: 10.1109/TIP.2019.2917857
[27]	AMBAT S K, CHATTERJEE S, and HARI K V S. Subspace pursuit embedded in orthogonal matching pursuit[C]. TENCON 2012 IEEE Region 10 Conference, Cebu, Philippines, 2012: 1–5.
[28]	LIU Jing, HUANG Kaiyu, and YAO Xianghua. Common-innovation subspace pursuit for distributed compressed sensing in wireless sensor networks[J]. IEEE Sensors Journal, 2019, 19(3): 1091–1103. doi: 10.1109/JSEN.2018.2881056
[29]	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.
[30]	MURALIKRISHNNA G S, AMBAT S K, and HARI K V S. Batch look ahead orthogonal matching pursuit[C]. 2018 Twenty Fourth National Conference on Communications (NCC), Hyderabad, India, 2018: 1–5.
[31]	SWAMY P B, AMBAT S K, CHATTERJEE S, et al. Reduced look ahead orthogonal matching pursuit[C]. 2014 Twentieth National Conference on Communications (NCC), Kanpur, India, 2014: 1–6.
[32]	AMBAT S K, CHATTERJEE S, and HARI K V S. Adaptive selection of search space in look ahead orthogonal matching pursuit[C]. 2012 National Conference on Communications (NCC), Kharagpur, India, 2012: 1–5.
[33]	KOPPARTHI V R, PEESAPATI R, and SABAT S L. System on chip implementation of low complex orthogonal matching pursuit algorithm on FPGA[C]. 2020 6th International Conference on Signal Processing and Communication (ICSC), Noida, India, 2020: 178–184.
[34]	CAI T T and WANG Lie. Orthogonal matching pursuit for sparse signal recovery with noise[J]. IEEE Transactions on Information Theory, 2011, 57(7): 4680–4688. doi: 10.1109/TIT.2011.2146090
[35]	WANG Zhizhan, LI Yuzhou, WANG Chengcai, et al. A-OMP: An adaptive OMP algorithm for underwater acoustic OFDM channel estimation[J]. IEEE Wireless Communications Letters, 2021, 10(8): 1761–1765. doi: 10.1109/LWC.2021.3079225
[36]	ZHANG Yi, VENKATESAN R, DOBRE O A, et al. An adaptive matching pursuit algorithm for sparse channel estimation[C]. 2015 IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, USA, 2015: 626–630.
[37]	HU Yunfeng and ZHAO Liquan. A fuzzy selection compressive sampling matching pursuit algorithm for its practical application[J]. IEEE Access, 2019, 7: 144101–144124. doi: 10.1109/ACCESS.2019.2941725
[38]	MOURAD N, SHARKAS M, and ELSHERBENY M M. Orthogonal matching pursuit with correction[C]. 2016 IEEE 12th International Colloquium on Signal Processing & Its Applications (CSPA), Melaka, Malaysia, 2016: 247–252.
[39]	ZHAO Juan and BAI Xia. Adaptive matching pursuit method based on auxiliary residual for sparse signal recovery[C]. 2019 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), Lanzhou, China, 2019: 774–778.
[40]	HUANG Honglin and MAKUR A. Backtracking-based matching pursuit method for sparse signal reconstruction[J]. IEEE Signal Processing Letters, 2011, 18(7): 391–394. doi: 10.1109/LSP.2011.2147313
[41]	ZENG Chunyan, MA Lihong, DU Minghui, et al. Regularized sequential selection and backtracking removal for CS atom matching[C]. 2012 IEEE 14th International Workshop on Multimedia Signal Processing (MMSP), Banff, Canada, 2012: 209–214,
[42]	GAO Guangyong, ZHOU Caixue, CUI Zongmin, et al. Improved sparsity adaptive matching pursuit algorithm[C]. 2017 3rd IEEE International Conference on Computer and Communications (ICCC), Chengdu, China, 2017: 1761–1766.
[43]	ZHENG Baifu, ZENG Cao, LI Shidong, et al. Joint sparse recovery for signals of spark-level sparsity and MMV tail- $ \ell _{2, 1}$ minimization[J]. IEEE Signal Processing Letters, 2021, 28: 1130–1134. doi: 10.1109/LSP.2021.3084517