Gradient-Based Methods for Sparse Recovery

Abstract

The convergence rate is analyzed for the sparse reconstruction by separable approximation (SpaRSA) algorithm for minimizing a sum $f(\mathbf{x})+\psi(\mathbf{x})$, where f is smooth and $\psi$ is convex, but possibly nonsmooth. It is shown that if f is convex, then the error in the objective function at iteration k is bounded by $a/k$ for some a independent of k. Moreover, if the objective function is strongly convex, then the convergence is R-linear. An improved version of the algorithm based on a cyclic version of the BB iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.