Skip to content

Port of SPGL1 to python

License

LGPL-2.1, LGPL-2.1 licenses found

Licenses found

LGPL-2.1
License.md
LGPL-2.1
COPYING
Notifications You must be signed in to change notification settings

epnev/SPGL1_python_port

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

SPGL1: Spectral Projected Gradient for L1 minimization
------------------------------------------------------

1. Introduction
===============

Thank you for downloading the SPGL1 solver!  SPGL1 is a python (or Matlab) 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):
   minimize  ||x||_1  subject to  ||Ax - b||_2 <= sigma,

2. Basis pursuit (BP):
   minimize   ||x||_1  subject to  Ax = b
 
3. Lasso:
   minimize  ||Ax - b||_2  subject to  ||x||_1 <= tau,

The matrix A can be defined explicitly, or as an operator (i.e., a function) that return both both Ax and A'y.  SPGL1 can solve these three problems in both the real and complex domains.

Original home page: http://www.cs.ubc.ca/labs/scl/spgl1/

Code ported by David Relyea ([email protected]). Direct kudos to that address.
For any questions and concerns, also use that address.
For blame, hostility, or general ill will, contact your local government representative.

2. Quick start
==============

Run the spgldemoo.py in a python shell. You need numpy and matplotlib and scipy.

This script illustrates various uses of SPGL1:

- Solve (BPDN) for some sigma > 0
- Solve (Lasso)
- Solve (BP)
- Solve a (BP) problem in complex variables
- Sample the entire Pareto frontier (i.e., ||Ax-b||_2 vs ||x||_1)
  for a small test problem.

3. Installation
===============

3.01 python
------------------

This entire codebase was ported in a few nights to python. It requires both python and numpy, which you have on your computer. If you’ve managed to get to this point and you don’t have numpy, you are a unique individual. Go get numpy.

3.1  C interface
------------------

I have not yet coded up C versions of the core routines, so this code is only incredibly fast and not blazing-hot habañero fast. I’ll do that soon.


4. References
=============

The algorithm implemented by SPGL1 is described in the paper

- 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

- Sparse optimization with least-squares constraints E. van den Berg
  and M. P. Friedlander, Tech. Rep. TR-2010-02, Dept of Computer
  Science, Univ of British Columbia, January 2010

About

Port of SPGL1 to python

Resources

License

LGPL-2.1, LGPL-2.1 licenses found

Licenses found

LGPL-2.1
License.md
LGPL-2.1
COPYING

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%