SPGL1

SPGL1 is a solver for large-scale one-norm regularized least squares.

It is designed to solve any of the following three problems:

  1. Basis pursuit denoise (BPDN):
\[min \quad ||\mathbf{x}||_1 \quad subj. to \quad ||\mathbf{A}\mathbf{x} - \mathbf{b}||_2 <= \sigma\]
  1. Basis pursuit (BP):
\[min \quad ||\mathbf{x}||_1 \quad subj. to \quad \mathbf{A}\mathbf{x} = \mathbf{b}\]
  1. Lasso:
\[min \quad ||\mathbf{A}\mathbf{x} - \mathbf{b}||_2 \quad subj. to \quad ||\mathbf{x}||_1 <= \tau\]

The matrix \(\mathbf{A}\) can be defined explicitly, or as a scipy.sparse.linalg.LinearOperator that returns both both \(\mathbf{Ax}\) and \(\mathbf{A}^H\mathbf{b}\).

SPGL1 can solve these three problems in both the real and complex domains.

References

The algorithm implemented by SPGL1 is described in these two papers:

  • E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. on Scientific Computing, 31(2):890-912, November 2008
  • E. van den Berg and M. P. Friedlander, Sparse optimization with least-squares constraints, Tech. Rep. TR-2010-02, Dept of Computer Science, Univ of British Columbia, January 2010

History

SPGL1 has been initially implemented in MATLAB by E. van den Berg and M. P. Friedlander. This project is aimed at porting of their algorithm in Python. Small modifications are implemented in some areas of the code where more appropriate implementation choices were identified for the Python programming language.

Installation

Python 3.5 or greater is required. This package may also work for Python 2.7 or greater, however we do not provide any guarantee neither we will make any effort to maintain back compatibility with Python 2.

From PyPI

To install spgl1 within your current environment, simply type:

>> pip install spgl1

From source

First of all clone the repository. To install spgl1 within your current environment, simply type:

>> make install

or as a developer:

>> make dev-install

To install spgl1 in a new conda environment, type:

>> make install_conda

or as a developer:

>> make dev-install_conda

SPGL1 API

Main Solver

spgl1(A, b[, tau, sigma, x0, fid, …]) SPGL1 solver.

Other Solvers

oneprojector(b, d, tau) One projector.
spg_bp(A, b, **kwargs) Basis pursuit (BP) problem.
spg_bpdn(A, b, sigma, **kwargs) Basis pursuit denoise (BPDN) problem.
spg_lasso(A, b, tau, **kwargs) LASSO problem.
spg_mmv(A, B[, sigma]) MMV problem.

Contributors