Systems Optimization Laboratory

ASP: Sparse Optimization

• AUTHORS: Michael Friedlander and Michael Saunders.
• CONTENTS: A set of Matlab routines for solving several variations of the sparse optimization problem \begin{align*} \text{minimize } & \lambda \|x\|_1 + \frac12 \|Ax-b\|_2^2, \end{align*} where $$A$$ may be an explicit dense or sparse rectangular matrix or an operator for computing $$Av$$ and $$A^T u$$ for given vectors $$v, u$$.
There are functions for the following problems:

• basis pursuit denoising (BPDN), including $$Ax=b$$ (BP)
• orthogonal matching pursuit
• homotopy version of basis pursuit denoising
• reweighted basis pursuit for approximating 0-norm solutions
• sequential compressed sensing (adding rows to $$A$$ and $$b$$)
• nonnegative least-squares
• sparse-residual and sparse-solution regression
• generalized Lasso for sparsity in $$Bx$$

For certain matching values of $$\lambda$$ and $$\tau$$, BPDN is equivalent to the Lasso problem: minimize $$\frac12 \|Ax-b\|_2^2$$ subject to $$\|x\|_1 \le \tau$$.

• REFERENCES:
[1] Michael Friedlander and Michael Saunders (2012). A dual active-set quadratic programming method for finding sparse least-squares solutions, DRAFT Technical Report, Dept of Computer Science, University of British Columbia, July 30, 2012.

[2] Hatef Monajemi, Sina Jafarpour, Matan Gavish, Stat 330/CME 362 Collaboration and David L. Donoho (2012). Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, PNAS 110:4, 1181-1186.
This paper made use of ASP (via BPdual) as well as CVX, FISTA, SPGL1, and Mosek.

• RELEASE: