×

Conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery. (English) Zbl 1461.94053

Summary: We propose a new iterative greedy algorithm to reconstruct sparse signals in Compressed Sensing. The algorithm, called Conjugate Gradient Hard Thresholding Pursuit (CGHTP), is a simple combination of Hard Thresholding Pursuit (HTP) and Conjugate Gradient Iterative Hard Thresholding (CGIHT). The conjugate gradient method with a fast asymptotic convergence rate is integrated into the HTP scheme that only uses simple line search, which accelerates the convergence of the iterative process. Moreover, an adaptive step size selection strategy, which constantly shrinks the step size until a convergence criterion is met, ensures that the algorithm has a stable and fast convergence rate without choosing step size. Finally, experiments on both Gaussian-signal and real-world images demonstrate the advantages of the proposed algorithm in convergence rate and reconstruction performance.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
90C52 Methods of reduced gradient type
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

LASSO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Donoho, D.L.; Compressed sensing; IEEE Trans. Inf. Theory: 2006; Volume 4 ,1289-1306. · Zbl 1288.94016
[2] Eldar, Y.; Kutinyok, G.; ; Compressed Sensing: Theory and Application: Cambridge, UK 2011; Volume Volume 4 ,1289-1306.
[3] Zhang, J.; Xiang, Q.; Yin, Y.; Chen, C.; Xin, L.; Adaptive compressed sensing for wireless image sensor networks; Multimed. Tools Appl.: 2017; Volume 3 ,4227-4242.
[4] Chen, Z.; Fu, Y.; Xiang, Y.; Rong, R.; A novel iterative shrinkage algorithm for CS-MRI via adaptive regularization; IEEE Signal Process. Lett.: 2017; Volume 10 ,1443-1447.
[5] Bu, H.; Tao, R.; Bai, X.; Zhao, J.; A novel SAR imaging algorithm based on compressed sensing; IEEE Geosci. Remote Sens. Lett.: 2015; Volume 5 ,1003-1007.
[6] Craven, D.; McGinley, B.; Kilmartin, L.; Glavin, M.; Jones, E.; Compressed sensing for bioelectric signals: A review; IEEE J. Biomed. Health Inform.: 2015; Volume 2 ,529-540.
[7] Candès, E.J.; Tao, T.; Decoding by linear programming; IEEE Trans. Inf. Theory: 2005; Volume 12 ,4203-4215. · Zbl 1264.94121
[8] Candès, E.J.; Romberg, J.; Tao, T.; Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information; IEEE Trans. Inf. Theory: 2006; Volume 2 ,489-509. · Zbl 1231.94017
[9] Vujović, S.; Stanković, I.; Daković, M.; Stanković, L.; Comparison of a gradient-based and LASSO (ISTA) algorithm for sparse signal reconstruction; Proceedings of the 5th Mediterranean Conference on Embedded Computing: ; ,377-380. · Zbl 1386.94038
[10] Beck, A.; Teboulle, M.; A fast iterative shrinkage-thresholding algorithm for linear inverse problems; SIAM J. Imaging Sci.: 2009; Volume 1 ,183-202. · Zbl 1175.94009
[11] Xie, K.; He, Z.; Cichocki, A.; Convergence analysis of the FOCUSS algorithm; IEEE Trans. Neural Netw. Learn. Syst: 2015; Volume 3 ,601-613.
[12] Zibetti, M.V.; Helou, E.S.; Pipa, D.R.; Accelerating overrelaxed and monotone fast iterative shrinkage-thresholding algorithms with line search for sparse reconstructions; IEEE Trans. Image Process.: 2017; Volume 7 ,3569-3578. · Zbl 1409.94807
[13] Cui, A.; Peng, J.; Li, H.; Wen, M.; Jia, J.; Iterative thresholding algorithm based on non-convex method for modified ℓp-norm regularization minimization; J. Comput. Appl. Math.: 2019; Volume 347 ,173-180. · Zbl 1410.90162
[14] Fei, W.; Liu, P.; Liu, Y.; Qiu, R.C.; Yu, W.; Robust sparse recovery for compressive sensing in impulsive noise using p-norm model fitting; Proceedings of the IEEE International Conference on Acoustics, Acoustics, Speech and Signal Processing (ICASSP): ; .
[15] Ghayem, F.; Sadeghi, M.; Babaie-Zadeh, M.; Chatterjee, S.; Skoglund, M.; Jutten, C.; Sparse signal recovery using iterative proximal projection; IEEE Trans. Signal Process.: 2018; Volume 4 ,879-894. · Zbl 1414.94214
[16] Dirksen, S.; Lecué, G.; Rauhut, H.; On the gap between restricted isometry properties and sparse recovery conditions; IEEE Trans. Inf. Theory: 2018; Volume 8 ,5478-5487. · Zbl 1401.94031
[17] Cohen, A.; Dahmen, W.; DeVore, R.; Orthogonal matching pursuit under the restricted isometry property; Constr. Approx.: 2017; Volume 1 ,113-127. · Zbl 1379.94014
[18] Satpathi, S.; Chakraborty, M.; On the number of iterations for convergence of cosamp and subspace pursuit algorithms; Appl. Comput. Harmon. Anal.: 2017; Volume 3 ,568-576. · Zbl 1372.65183
[19] Needell, D.; Vershynin, R.; Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit; IEEE J. Sel. Top. Signal Process.: 2010; Volume 2 ,310-316.
[20] Wang, J.; Kwon, S.; Li, P.; Shim, B.; Recovery of sparse signals via generalized orthogonal matching pursuit: A new analysis; IEEE Trans. Signal Process.: 2016; Volume 4 ,1076-1089. · Zbl 1412.94098
[21] Yao, S.; Wang, T.; Chong, Y.; Pan, S.; Sparsity estimation based adaptive matching pursuit algorithm; Multimed. Tools Appl.: 2018; Volume 4 ,4095-4112.
[22] Saadat, S.A.; Safari, A.; Needell, D.; Sparse Reconstruction of Regional Gravity Signal Based on Stabilized Orthogonal Matching Pursuit (SOMP); Pure Appl. Geophys.: 2016; Volume 6 ,2087-2099.
[23] Cui, Y.; Xu, W.; Tian, Y.; Lin, J.; Perturbed block orthogonal matching pursuit; Electron. Lett.: 2018; Volume 22 ,1300-1302.
[24] Shalaby, W.A.; Saad, W.; Shokair, M.; Dessouky, M.I.; Forward-backward hard thresholding algorithm for compressed sensing; Proceedings of the 2017 34th National Radio Science Conference (NRSC): ; ,142-151.
[25] Blumensath, T.; Accelerated iterative hard thresholding; Signal Process.: 2012; Volume 3 ,752-756.
[26] Blanchard, J.D.; Tanner, J.; Wei, K.; Conjugate gradient iterative hard thresholding: Observed noise stability for compressed sensing; IEEE Trans. Signal Process.: 2015; Volume 2 ,528-537. · Zbl 1394.94083
[27] Blanchard, J.D.; Tanner, J.; Wei, K.; CGIHT: Conjugate gradient iterative hard thresholding for compressed sensing and matrix completion; Inf. Inference J. IMA: 2015; Volume 4 ,289-327. · Zbl 1380.94045
[28] Foucart, S.; Hard thresholding pursuit: An algorithm for compressive sensing; SIAM J. Numer. Anal.: 2011; Volume 6 ,2543-2563. · Zbl 1242.65060
[29] Bouchot, J.L.; Foucart, S.; Hitczenko, P.; Hard thresholding pursuit algorithms: Number of iterations; Appl. Comput. Harmon. Anal.: 2016; Volume 2 ,412-435. · Zbl 1346.65012
[30] Li, H.; Fu, Y.; Zhang, Q.; Rong, R.; A generalized hard thresholding pursuit algorithm; Circuits Syst. Signal Process.: 2014; Volume 4 ,1313-1323.
[31] Sun, T.; Jiang, H.; Cheng, L.; Hard thresholding pursuit with continuation for ℓ0 regularized minimizations; Math. Meth. Appl. Sci.: 2018; Volume 16 ,6195-6209. · Zbl 1402.90181
[32] Jain, P.; Tewari, A.; Dhillon, I.S.; Partial hard thresholding; IEEE Trans. Inf. Theory: 2017; Volume 5 ,3029-3038. · Zbl 1368.94031
[33] Song, C.B.; Xia, S.T.; Liu, X.J.; Subspace thresholding pursuit: A reconstruction algorithm for compressed sensing; Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT): ; .
[34] Powell, M.J.D.; Some convergence properties of the conjugate gradient method; Math. Program.: 1976; Volume 1 ,42-49. · Zbl 0356.65056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.