Introduction

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{BP}_\sigma)\quad\hbox{minimize} \quad \|x\|_1^{} \quad\hbox{subject to}\quad\|Ax-b\|_2^{}\le\sigma

Basis pursuit

(\hbox{BP})\quad\hbox{minimize} \quad \|x\|_1^{} \quad\hbox{subject to}\quad Ax=b

Lasso

(\hbox{Lasso})\quad\hbox{minimize} \quad \|Ax-b\|_2^{} \quad\hbox{subject to}\quad \|x\|_1^{}\le\tau

SPGL1 relies only on matrix-vector operations Ax and A^Ty 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 the paper Probing the Pareto Frontier for basis pursuit solutions (pdf).

Group sparsity

In version 1.6, the core SPGL1 function was generalized to solve the above three problems with \|\cdot\|_1 replaced by any norm \|\cdot\|. In order to do so, it requires that functions are provided for computing: (1) the (primal) norm \|\cdot\|, (2) the corresponding dual norm \|\cdot\|_*, and (3), the (possibly weighted) Euclidean projection:

\hbox{project}(x,\tau) := \hbox{argmin}\quad \|p - x\|_2\quad\hbox{subject to}\quad\|p\| \le\tau

Using this framework we implemented two new solvers (for more information, see spgdemo.m and Extensions):

Multiple measurement vectors (MMV)

The MMV version of BPDN currently implemented solves

(\hbox{MMV}_\sigma)\quad\hbox{minimize} \quad \|X\|_{1,2}^{} \quad\hbox{subject to}\quad\|AX-B\|_{2,2}^{}\le\sigma,

where the mixed (p,q)-norm, \|X\|_{p,q}, (p,q\ge 1), defined by

\|X\|_{p,q} := \left(\sum_{i}^{m} \|X_i^T\|_q^p\right)^{1/p},

with X an m\times n matrix and where X_i denotes the i-th row of X. When weights are given, they apply to each row of X.

Group-sparse BPDN

In group-sparse BPDN each entry of x is assigned a group. Denoting by \Lambda_i the indices of group i, the group-sparse BPDN problem, for \sigma \ge 0, is given by:

(\hbox{Group}_\sigma)\quad\hbox{minimize} \quad \sum_i \|x_{\Lambda_i}\|_2^{} \quad\hbox{subject to}\quad\|Ax-b\|_2^{}\le\sigma.

It is assumed that the \Lambda_i are disjoint and that their union gives the set \{1,\ldots,n\}. When weights are given, they apply to each group.

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 (ewout78@cs.ubc.ca)

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.