Fast Sparse Recovery Algorithms

Compressive sensing, i.e., reconstructing the sparse signal from a few linear observations, has found many applications in signal and image processing, machine learning and so on. Due to its important theoretical and practical values, kinds of algorithms are developed. These algorithms can be mainly classed into three groups: convex relaxations, greedy methods, and hard thresholding algorithms. However, as the scale increases,these algorithms are all affected in terms of efficiency. In these paper, we employ some advanced techniques to deal with such problems. The main innovation and work include:Firstly, we propose the preconditionally linearized Bregman algorithms and provide a theoretical proof. The numerical results provided in this paper coincide with the proof.We extend the same methodology to inconsistent augmented ?1model, and propose a corresponding algorithm.Secondly, for solving the l1-l1 minimization problem, we propose a Fast Iterative Shrinkage Thresholding Algorithm. The proposed algorithm consists of two steps: in the first step, we apply the smoothing technique to l1-l1minimization; and in the second step we solve the smoothed problem by fast iterative shrinkage thresholding algorithm.With the help of restarts technique, we further accelerate the reweighted FISTA algorithm. Compared with some provable and efficient existing methods, the methods proposed in this paper enjoys faster speed, less parameters and that the convergent analysis does not need any assumption of A. On the computational level, numerical experiments on sparse signal recovery demonstrate the efficiency of the proposed methods.Thirdly, we further develop accelerated algorithms to deal with the LLS which make large scale HTP possible. Theoretically, we prove that all these algorithms are convergent provided the sensing matrix has suitable restricted isometry property. Numerical experiments on sparse signal recovery demonstrate the efficiency of the proposed methods.Last, we propose the Projective Hard Thresholding Pursuit for nonnegative sparse signal recovery. Theoretically, we prove that the proposed algorithm is convergent provided the sensing matrix has suitable restricted isometry property. Numerical experiments on sparse nonnegative signal recovery demonstrate the efficiency of the proposed method.