A Simple Homotopy Algorithm for Compressive Sensing

In this paper, we consider the problem of re-covering the s largest elements of an arbitrary vector from noisy measurements. Inspired by previous work, we develop an homotopy al-gorithm which solves the ℓ1-regularized least square problem for a sequence of decreasing values of the regularization parameter. Com-pared to the previous method, our algorithm is more efficient in the sense it only updates the solution once for each intermediate prob-lem, and more practical in the sense it has a simple stopping criterion by checking the s-parsity of the intermediate solution. Theoret-ical analysis reveals that our method enjoys a linear convergence rate in reducing the recov-ery error. Furthermore, our guarantee for re-covering the top s elements of the target vec-tor is tighter than previous results, and that for recovering the target vector itself matches the state of the art in compressive sensing.