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

Ma, Jinyao ; Zhang, Haibin ; Yang, Shanshan ; Jiang, Jiaojiao

Applications of Mathematics, Tome 68 (2023) no. 5, pp. 623-642

Abstract (VO)

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.

Détail

DOI : 10.21136/AM.2023.0221-22

Classification : 34B16, 34C25, 90C31
Keywords: iterative hard thresholding; signal reconstruction; classification problem; least squares support vector machine