A tight bound of modified iterative hard thresholding algorithm for compressed sensing

Jinyao Ma; Haibin Zhang; Shanshan Yang; Jiaojiao Jiang

Applications of Mathematics (2023)

  • Volume: 68, Issue: 5, page 623-642
  • ISSN: 0862-7940

Abstract

top
We provide a theoretical study of the iterative hard thresholding with partially known support set (IHT-PKS) algorithm when used to solve the compressed sensing recovery problem. Recent work has shown that IHT-PKS performs better than the traditional IHT in reconstructing sparse or compressible signals. However, less work has been done on analyzing the performance guarantees of IHT-PKS. In this paper, we improve the current RIP-based bound of IHT-PKS algorithm from δ 3 s - 2 k < 1 32 ≈ 0 . 1768 to δ 3 s - 2 k < 5 - 1 4 ≈ 0 . 309 , where δ 3 s - 2 k is the restricted isometric constant of the measurement matrix. We also present the conditions for stable reconstruction using the IHT μ -PKS algorithm which is a general form of IHT-PKS. We further apply the algorithm on Least Squares Support Vector Machines (LS-SVM), which is one of the most popular tools for regression and classification learning but confronts the loss of sparsity problem. After the sparse representation of LS-SVM is presented by compressed sensing, we exploit the support of bias term in the LS-SVM model with the IHT μ -PKS algorithm. Experimental results on classification problems show that IHT μ -PKS outperforms other approaches to computing the sparse LS-SVM classifier.

How to cite

top

Ma, Jinyao, et al. "A tight bound of modified iterative hard thresholding algorithm for compressed sensing." Applications of Mathematics 68.5 (2023): 623-642. <http://eudml.org/doc/299524>.

@article{Ma2023,
abstract = {We provide a theoretical study of the iterative hard thresholding with partially known support set (IHT-PKS) algorithm when used to solve the compressed sensing recovery problem. Recent work has shown that IHT-PKS performs better than the traditional IHT in reconstructing sparse or compressible signals. However, less work has been done on analyzing the performance guarantees of IHT-PKS. In this paper, we improve the current RIP-based bound of IHT-PKS algorithm from $\delta _\{3s-2k\}<\smash\{\frac\{1\}\{\sqrt\{32\}\}\}\approx 0.1768$ to $\delta _\{3s-2k\}<\frac\{\sqrt\{5\}-1\}\{4\}\approx 0.309$, where $\delta _\{3s-2k\}$ is the restricted isometric constant of the measurement matrix. We also present the conditions for stable reconstruction using the $\{\rm IHT\}^\{\mu \}$-PKS algorithm which is a general form of IHT-PKS. We further apply the algorithm on Least Squares Support Vector Machines (LS-SVM), which is one of the most popular tools for regression and classification learning but confronts the loss of sparsity problem. After the sparse representation of LS-SVM is presented by compressed sensing, we exploit the support of bias term in the LS-SVM model with the $\{\rm IHT\}^\{\mu \}$-PKS algorithm. Experimental results on classification problems show that $\{\rm IHT\}^\{\mu \}$-PKS outperforms other approaches to computing the sparse LS-SVM classifier.},
author = {Ma, Jinyao, Zhang, Haibin, Yang, Shanshan, Jiang, Jiaojiao},
journal = {Applications of Mathematics},
keywords = {iterative hard thresholding; signal reconstruction; classification problem; least squares support vector machine},
language = {eng},
number = {5},
pages = {623-642},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A tight bound of modified iterative hard thresholding algorithm for compressed sensing},
url = {http://eudml.org/doc/299524},
volume = {68},
year = {2023},
}

