SPGL1: A solver for large-scale sparse reconstruction

Version 1.9, April 2015

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

Fork me on GitHub

basis pursuit denoise
   hbox{minimize} quad |x|_1   quadhbox{subject to}quad   |Ax-b|_2 le sigma
basis pursuit
   hbox{minimize} quad |x|_1   quadhbox{subject to}quad   Ax=b
Lasso
   hbox{minimize} quad |Ax-b|_2   quadhbox{subject to}quad   |x| le tau

SPGL1 relies only on matrix-vector operations Ax 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 x. In order to do so, it requires that routines are provided for computing the

  1. norm |x|

  2. corresponding dual norm |x|_*

  3. 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 x is assigned to a group. Denoting by alpha_i the indices of group i, 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

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.