Accelerated over-relaxation heavy-ball hard thresholding pursuit for compressive sensing

Xinyu Diao; Zhongfeng Sun; Jingyong Tang; Jinchuan Zhou; Xinyu Diao; Zhongfeng Sun; Jingyong Tang; Jinchuan Zhou

doi:10.3934/math.2025831

AIMS Mathematics

2025, Volume 10, Issue 8: 18603-18626. doi: 10.3934/math.2025831

Previous Article Next Article

Research article

Accelerated over-relaxation heavy-ball hard thresholding pursuit for compressive sensing

1.
School of Mathematics and Statistics, Shandong University of Technology, Zibo 255000, China
2.
School of Mathematics and Statistics, Xinyang Normal University, Xinyang 464000, China

Received: 22 April 2025 Revised: 24 July 2025 Accepted: 04 August 2025 Published: 18 August 2025
MSC : 90C26, 90C52

In this paper, we propose a novel algorithm, called Accelerated Over-Relaxation Heavy-Ball Hard Threshold Pursuit (AOR-HBHTP), for solving compressive sensing problems. The algorithm incorporates the Accelerated Over-Relaxation technique and Heavy-Ball momentum into the Hard Threshold Pursuit framework. Theoretical results include establishing convergence analysis and providing an estimation of the number of iteration steps. We show that, as long as the measurement matrix satisfies the restricted isometry property, AOR-HBHTP can successfully recover unknown signals within a number of iterations proportional to the sparsity level. The upper bound on the number of iterations is uniform in the sense that it does not depend on any unknown special-signal information. In numerical experiments, we evaluate recovery capability, success rate, and runtime of AOR-HBHTP by using Phase Transition Curve, Algorithm Selection Map, and Signal-to-Noise Ratio. The promising numerical results demonstrate the effectiveness of AOR-HBHTP in recovering sparse signals.
- compressive sensing,
- sparse signal recovery,
- restricted isometry property,
- hard thresholding pursuit,
- accelerated over-relaxation heavy-ball methods
Citation: Xinyu Diao, Zhongfeng Sun, Jingyong Tang, Jinchuan Zhou. Accelerated over-relaxation heavy-ball hard thresholding pursuit for compressive sensing[J]. AIMS Mathematics, 2025, 10(8): 18603-18626. doi: 10.3934/math.2025831

Related Papers:

Abstract

In this paper, we propose a novel algorithm, called Accelerated Over-Relaxation Heavy-Ball Hard Threshold Pursuit (AOR-HBHTP), for solving compressive sensing problems. The algorithm incorporates the Accelerated Over-Relaxation technique and Heavy-Ball momentum into the Hard Threshold Pursuit framework. Theoretical results include establishing convergence analysis and providing an estimation of the number of iteration steps. We show that, as long as the measurement matrix satisfies the restricted isometry property, AOR-HBHTP can successfully recover unknown signals within a number of iterations proportional to the sparsity level. The upper bound on the number of iterations is uniform in the sense that it does not depend on any unknown special-signal information. In numerical experiments, we evaluate recovery capability, success rate, and runtime of AOR-HBHTP by using Phase Transition Curve, Algorithm Selection Map, and Signal-to-Noise Ratio. The promising numerical results demonstrate the effectiveness of AOR-HBHTP in recovering sparse signals.

References

