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

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 δ3s−2k<132≈0.1768\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\delta _{3s - 2k}} < {1 \over {\sqrt {32}}} \approx 0.1768$$\end{document} to δ3s−2k<5−14\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\delta _{3s - 2k}} < {{\sqrt 5 - 1} \over 4}$$\end{document}, where δ3s−2k 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.