Abstract: Aiming at the problems of high complexity and long reconstruction time of Generalized Orthogonal Matching Pursuit(GOMP)algorithm,a Stochastic support selection based GOMP(StoGOMP)algorithm was proposed. Firstly,the strategy of stochastic support selection was introduced,and a probability value was randomly generated in each iteration. Then the generated probability value was compared to the preset probability value to determine the selection method of candidate support set. If this probability value was less than the preset probability value,the matching calculation method was adopted,otherwise,the random selection method was adopted. Finally,the residual was updated according to the obtained candidate supports. In this way,the balance between the complexity of the single iteration and the number of iterations of the algorithm was fully considered,and the computational cost of the algorithm was reduced. The experiment of one-dimensional random signal reconstruction shows that the number of samples required for StoGOMP algorithm to achieve 100% reconstruction success rate is reduced by 9. 5% compared with that for GOMP algorithm when the preset probability is 0. 5 and the sparsity is 20. The actual image reconstruction experiment shows that the proposed algorithm has the same reconstruction accuracy as GOMP algorithm,and the reconstruction time of the proposed algorithm is reduced by more than 27% compared to that of the original algorithm when the sampling rate is 0. 5,which indicates that StoGOMP algorithm can effectively reduce the signal reconstruction time.

Key words: compressed sensing, stochastic support selection, Generalized Orthogonal Matching Pursuit (GOMP), algorithm complexity, reconstruction algorithm

摘要： 针对广义正交匹配追踪（GOMP）算法复杂度高、重构时间长的问题，提出了一种基于随机支撑挑选的GOMP（StoGOMP）算法。首先引入随机支撑挑选的策略，在每次迭代中随机生成一个概率值。然后通过比较此概率值与预设概率值的大小来决定候选支撑集的挑选方式：若此概率值小于预设概率值，则采用匹配计算方式；否则，采用随机选择方式。最后根据得到的候选支撑来更新残差。这种方式充分考虑了算法单次迭代复杂度和迭代次数之间的平衡，减少了算法的计算量。一维随机信号重构实验结果表明，在预设概率值为0.5、稀疏度为20时，StoGOMP算法相较GOMP算法达到100%重构成功率所需的采样数减少了9.5%。实际图像重构实验结果表明，所提出的算法具有与GOMP算法相当的重构精度，且在采样率为0.5时，所提算法的重构时间相较于原算法减少了27%以上，这说明StoGOMP算法能够有效减少信号的重构时间。

关键词: 压缩感知, 随机支撑挑选, 广义正交匹配追踪, 算法复杂度, 重构算法