README

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

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

Thank you for downloading the SPGL1 solver!  SPGL1 is a 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 explicily, 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.


Home page: https://www.math.ucdavis.edu/~mpf/spgl1/


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

Start Matlab and make sure the working directory is set to the
directory containing the SPGL1 source files. When this is done, run

 >> spgdemo

at the Matlab prompt.  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.1  MEX interface
------------------

A vital component of SPGL1 is a routine (oneProjector.m) for
projecting vectors onto the one-norm ball.  The default distribution
includes a pure Matlab version of oneProjector which should work on
all platforms, and also a C-version of this routine that is more
efficient on large problems.  Precompiled MEX interfaces to the C
implementation of oneProjector are included for Windows
(oneProjector.dll), Linux/x86 (oneProjector.mexglx) and MacOSX/Intel
(oneProjector.mexmaci).  If you need to compile the MEX interface on
your own machine, run the following command at the Matlab prompt:

 >> spgsetup

or, equivalently, change to the "private" directory and issue the
command

 >> mex oneProjector.c oneProjector_core.c -output oneProjector -DNDEBUG

If the MEX interface cannot be found, SPGL1 falls back to the slower
Matlab implementation of oneProjector.

3.2  Path
---------

In order to use SPGL1 from any directory other than the one
containing the main spgl1 routine, add the SPGL1 package to your
default path:

 >> addpath <dir-name>

where <dir-name> is the location of spgl1.m.  You can also add this
command to your startup.m file.

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