SGPL1: A solver for large-scale sparse reconstruction

Version 1.8, May 2013

SPGL1 is a Matlab solver for large-scale one-norm regularized least squares. It is designed to solve any of the following three problems:

basis pursuit denoise

$hbox{minimize} quad |x|_1 quadhbox{subect to}quad |Ax-b|_2 le sigma$

basis pursuit

$hbox{minimize} quad |x|_1 quadhbox{subect to}quad Ax=b$

Lasso

$hbox{minimize} quad |Ax-b|_2 quadhbox{subect to}quad |x| le tau$

SPGL1 relies only on matrix-vector operations and A^T y and accepts both explicit matrices and functions that evaluate these products. SPGL1 is suitable for problems that are in the complex domain. The theory underlying SPGL1 is described in these papers:

Probing the Pareto frontier for basis pursuit solutions E. van den Berg and M. P. Friedlander, SIAM J. on Scientific Computing, 31(2):890-912, November 2008 (pdf)
Sparse optimization with least-squares constraints E. van den Berg and M. P. Friedlander, SIAM J. on Optimization, SIAM J. on Optimization, 21(4):1201–1229, 2011 (pdf)

Group sparsity

In version 1.6, the core SPGL1 routine was generalized to solve the above three problems with |x|_1 replaced by any norm on . In order to do so, it requires that routines are provided for computing the

norm
corresponding dual norm
Euclidean projection

$hbox{project}(x;tau) := hbox{argmin}_p |p-x|_2 hbox{subject to} |p|letau$

This framework can be used to implement solvers for MMV and group-sparse BPDN (see below.) Also, Check out these demos.

Multiple measurement vectors (MMV)

The MMV version of BPDN currently implemented solves

$hbox{minimize}quad|X|_{1,2} quadhbox{subject to}quad |AX-B|_F le sigma$

where the mixed (1,2)-norm $|X|_{1,2}$ is defined by the sum of the two-norms of the rows of X.

Group-sparse BPDN

In group-sparse BPDN, each entry of is assigned to a group. Denoting by alpha_i the indices of group , the group-sparse BPDN problem is

$hbox{minimize}quadsum_i|x_{alpha_i}|_2 quadhbox{subject to}quad |Ax-b|_2lesigma$

Feedback

We would be delighted to hear from you if you find SPGL1 useful, or if you have any suggestions, contributions, or bug reports. Please send these to

Michael P. Friedlander (mpf@cs.ubc.ca)
Ewout van den Berg (ewout@stanford.edu)

License

SPGL1 is distributed under the GNU Public License.

Credits

This research is supported in part by an NSERC Discovery Grant and by an NSERC Collaborative Research and Development Grant (334810-05) that funds the DNOISE project.