QSR: Q-Learning Based Algorithm of Support Recovery for Sparse Signals

Within a number of compressed sensing (CS) problems, support recovery of sparse signals is the primary task that needs to be performed. In this paper, we propose a Q-learning based algorithm of support recovery (QSR) for sparse signals, which treats the atomic selection in traditional greedy CS algorithms as Markov Decision Process (MDP) in reinforcement learning (RL). We adopt parallel computing to address "the curse of dimensionality" in Q-learning, dividing the overall RL problem into multiple subproblems. The computational complexity can thus significantly decrease, which grows linearly with the increase of signal length. Experiments show that the proposed algorithm performs closely to other CS algorithms when dealing with high sparsity level signals and it has better performance when dealing with low sparsity level signals.