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:
  17 Dec 2012: asp-v1.0.zip downloadable from Michael Friedlander's homepage.
  14 May 2015: BPprimal.m added to zip.
  26 May 2015: asp is now a Git repository.
  13 Apr 2019: asp/doc/bpprimal.pdf files added to asp-v1.0.zip.

• MATLAB files: github.com/mpf/asp.
• asp-v1.0.zip containing asp-v1.0 files plus bpprimal.pdf.
• See also Michael Friedlander's software site.