The Viterbi Algorithm for Subset Selection

We study the problem of sparse recovery in an overcomplete dictionary. This problem has attracted considerable attention in signal processing, statistics, and computer science, and a variety of algorithms have been developed to recover the sparse vector. We propose a new method based on the computationally efficient Viterbi algorithm which is shown to achieve better performance than competing algorithms such as Orthogonal Matching Pursuit (OMP), Orthogonal Least-Squares (OLS), Multi-Branch Matching Pursuit (MBMP), Iterative Hard Thresholding (IHT), and l1 minimization. We also explore the relationship of the Viterbi-based approach with OLS.