TY - JOUR
AU - Ma, Jinyao
AU - Zhang, Haibin
AU - Yang, Shanshan
AU - Jiang, Jiaojiao
TI - A tight bound of modified iterative hard thresholding algorithm for compressed sensing
JO - Applications of Mathematics
PY - 2023
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 5
SP - 623
EP - 642
AB - We provide a theoretical study of the iterative hard thresholding with partially known support set (IHT-PKS) algorithm when used to solve the compressed sensing recovery problem. Recent work has shown that IHT-PKS performs better than the traditional IHT in reconstructing sparse or compressible signals. However, less work has been done on analyzing the performance guarantees of IHT-PKS. In this paper, we improve the current RIP-based bound of IHT-PKS algorithm from $\delta _{3s-2k}<\smash{\frac{1}{\sqrt{32}}}\approx 0.1768$ to $\delta _{3s-2k}<\frac{\sqrt{5}-1}{4}\approx 0.309$, where $\delta _{3s-2k}$ is the restricted isometric constant of the measurement matrix. We also present the conditions for stable reconstruction using the ${\rm IHT}^{\mu }$-PKS algorithm which is a general form of IHT-PKS. We further apply the algorithm on Least Squares Support Vector Machines (LS-SVM), which is one of the most popular tools for regression and classification learning but confronts the loss of sparsity problem. After the sparse representation of LS-SVM is presented by compressed sensing, we exploit the support of bias term in the LS-SVM model with the ${\rm IHT}^{\mu }$-PKS algorithm. Experimental results on classification problems show that ${\rm IHT}^{\mu }$-PKS outperforms other approaches to computing the sparse LS-SVM classifier.
LA - eng
KW - iterative hard thresholding; signal reconstruction; classification problem; least squares support vector machine
UR - http://eudml.org/doc/299524
ER -

References

