Article
| Title: | A tight bound of modified iterative hard thresholding algorithm for compressed sensing (English) |
| Author: | Ma, Jinyao |
| Author: | Zhang, Haibin |
| Author: | Yang, Shanshan |
| Author: | Jiang, Jiaojiao |
| Language: | English |
| Journal: | Applications of Mathematics |
| ISSN: | 0862-7940 (print) |
| ISSN: | 1572-9109 (online) |
| Volume: | 68 |
| Issue: | 5 |
| Year: | 2023 |
| Pages: | 623-642 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | 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. (English) |
| Keyword: | iterative hard thresholding |
| Keyword: | signal reconstruction |
| Keyword: | classification problem |
| Keyword: | least squares support vector machine |
| MSC: | 34B16 |
| MSC: | 34C25 |
| MSC: | 90C31 |
| DOI: | 10.21136/AM.2023.0221-22 |
| . | |
| Date available: | 2023-10-05T15:12:03Z |
| Last updated: | 2023-10-09 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/151836 |
| . | |
| Reference: | [1] Axiotis, K., Sviridenko, M.: Sparse convex optimization via adaptively regularized hard thresholding.J. Mach. Learn. Res. 22 (2021), Article ID 122, 47 pages. Zbl 07370639, MR 4279773 |
| Reference: | [2] Baraniuk, R. G., Cevher, V., Duarte, M. F., Hegde, C.: Model-based compressive sensing.IEEE Trans. Inf. Theory 56 (2010), 1982-2001. Zbl 1366.94215, MR 2654489, 10.1109/TIT.2010.2040894 |
| Reference: | [3] Besson, A., Perdios, D., Wiaux, Y., Thiran, J.-P.: Joint sparsity with partially known support and application to ultrasound imaging.IEEE Signal Process. Lett. 26 (2019), 84-88. 10.110/LSP.2018.2880571 |
| Reference: | [4] Blumensath, T., Davies, M. E.: Iterative thresholding for sparse approximations.J. Fourier Anal. Appl. 14 (2008), 629-654. Zbl 1175.94060, MR 2461601, 10.1007/s00041-008-9035-z |
| Reference: | [5] Blumensath, T., Davies, M. E.: Iterative hard thresholding for compressed sensing.Appl. Comput. Harmon. Anal. 27 (2009), 265-274. Zbl 1174.94008, MR 2559726, 10.1016/j.acha.2009.04.002 |
| Reference: | [6] Blumensath, T., Davies, M. E.: Normalized iterative hard thresholding: Guaranteed stability and performance.IEEE J. Selected Topics Signal Process. 4 (2010), 298-309. 10.1109/JSTSP.2010.2042411 |
| Reference: | [7] Candès, E. J., Tao, T.: Decoding by linear programming.IEEE Trans. Inf. Theory 51 (2005), 4203-4215. Zbl 1264.94121, MR 2243152, 10.1109/TIT.2005.858979 |
| Reference: | [8] Carrillo, R. E., Polania, L. F., Barner, K. E.: Iterative algorithms for compressed sensing with partially known support.IEEE International Conference on Acoustics, Speech and Signal Processing IEEE, Los Alamitos (2010), 3654-3657. 10.1109/ICASSP.2010.5495901 |
| Reference: | [9] Carrillo, R. E., Polania, L. F., Barner, K. E.: Iterative hard thresholding for compressed sensing with partially known support.IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) IEEE, Los Alamitos (2011), 4028-4031. 10.1109/ICASSP.2011.5947236 |
| Reference: | [10] Chen, S. S., Donoho, D. L., Saunders, M. A.: Atomic decomposition by basis pursuit.SIAM Rev. 43 (2001), 129-159. Zbl 0979.94010, MR 1854649, 10.1137/S003614450037906X |
| Reference: | [11] Cui, K., Song, Z., Han, N.: Fast thresholding algorithms with feedbacks and partially known support for compressed sensing.Asia-Pac. J. Oper. Res. 37 (2020), Article ID 2050013, 20 pages. Zbl 1457.94037, MR 4107957, 10.1142/S021759592050013X |
| Reference: | [12] Foucart, S.: A note on guaranteed sparse recovery via $\ell_1$-minimization.Appl. Comput. Harmon. Anal. 29 (2010), 97-103. Zbl 1198.41011, MR 2647014, 10.1016/j.acha.2009.10.004 |
| Reference: | [13] Foucart, S.: Hard thresholding pursuit: An algorithm for compressive sensing.SIAM J. Numer. Anal. 49 (2011), 2543-2563. Zbl 1242.65060, MR 2873246, 10.1137/100806278 |
| Reference: | [14] Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing.Applied and Numerical Harmonic Analysis. Birkhäuser, New York (2013). Zbl 1315.94002, MR 3100033, 10.1007/978-0-8176-4948-7 |
| Reference: | [15] Jacques, L.: A short note on compressed sensing with partially known signal support.Signal Process. 90 (2010), 3308-3312. Zbl 1197.94063, 10.1016/j.sigpro.2010.05.025 |
| Reference: | [16] Khajehnejad, M. A., Xu, W., Avestimehr, A. S., Hassibi, B.: Weighted $\ell_1$ minimization for sparse recovery with prior information.IEEE International Symposium on Information Theory IEEE, Los Alamitos (2009), 483-487. MR 2816477, 10.1109ISIT.2009.5205716 |
| Reference: | [17] Khera, S., Singh, S.: Estimation of channel for millimeter-wave hybrid massive MIMO systems using Orthogonal Matching Pursuit (OMP).J. Phys., Conf. Ser. 2327 (2022), Article ID 012040, 9 pages. 10.1088/1742-6596/2327/1/012040 |
| Reference: | [18] Li, Y., Lin, C., Zhang, W.: Improved sparse least-squares support vector machine classifiers.Neurocomputing 69 (2006), 1655-1658. 10.1016/j.neucom.2006.03.001 |
| Reference: | [19] Liu, H., Barber, R. Foygel: Between hard and soft thresholding: Optimal iterative thresholding algorithms.Inf. Inference 9 (2020), 899-933. Zbl 1473.90162, MR 4188230, 10.1093/imaiai/iaz027 |
| Reference: | [20] Mall, R., Suykens, J. A. K.: Very sparse LSSVM reductions for large-scale data.IEEE Trans. Neural Netw. Learn. Syst. 26 (2015), 1086-1097. MR 3454265, 10.1109/TNNLS.2014.2333879 |
| Reference: | [21] Shao, Y.-H., Li, C.-N., Liu, M.-Z., Wang, Z., Deng, N.-Y.: Sparse $L_q$-norm least squares support vector machine with feature selection.Pattern Recognition 78 (2018), 167-181. MR 3621691, 10.1016/j.patcog.2018.01.016 |
| Reference: | [22] Shen, J., Li, P.: A tight bound of hard thresholding.J. Mach. Learn. Res. 18 (2018), Article ID 208, 42 pages. Zbl 1473.62287, MR 3827096 |
| Reference: | [23] Suykens, J. A. K., Lukas, L., Vandewalle, J.: Sparse approximation using least squares support vector machines.IEEE International Symposium on Circuits and Systems (ISCAS). Vol. 2 IEEE, Los Alamitos (2000), 757-760. 10.1109/ISCAS.2000.856439 |
| Reference: | [24] Vaswani, N., Lu, W.: Modified-CS: Modifying compressive sensing for problems with partially known support.IEEE Trans. Signal Process. 58 (2010), 4595-4607. Zbl 1392.94045, MR 2752724, 10.1109/TSP.2010.2051150 |
| Reference: | [25] Borries, R. von, Miosso, C. J., Potes, C.: Compressed sensing using prior information.International Workshop on Computational Advances in Multi-Sensor Adaptive Processing IEEE, Los Alamitos (2007), 121-124. 10.1109/CAMSAP.2007.4497980 |
| Reference: | [26] Wang, X.-Z., Xing, H.-J., Li, Y., Hua, Q., Dong, C.-R., Pedrycz, W.: A study on relationship between generalization abilities and fuzziness of base classifiers in ensemble learning.IEEE Trans. Fuzzy Syst. 23 (2015), 1638-1654. 10.1109/TFUZZ.2014.2371479 |
| Reference: | [27] Yang, J., Bouzerdoum, A., Phung, S. L.: A training algorithm for sparse LS-SVM using compressive sampling.IEEE International Conference on Acoustics, Speech and Signal Processing IEEE, Los Alamitos (2010), 2054-2057. MR 0642901, 10.1109/ICASSP.2010.5495015 |
| Reference: | [28] Yang, J., Ma, J.: A sparsity-based training algorithm for Least Squares SVM.IEEE Symposium on Computational Intelligence and Data Mining (CIDM) IEEE, Los Alamitos (2014), 345-350. 10.1109/CIDM.2014.7008688 |
| Reference: | [29] Yu, M., Gupta, V., Kolar, M.: Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach.Electron. J. Stat. 14 (2020), 413-457. Zbl 1434.90161, MR 4054252, 10.1214/19-EJS1658 |
| Reference: | [30] Zhang, X., Xu, W., Cui, Y., Lu, L., Lin, J.: On recovery of block sparse signals via block compressive sampling matching pursuit.IEEE Access 7 (2019), 175554-175563. 10.1109/ACCESS.2019.2955759 |
| Reference: | [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. MR 4577493 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
