  In this paper, we present a novel yet simple homotopy proximal mapping
algorithm for compressive sensing. The algorithm adopts a simple proximal
mapping of the $\ell_1$ norm at each iteration and gradually reduces the
regularization parameter for the $\ell_1$ norm. We prove a global linear
convergence of the proposed homotopy proximal mapping (HPM) algorithm for
solving compressive sensing under three different settings (i) sparse signal
recovery under noiseless measurements, (ii) sparse signal recovery under noisy
measurements, and (iii) nearly-sparse signal recovery under sub-gaussian noisy
measurements. In particular, we show that when the measurement matrix satisfies
Restricted Isometric Properties (RIP), our theoretical results in settings (i)
and (ii) almost recover the best condition on the RIP constants for compressive
sensing. In addition, in setting (iii), our results for sparse signal recovery
are better than the previous results, and furthermore our analysis explicitly
exhibits that more observations lead to not only more accurate recovery but
also faster convergence. Compared with previous studies on linear convergence
for sparse signal recovery, our algorithm is simple and efficient, and our
results are better and provide more insights. Finally our empirical studies
provide further support for the proposed homotopy proximal mapping algorithm
and verify the theoretical results.
