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 (lscr ₂) error term added to a sparsity-inducing (usually lscr₁) regularizater. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex regularizer. We propose iterative methods in which each step is obtained by solving an optimization subproblem involving a quadratic term with diagonal Hessian (i.e., separable in the unknowns) plus the original sparsity-inducing regularizer; our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. Under mild conditions (namely convexity of the regularizer), we prove convergence of the proposed iterative algorithm to a minimum of the objective function. In addition to solving the standard lscr₂-lscr₁ case, our framework yields efficient solution techniques for other regularizers, such as an lscr_infin norm and group-separable regularizers. It also generalizes immediately to the case in which the data is complex rather than real. Experiments with CS problems show that our approach is competitive with the fastest known methods for the standard lscr₂-lscr₁ problem, as well as being efficient on problems with other separable regularization terms.

I. Introduction

IN this paper, we propose an approach for solving unconstrained optimization problems of the form

$$\min _{\bf x} \quad \phi ({\bf x}) := f({\bf x}) + \tau \, c({\bf x}) \eqno{\hbox{(1)}}$$ where is a smooth function, and , usually called the regularizer or regularization function, is finite for all , but usually nonsmooth and possibly also nonconvex. Problem (1) generalizes the now famous problem (called basis pursuit denoising (BPDN) in [15]) $$\min _{{\bf x}\in {\BBR}^{n}} \quad {{1}\over {2}}\Vert {\bf y} - {\bf A}{\bf x}\Vert _{2}^{2} + \tau \Vert {\bf x}\Vert _{1} \eqno{\hbox{(2)}}$$ where , (usually ), , denotes the standard Euclidean norm, and stands for the norm (for ), defined as . Problem (2) is closely related to the following two formulations: $$\min _{\bf x} \Vert {\bf y} - {\bf A}{\bf x}\Vert _{2}^{2} \quad {\rm subject to} \quad \Vert {\bf x}\Vert _{1} \leq T \eqno{\hbox{(3)}}$$ frequently referred to as the least absolute shrinkage and selection operator (LASSO) [70] and $$\min _{\bf x} \Vert {\bf x}\Vert _{1} \quad {\hbox {subject to}} \quad \Vert {\bf y} - {\bf A}{\bf x}\Vert _{2}^{2} \leq \varepsilon \eqno{\hbox{(4)}}$$ where and are nonnegative real parameters. These formulations can all be used to identify sparse approximate solutions to the underdetermined system , and have become familiar in the past few decades, particularly in statistics and signal/image processing contexts. A large amount of research has been aimed at finding fast algorithms for solving these formulations; early references include [16], [55], [66], [69]. for brief historical accounts on the use of the penalty in statistics and signal processing, see [59] and [71]. The precise relationship between (2), (3), and (4) is discussed in [39] and [75], for example.