top
  1. Axiotis, K., Sviridenko, M., Sparse convex optimization via adaptively regularized hard thresholding, J. Mach. Learn. Res. 22 (2021), Article ID 122, 47 pages. (2021) Zbl07370639MR4279773
  2. Baraniuk, R. G., Cevher, V., Duarte, M. F., Hegde, C., 10.1109/TIT.2010.2040894, IEEE Trans. Inf. Theory 56 (2010), 1982-2001. (2010) Zbl1366.94215MR2654489DOI10.1109/TIT.2010.2040894
  3. Besson, A., Perdios, D., Wiaux, Y., Thiran, J.-P., 10.110/LSP.2018.2880571, IEEE Signal Process. Lett. 26 (2019), 84-88. (2019) DOI10.110/LSP.2018.2880571
  4. Blumensath, T., Davies, M. E., 10.1007/s00041-008-9035-z, J. Fourier Anal. Appl. 14 (2008), 629-654. (2008) Zbl1175.94060MR2461601DOI10.1007/s00041-008-9035-z
  5. Blumensath, T., Davies, M. E., 10.1016/j.acha.2009.04.002, Appl. Comput. Harmon. Anal. 27 (2009), 265-274. (2009) Zbl1174.94008MR2559726DOI10.1016/j.acha.2009.04.002
  6. Blumensath, T., Davies, M. E., 10.1109/JSTSP.2010.2042411, IEEE J. Selected Topics Signal Process. 4 (2010), 298-309. (2010) DOI10.1109/JSTSP.2010.2042411
  7. Candès, E. J., Tao, T., 10.1109/TIT.2005.858979, IEEE Trans. Inf. Theory 51 (2005), 4203-4215. (2005) Zbl1264.94121MR2243152DOI10.1109/TIT.2005.858979
  8. Carrillo, R. E., Polania, L. F., Barner, K. E., 10.1109/ICASSP.2010.5495901, IEEE International Conference on Acoustics, Speech and Signal Processing IEEE, Los Alamitos (2010), 3654-3657. (2010) DOI10.1109/ICASSP.2010.5495901
  9. Carrillo, R. E., Polania, L. F., Barner, K. E., 10.1109/ICASSP.2011.5947236, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) IEEE, Los Alamitos (2011), 4028-4031. (2011) DOI10.1109/ICASSP.2011.5947236
  10. Chen, S. S., Donoho, D. L., Saunders, M. A., 10.1137/S003614450037906X, SIAM Rev. 43 (2001), 129-159. (2001) Zbl0979.94010MR1854649DOI10.1137/S003614450037906X
  11. Cui, K., Song, Z., Han, N., 10.1142/S021759592050013X, Asia-Pac. J. Oper. Res. 37 (2020), Article ID 2050013, 20 pages. (2020) Zbl1457.94037MR4107957DOI10.1142/S021759592050013X
  12. Foucart, S., 10.1016/j.acha.2009.10.004, Appl. Comput. Harmon. Anal. 29 (2010), 97-103. (2010) Zbl1198.41011MR2647014DOI10.1016/j.acha.2009.10.004
  13. Foucart, S., 10.1137/100806278, SIAM J. Numer. Anal. 49 (2011), 2543-2563. (2011) Zbl1242.65060MR2873246DOI10.1137/100806278
  14. Foucart, S., Rauhut, H., 10.1007/978-0-8176-4948-7, Applied and Numerical Harmonic Analysis. Birkhäuser, New York (2013). (2013) Zbl1315.94002MR3100033DOI10.1007/978-0-8176-4948-7
  15. Jacques, L., 10.1016/j.sigpro.2010.05.025, Signal Process. 90 (2010), 3308-3312. (2010) Zbl1197.94063DOI10.1016/j.sigpro.2010.05.025
  16. Khajehnejad, M. A., Xu, W., Avestimehr, A. S., Hassibi, B., 10.1109ISIT.2009.5205716, IEEE International Symposium on Information Theory IEEE, Los Alamitos (2009), 483-487. (2009) MR2816477DOI10.1109ISIT.2009.5205716
  17. Khera, S., Singh, S., 10.1088/1742-6596/2327/1/012040, J. Phys., Conf. Ser. 2327 (2022), Article ID 012040, 9 pages. (2022) DOI10.1088/1742-6596/2327/1/012040
  18. Li, Y., Lin, C., Zhang, W., 10.1016/j.neucom.2006.03.001, Neurocomputing 69 (2006), 1655-1658. (2006) DOI10.1016/j.neucom.2006.03.001
  19. Liu, H., Barber, R. Foygel, 10.1093/imaiai/iaz027, Inf. Inference 9 (2020), 899-933. (2020) Zbl1473.90162MR4188230DOI10.1093/imaiai/iaz027
  20. Mall, R., Suykens, J. A. K., 10.1109/TNNLS.2014.2333879, IEEE Trans. Neural Netw. Learn. Syst. 26 (2015), 1086-1097. (2015) MR3454265DOI10.1109/TNNLS.2014.2333879
  21. Shao, Y.-H., Li, C.-N., Liu, M.-Z., Wang, Z., Deng, N.-Y., 10.1016/j.patcog.2018.01.016, Pattern Recognition 78 (2018), 167-181. (2018) MR3621691DOI10.1016/j.patcog.2018.01.016
  22. Shen, J., Li, P., A tight bound of hard thresholding, J. Mach. Learn. Res. 18 (2018), Article ID 208, 42 pages. (2018) Zbl1473.62287MR3827096
  23. Suykens, J. A. K., Lukas, L., Vandewalle, J., 10.1109/ISCAS.2000.856439, IEEE International Symposium on Circuits and Systems (ISCAS). Vol. 2 IEEE, Los Alamitos (2000), 757-760. (2000) DOI10.1109/ISCAS.2000.856439
  24. Vaswani, N., Lu, W., 10.1109/TSP.2010.2051150, IEEE Trans. Signal Process. 58 (2010), 4595-4607. (2010) Zbl1392.94045MR2752724DOI10.1109/TSP.2010.2051150
  25. Borries, R. von, Miosso, C. J., Potes, C., 10.1109/CAMSAP.2007.4497980, International Workshop on Computational Advances in Multi-Sensor Adaptive Processing IEEE, Los Alamitos (2007), 121-124. (2007) DOI10.1109/CAMSAP.2007.4497980
  26. Wang, X.-Z., Xing, H.-J., Li, Y., Hua, Q., Dong, C.-R., Pedrycz, W., 10.1109/TFUZZ.2014.2371479, IEEE Trans. Fuzzy Syst. 23 (2015), 1638-1654. (2015) DOI10.1109/TFUZZ.2014.2371479
  27. Yang, J., Bouzerdoum, A., Phung, S. L., 10.1109/ICASSP.2010.5495015, IEEE International Conference on Acoustics, Speech and Signal Processing IEEE, Los Alamitos (2010), 2054-2057. (2010) MR0642901DOI10.1109/ICASSP.2010.5495015
  28. Yang, J., Ma, J., 10.1109/CIDM.2014.7008688, IEEE Symposium on Computational Intelligence and Data Mining (CIDM) IEEE, Los Alamitos (2014), 345-350. (2014) DOI10.1109/CIDM.2014.7008688
  29. Yu, M., Gupta, V., Kolar, M., 10.1214/19-EJS1658, Electron. J. Stat. 14 (2020), 413-457. (2020) Zbl1434.90161MR4054252DOI10.1214/19-EJS1658
  30. Zhang, X., Xu, W., Cui, Y., Lu, L., Lin, J., 10.1109/ACCESS.2019.2955759, IEEE Access 7 (2019), 175554-175563. (2019) DOI10.1109/ACCESS.2019.2955759
  31. Zhao, Y.-B., Luo, Z.-Q., Improved rip-based bounds for guaranteed performance of two compressed sensing algorithms, Available at https://arxiv.org/abs/2007.01451 (2020), 10 pages. (2020) MR4577493

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.