Robust sparse recovery via non-convex optimization

Though the convex relaxation technique has become a great success for sparse recovery, numerous researches hint that utilizing non-convex penalties might induce better sparsity. Up until now, those promising non-convex algorithms still lack theoretical convergence guarantees from the initial solution to the global optimum. This paper aims to provide performance guarantees of a non-convex approach for sparse recovery. A class of sparsity-inducing penalties is introduced with characterization of the non-convexity, and a simple algorithm is proposed to solve the corresponding optimization problem. Theoretical analysis reveals that if the non-convexity of the penalty is below a threshold (which is in inverse proportion to the distance between the initial solution and the sparse signal), the recovered solution has recovery error linear in both the step size and the noise term. Numerical simulations are implemented to test the performance of the proposed approach.