From least squares to sparse: A non-convex approach with guarantee

This paper aims to provide theoretical guarantees via non-convex optimization for sparse recovery. It is shown that the sparse signal is the unique local optimal solution within a neighborhood, which contains the least squares solution if the sparsity-inducing penalties are not too non-convex. The idea of projected subgradient method is generalized to solve this non-convex optimization problem. A uniform approximate projection is applied in the projection step to make the algorithm more computationally tractable. The theoretical convergence analysis of the proposed method, approximate projected generalized gradient (APGG), is performed in the noisy scenario. The result reveals that if the non-convexity of the penalties is under a threshold, the bound of the recovery error is linear in both the noise bound and the step size. Numerical simulations are performed to test the performance of APGG and verify its theoretical analysis.