Gradient-based methods for sparse recovery. (English) Zbl 1209.90266
Summary: The convergence rate is analyzed for the sparse reconstruction by separable approximation (SpaRSA) algorithm for minimizing a sum \(f(\text{x})+\psi(\text{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.
MSC:
90C06 | Large-scale problems in mathematical programming |
90C25 | Convex programming |
65Y20 | Complexity and performance of numerical algorithms |
94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |