Sparse Reconstruction by Separable Approximation

By Stephen J. Wright, Robert D. Nowak, Mário A. T. Figueiredo. 2008

2,037 citations recorded by the source corpus.

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 2) error term added to a sparsity-inducing (usually lscr1) 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 lscr2-lscr1 case, our framework yields efficient solution techniques for other regularizers, such as an lscrinfin 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 lscr2-lscr1 problem, as well as being efficient on problems with other separable regularization terms.

Subfields: Biomedical Engineering, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Interpretable Recurrent Neural Networks Using Sequential Sparse Recovery (2016, methodology): “…, such as fast ISTA (FISTA) [20], which combines Nesterov’s adaptive step size method [21] with a gradual decrease in λ ( k ) , and sparse reconstruction by separable approximation (SparSA) [22], which combines Barzilai-Borwein gradient step size adjustment [23] with a gradual decrease in λ ( k ) .”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “This is the case of many gradient-based or proximal methods [3, 14, 28, 45, 54], expectation-maximization (EM) algorithms in statistics [20, 42], difference-of-convex (DC) programming [30], boosting [13, 19], some variational Bayes techniques used in machine learning [53], and the mean-shift algorit”
A Singular Value Thresholding Algorithm for Matrix Completion (2008, methodology): “One could then use a continuation method as in [50] to increase the value of τ sequentially according to a schedule τ 0 , τ 1 , . . . , and use the solution to the previous problem with τ = τ i − 1 as an initial guess for the solution to the current problem with τ = τ i (warm starting).”
Optimization with Sparsity-Inducing Penalties (2011, background): “We will show in this section that, in fact, the primal problem corresponding exactly to MKL (i.e., Eq.”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, background): “Increasing λ encourages the solution of (1) to be sparser [26].”
Parallel Coordinate Descent for L1-Regularized Loss Minimization (2011, neutral): “SpaRSA (Wright et al., 2009) is an accelerated iterative shrinkage/thresholding algorithm which solves a sequence of quadratic approximations of the objective.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “, [21, 208, 48] and numerous references therein) and in the machine learning communities (see, e.”
Multi-Stage Multi-Task Feature Learning (2012, neutral): “Therefore, W ⋆ is a critical point of Eq.”
Sample size selection in optimization methods for machine learning (2012, background): “1) (see for example [32, 15, 12, 4, 33, 14, 13]) and have proven to be very effective for many online applications.”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, methodology): “When P is the 1-norm or has the block-separable form (21), the new point xk+1 can be found in closed form, which is a key advantage of this method for large-scale optimization; see [147,152] and references therein.”
Inexact Coordinate Descent: Complexity and Preconditioning (2013, methodology): “Applications where such problems arise, and where first-order methods have proved successful, include machine learning [1,2], compressive sensing [3,4], group lasso [5,6], matrix completion [7,8], and truss topology design [9].”
Composite objective mirror descent (2010, background): “Some notable examples include Wright et al. (2009); Nesterov (2007); Tseng (2009).”
Distributed Sparse Linear Regression (2010, neutral): “Other approaches based on variable decoupling have been proposed by [17] and [35].”
Hyperspectral Image Classification Based on Structured Sparse Logistic Regression and Three-Dimensional Wavelet Texture Features (2013, methodology): “For group lasso regularization, the analytical solution for each group of variables is [49]”
Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization (2011, methodology): “We can efficiently compute an analytic solution to this problem for several notable choices of h, including the case of `1-regularization and disjoint group `1-regularization [5, 6].”