Sparse reconstruction by separable approximation

Finding sparse approximate solutions to large underdetermined linear systems of equations is a common problem in signal/image processing and statistics. Basis pursuit, the least absolute shrinkage and selection operator (LASSO), wavelet-based deconvolution and reconstruction, and compressed sensing (CS) are a few well-known areas in which problems of this type appear. One standard approach is to minimize an objective function that includes a quadratic (pound ₂) error term added to a sparsity-inducing (usually pound ₁) regularizer. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex, sparsity-inducing function. We propose iterative methods in which each step is an optimization subproblem involving a separable quadratic term (diagonal Hessian) plus the original sparsity-inducing term. Our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. In addition to solving the standard pound ₂ - pound ₁ case, our approach handles other problems, e.g., pound _p regularizers with p ne 1, or group-separable (GS) regularizers. Experiments with CS problems show that our approach provides state-of-the-art speed for the standard pound ₂ - pound ₁ problem, and is also efficient on problems with GS regularizers.

1. INTRODUCTION

There is growing interest in finding fast algorithms for solving the convex unconstrained optimization problem $$\min_{{\bf x}\in {\BB R}^{n}}{1\over 2}\Vert {\bf y}-{\bf Ax}\Vert_{2}^{2}+\tau\Vert {\bf x}\Vert_{1}, \eqno \hbox{(1)}$$ where (usually and . Problems of the form (1) can be used to identify a sparse approximate solution to the underdetermined system Ax, and have become familiar over the past three decades, particularly in signal processing. Several algorithms have been proposed for solving (1) and its variants; see [15] for a recent overview of the work in this domain.