Abstract: For the Backtracking-based Iterative Hard Thresholding algorithm (BIHT) has the problems of large number of iterations and too long reconstruction time, a Backtracking-based Conjugate Gradient Iterative Hard Thresholding algorithm (BCGIHT) was proposed. Firstly, the idea of backtracking was adopted in each iteration, and the support set of the previous iteration was combined with the current support set to form a candidate set. Then, a new support set was selected in the space spanned by the matrix columns corresponding to the candidate set, so as to reduce times that the support set was selected repeatedly and ensure that the correct support set was found quickly. Finally, according to the criteria of whether or not the support set of the last iteration was equal to the support set of the next iteration, gradient descent method or conjugate gradient method was used to be the optimization method, so as to accelerate the convergence of algorithm. The reconstruction experimental results of one-dimensional random Gaussian signals show that, the reconstruction success rate of BCGIHT is higher than that of BIHT and similar algorithms, and its reconstruction time is less than that of BIHT by at least 25%. The reconstruction experiment results of Pepper image show that, the reconstruction accuracy and the anti-noise performance of the proposed BCGIHT algorithm is comparable with BIHT and similar algorithms, and its reconstruction time is reduced by more than 50% compared with BIHT.

Key words: Compressed Sensing (CS), Backtracking-based Iterative Hard Thresholding algorithm (BIHT), conjugate gradient, reconstruction algorithm

摘要： 针对基于回溯的迭代硬阈值算法（BIHT）迭代次数多、重构时间长的问题，提出一种基于回溯的共轭梯度迭代硬阈值算法（BCGIHT）。首先，在每次迭代中采用回溯思想，将前一次迭代的支撑集与当前支撑集合并成候选集；然后，在候选集所对应的矩阵列张成的空间中选择新的支撑集，以此减少支撑集被反复选择的次数，确保正确的支撑集被快速找到；最后，根据前后迭代支撑集是否相等的准则来决定使用梯度下降法或共轭梯度法作为寻优方法，加速算法收敛。一维随机高斯信号重构实验结果表明，BCGIHT重构成功率高于BIHT及同类算法，重构时间低于BIHT 25%以上。Pepper图像重构实验结果表明，BCGIHT重构精度和抗噪性能与BIHT及同类算法相当，重构时间相较于BIHT减少50%以上。

关键词: 压缩感知, 基于回溯的迭代硬阈值算法, 共轭梯度, 重构算法