# SPGL1

April 2015

GitHub Python Version Homepage

# A Matlab solver for sparse optimization

Python version contributed by David Relyea.

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*: $$\text{minimize}\ \Vert x \Vert_1 \text{ subject to } | \Vert Ax - b \Vert_2 \leq \sigma$$*basis pursuit*: $$\text{minimize}\ \Vert x \Vert_1 \text{ subject to } Ax = b$$*Lasso*: $$\text{minimize}\ \Vert Ax - b \Vert_2 \text{ subject to } \Vert x \Vert \leq \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 \(\Vert x\Vert_1\) replaced by any norm on \(x\). In order to do so, it requires that routines are provided for computing the

- norm \(\Vert x\Vert\)
- corresponding dual norm \(\Vert x\Vert_*\)
- Euclidean projection $$ \text{project}(x; \tau) := \text{argmin}_p \{ \Vert p - x \Vert_2 \mid \Vert p \Vert \leq \tau\} $$

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 the problem $$\text{minimize}\ \Vert X \Vert_{1,2} \text{ subject to }\Vert AX - B \Vert_F \leq \sigma$$

where the mixed (1,2)-norm \(\Vert X\Vert_{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

minimize \( \sum_i \Vert X_{\alpha_i} \Vert_2 \text{ subject to } \Vert Ax - b \Vert_2 \leq \sigma.\)

## 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 (vandenberg.ewout@gmail.com)

## License

SPGL1 is distributed under the GNU Public License.

## Credits

This research is supported in part by an NSERC Discovery Grant and by a grant from the Office of Naval Research (N00014-17-1-2009).