The Moreau envelope based efficient first-order methods for sparse recovery

Sparse recovery from indirectly under-sampled or possibly noisy data is a burgeoning topic drawing the attention of many researchers. Since sparse recovery problems can be cast as a class of the constrained convex optimization models which minimize a nonsmooth convex objection function in a convex closed set, fast and efficient methods for solving the constrained optimization models are highly needed. By introducing the indicator functions related to constrained sets in sparse recovery models, we reformulate these models as two general unconstrained optimization problems. To develop fast first-order methods, two smoothing approaches are proposed based on the Moreau envelope: smoothing the related indicator functions or the objection functions. By using the first smoothing approach, we obtain more proper unconstrained models for sparse recovery from noisy data. Fast iterative shrinkage-thresholding algorithm (FISTA) is applied to solve the smoothed models. When smoothing the objection functions, we propose an efficient first-order method based on FISTA to establish the rate of convergence of order O(logkk) for the iterative sequence of values of the original objective functions. Numerical experiments have demonstrated that the two proposed smoothing methods are comparable to the state-of-the-art first-order methods with respect to accuracy and speed when applied to the sparse recovery problems such as compressed sensing, matrix completion, and robust and stable principal component analysis.