Sparse recovery via nonconvex regularized M-estimators over ℓq-balls

Abstract The recovery properties of nonconvex regularized M -estimators are analysed, under the general sparsity assumption on the true parameter. In the statistical aspect, the recovery bound for any stationary point of the nonconvex regularized M -estimator is established under some regularity conditions. In the computational aspect, the proximal gradient method is used to solve the nonconvex optimization problem and is proved to achieve a linear convergence rate, by virtue of a slight decomposition of the objective function. In particular, for commonly-used regularizers such as SCAD and MCP, a simpler decomposition is applicable thanks to the assumption on the regularizer, which helps to construct the estimator with better recovery performance. In the asepct of application, theoretical consequences are obtained on the corrupted error-in-variables linear regression model by verifying the required conditions. Finally, statistical and computational results as well as advantages of the assumptions are demonstrated by several numerical experiments. Simulation results show remarkable consistency with the theory under high-dimensional scaling.