[1]	D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), 1289–1306. https://doi.org/10.1109/TIT.2006.871582 doi: 10.1109/TIT.2006.871582
[2]	S. Foucart, H. Rauhut, An invitation to compressive sensing, In: A mathematical introduction to compressive sensing, New York: Springer, 2013. https://doi.org/10.1007/978-0-8176-4948-7_1
[3]	C. Qiu, X. Hu, AdaCS: adaptive compressive sensing with restricted isometry property-based error-clamping, IEEE Trans. Pattern Anal., 46 (2024), 4702–4719. https://doi.org/10.1109/TPAMI.2024.3357704 doi: 10.1109/TPAMI.2024.3357704
[4]	S. Foucart, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49 (2011), 2543–2563. https://doi.org/10.1137/100806278 doi: 10.1137/100806278
[5]	T. Blumensath, M. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27 (2009), 265–274. https://doi.org/10.1016/j.acha.2009.04.002 doi: 10.1016/j.acha.2009.04.002
[6]	Y. Feng, A. Taya, Y. Nishiyama, K. Sezaki, J. Liu, Compressive detection of stochastic sparse signals with unknown sparsity degree, IEEE Signal Proc. Lett., 30 (2023), 1482–1486. https://doi.org/10.1109/LSP.2023.3324573 doi: 10.1109/LSP.2023.3324573
[7]	W. Xiong, J. Cao, S. Li, Sparse signal recovery with unknown signal sparsity, EURASIP J. Adv. Signal Process., 2014 (2014), 178. https://doi.org/10.1186/1687-6180-2014-178 doi: 10.1186/1687-6180-2014-178
[8]	M. Lopes, Unknown sparsity in compressed sensing: denoising and inference, IEEE Trans. Inform. Theory, 62 (2016), 5145–5166. https://doi.org/10.1109/TIT.2016.2587772 doi: 10.1109/TIT.2016.2587772
[9]	C. An, J. Ran, Hard thresholding hyperinterpolation over general regions, J. Sci. Comput., 102 (2025), 37. https://doi.org/10.1007/s10915-024-02754-4 doi: 10.1007/s10915-024-02754-4
[10]	C. An, J. Ran, A. Sommariva, Hybrid hyperinterpolation over general regions, Calcolo, 62 (2025), 3. https://doi.org/10.1007/s10092-024-00625-w doi: 10.1007/s10092-024-00625-w
[11]	Z. He, Q. Shu, Y. Wang, J. Wen, A ReLU-based hard-thresholding algorithm for non-negative sparse signal recovery, Signal Process., 215 (2024), 109260. https://doi.org/10.1016/j.sigpro.2023.109260 doi: 10.1016/j.sigpro.2023.109260
[12]	J. Xue, Y. Zhao, T. Wu, J. Chan, Tensor convolution-like low-rank dictionary for high-dimensional image representation, IEEE Trans. Circ. Syst. Vid., 34 (2024), 13257–13270. https://doi.org/10.1109/TCSVT.2024.3442295 doi: 10.1109/TCSVT.2024.3442295
[13]	J. Xue, Y. Zhao, S. Huang, W. Liao, J. Chan, S. Kong, Multilayer sparsity-based tensor decomposition for low-rank tensor completion, IEEE Trans. Neur. Net. Lear., 33 (2022), 6916–6930. https://doi.org/10.1109/TNNLS.2021.3083931 doi: 10.1109/TNNLS.2021.3083931
[14]	J. Xue, Y. Zhao, Y. Bu, J. Chan, S. Kong, When Laplacian scale mixture meets three-layer transform: a parametric tensor sparsity for tensor completion, IEEE Trans. Cybernetics, 52 (2022), 13887–13901. https://doi.org/10.1109/TCYB.2021.3140148 doi: 10.1109/TCYB.2021.3140148
[15]	J. Huang, F. Zhang, J. Wang, X. Liu, J. Jia, The perturbation analysis of nonconvex low-rank matrix robust recovery, IEEE Trans. Neur. Net. Lear., 35 (2024), 15710–15723. https://doi.org/10.1109/TNNLS.2023.3289209 doi: 10.1109/TNNLS.2023.3289209
[16]	J. Huang, F. Zhang, X. Liu, J. Wang, J. Jia, R. Wang, Stable recovery of sparse signals with non-convex weighted r-norm minus 1-norm, J. Comput. Math., 43 (2025), 43–62. https://doi.org/10.4208/jcm.2307-m2022-0225 doi: 10.4208/jcm.2307-m2022-0225
[17]	J. Huang, X. Liu, F. Zhang, G. Luo, R. Tang, Performance analysis of unconstrained $l_p$ minimization for sparse recovery, Signal Process., 233 (2025), 109937. https://doi.org/10.1016/j.sigpro.2025.109937 doi: 10.1016/j.sigpro.2025.109937
[18]	J. Aujol, C. Dossal, A. Rondepierre, Convergence rates of the heavy-ball method under the Lojasiewicz property, Math. Program., 198 (2023), 195–254. https://doi.org/10.1007/s10107-022-01770-2 doi: 10.1007/s10107-022-01770-2
[19]	B. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comp. Math. Math. Phys., 4 (1964), 1–17. https://doi.org/10.1016/0041-5553(64)90137-5 doi: 10.1016/0041-5553(64)90137-5
[20]	Y. Zeng, D. Han, Y. Su, J. Xie, On adaptive stochastic heavy ball momentum for solving linear systems, SIAM J. Matrix Anal. Appl., 45 (2024), 1259–1286. https://doi.org/10.1137/23M1575883 doi: 10.1137/23M1575883
[21]	H. Attouch, J. Fadili, From the Ravine method to the Nesterov method and vice versa: a dynamical system perspective, SIAM J. Optimiz., 32 (2022), 2074–2101. https://doi.org/10.1137/22M1474357 doi: 10.1137/22M1474357
[22]	Y. Nesterov, A method for unconstrained convex minimization problem with the rate of convergence $O(1/k^2)$, Dokl. Akad. Nauk. SSSR, 269 (1983), 543–547.
[23]	X. Zeng, J. Lei, J. Chen, Dynamical primal-dual Nesterov accelerated method and its application to network optimization, IEEE Trans. Automat. Contr., 68 (2023), 1760–1767. https://doi.org/10.1109/TAC.2022.3152720 doi: 10.1109/TAC.2022.3152720
[24]	E. Ghadimi, H. Feyzmahdavian, M. Johansson, Global convergence of the heavy-ball method for convex optimization, Proceedings of European Control Conference (ECC), 2015,310–315. https://doi.org/10.1109/ECC.2015.7330562
[25]	S. Saab, S. Phoha, M. Zhu, A. Ray, An adaptive polyak heavy-ball method, Mach. Learn., 111 (2022), 3245–3277. https://doi.org/10.1007/s10994-022-06215-7 doi: 10.1007/s10994-022-06215-7
[26]	B. Shi, S. Du, M. Jordan, W. Su, Understanding the acceleration phenomenon via high-resolution differential equations, Math. Program., 195 (2022), 79–148. https://doi.org/10.1007/s10107-021-01681-8 doi: 10.1007/s10107-021-01681-8
[27]	B. Goujaud, A. Taylor, A. Dieuleveut, Provable non-accelerations of the heavy-ball method, arXiv: 2307.11291. https://doi.org/10.48550/arXiv.2307.11291
[28]	J. Wei, L. Chen, Accelerated over-relaxation heavy-ball method: achieving global accelerated convergence with broad generalization, arXiv: 2406.09772. https://doi.org/10.48550/arXiv.2406.09772
[29]	Z. Sun, J. Zhou, Y. Zhao, N. Meng, Heavy-ball-based hard thresholding algorithms for sparse signal recovery, J. Comput. Appl. Math., 430 (2023), 115264. https://doi.org/10.1016/j.cam.2023.115264 doi: 10.1016/j.cam.2023.115264
[30]	D. Needell, J. Tropp, CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26 (2009), 301–321. https://doi.org/10.1016/j.acha.2008.07.002 doi: 10.1016/j.acha.2008.07.002
[31]	W. Dai, O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55 (2009), 2230–2249. https://doi.org/10.1109/TIT.2009.2016006 doi: 10.1109/TIT.2009.2016006
[32]	Y. Zhao, Z. Luo, Dynamic orthogonal matching pursuit for sparse data reconstruction, IEEE Open Journal of Signal Processing, 4 (2023), 242–256. https://doi.org/10.1109/OJSP.2023.3247301 doi: 10.1109/OJSP.2023.3247301
[33]	J. Bouchot, S. Foucart, P. Hitczenko, Hard thresholding pursuit algorithms: number of iterations, Appl. Comput. Harmon. Anal., 41 (2016), 412–435. https://doi.org/10.1016/j.acha.2016.03.002 doi: 10.1016/j.acha.2016.03.002
[34]	J. Blanchard, J. Tanner, Performance comparisons of greedy algorithms in compressed sensing, Numer. Linear Algebr., 22 (2015), 254–282. https://doi.org/10.1002/nla.1948 doi: 10.1002/nla.1948
[35]	J. Blanchard, J. Tanner, K. Wei, CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Inf. Inference, 4 (2015), 289–327. https://doi.org/10.1093/imaiai/iav011 doi: 10.1093/imaiai/iav011

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)