Sparse optimization with least-squares constraints

E. van den Berg and M. P. Friedlander
SIAM J. on Optimization, 21(4):1201–1229, 2011 PDF


The use of convex optimization for the recovery of sparse signals from incomplete or compressed data is now common practice. Motivated by the success of basis pursuit in recovering sparse vectors, new formulations have been proposed that take advantage of different types of sparsity. In this paper we propose an efficient algorithm for solving a general class of sparsifying formulations. For several common types of sparsity we provide applications, along with details on how to apply the algorithm, and experimental results.

Reproducible research

The following code facilitates the reproduction of all figures and tables appearing in the paper, except those that were generated manually or using XFig.


Most scripts use pre-computed data files to save time. When a required data file is missing it is automatically regenerated. To regenerate all experiments, simply delete the intermediate files in the scripts/cache and scripts/Experiments/cache directories.

To keep the filesizes down, the code is split into four parts:

  • Scripts and pre-computed data for the generation of all figures (.zip, 1.7M)
  • Scripts and dependencies to regenerate all figure data (.zip, 11M)
  • Scripts and pre-computed data for the generation of all tables (.zip, 55M)
  • Scripts and dependencies to regenerate all table data (.zip, 3.6M)

The archives are ordered in such a way that the scripts in them depend only on the scripts in the preceding archives.

Getting started

Download all zip archives in a suitable directory and unzip them. Next, start Matlab, change directory to the scripts directory and type runme to set up all required paths.

To generate a figure use GenerateFigure(<figure number>,<export flag>). The figure number corresponds to the number appearing in the paper (the number can either be specifies as a number or as a string, e.g., 6.1, or ’6.1’). Setting the export flag to true causes the figure to be output in .PDF or .PNG format to the fig directory. The PDF output script depends on pdfcrop, which is operating system specific and is not included in the distribution.

Tables are output in a similar manner using the GenerateTable script.


 Author = {Ewout van den Berg and Michael P. Friedlander},
 Title = {Sparse optimization with least-squares constraints},
 Journal = {SIAM J. Optimization},
 Volume = 21,
 Number = 4,
 Pages = {1201--1229},
 Year = {2011}