A simulated annealing algorithm for sparse recovery by l0 minimization

This paper addresses the sparse recovery problem by l0 minimization, which is of central importance in the compressed sensing theory. We model the problem as a combinatorial optimization problem and present a novel algorithm termed SASR based on simulated annealing (SA) and some greedy pursuit (GP) algorithms. In SASR, the initial solution is designed using the simple thresholding algorithm, and the generating mechanism is designed using the strategies existed in the subspace pursuit algorithm and the compressed sampling matching pursuit algorithm. On both the random Gaussian data and the face recognition task, the numerical simulation results illustrate the efficiency of SASR. Compared with the existing sparse recovery algorithms, SASR is more efficient in finding global optimums and performs relatively fast in some good cases. That is, SASR inherits the advantage of SA in finding global optimums and the advantage of GP in fast speed to some extent.