Convex optimization for generalized sparse recovery

 

I finished writing my PhD thesis, entitled Convex optimization for generalize sparse recovery, in December 2009, under the supervision of Michael Friedlander. Following the practice of reproducible research, all code used for the experiments, as well as for the generation of tables and figures is made available on this webpage. A list of errata can be found here.

Ewout van den Berg

Abstract

The past decade has witnessed the emergence of compressed sensing as a way of acquiring sparsely representable signals in a compressed form. These developments have greatly motivated research in sparse signal recovery, which lies at the heart of compressed sensing, and which has recently found its use in altogether new applications.

In the first part of this thesis we study the theoretical aspects of joint-sparse recovery by means of sum-of-norms minimization, and the ReMBo-ell_1 algorithm, which combines boosting techniques with ell_1-minimization. For the sum-of-norms approach we derive necessary and sufficient conditions for recovery, by extending existing results to the joint-sparse setting. We focus in particular on minimization of the sum of ell_1, and ell_2 norms, and give concrete examples where recovery succeeds with one formulation but not with the other. We base our analysis of ReMBo-ell_1 on its geometrical interpretation, which leads to a study of orthant intersections with randomly oriented subspaces. This work establishes a clear picture of the mechanics behind the method, and explains the different aspects of its performance.

The second part and main contribution of this thesis is the development of a framework for solving a wide class of convex optimization problems for sparse recovery. We provide a detailed account of the application of the framework on several problems, but also consider its limitations. The framework has been implemented in the SPGL1 algorithm, which is already well established as an effective solver. Numerical results show that our algorithm is state-of-the-art, and compares favorably even with solvers for the easier — but less natural — Lagrangian formulations.

The last part of this thesis discusses two supporting software packages: Sparco, which provides a suite of test problems for sparse recovery, and Spot, a Matlab toolbox for the creation and manipulation of linear operators. Spot greatly facilitates rapid prototyping in sparse recovery and compressed sensing, where linear operators form the elementary building blocks.

Downloads

The software accompanying the thesis consists of four parts:

  1. Source code (4.9M)

  2. Cached results for figures (8.4M)

  3. Cached results for experiments (35M)

  4. External dependencies (11M)

The source code provides the scripts needed to generate results and to create the tables and figures. As much as permitted, it also includes external dependencies and modified versions of second-party software. Some software is available only under certain conditions and could not be included. For more information on this, please see the external dependencies section below.

In order to produce the machine-specific results (such as runtimes) as they appear in the thesis, or to avoid long waiting times to regenerate data, it is possible to download cached data files. The cached data has been divided into two parts: one for the reproduction of figures, the other for the experimental results.

All matlab scripts check for the availability of relevant cached data and return use this when available, otherwise the results are regenerated and cached. To enforce regeneration of data on the local machine, simply ensure that the cache data file does not exist (make sure to delete related cached files as well to avoid comparing runtimes obtained on different machines).

Note: The above scripts correct some issues related to the matrix-vector product counts reported in Tables 7.1–7.9. All experiments for these tables were repeated to fix the problem, resulting in slightly different runtimes than those given in the thesis.

Running the code

Once the various archives have been downloaded, unzip them in the target directory. This will create a directory called thesis that contains all the relevant files. Next, start Matlab, change directory to the thesis/scripts directory, and run the runme script to set up all required paths. Provided all external dependencies are available, you can reproduce the figures and tables of the thesis by typing, for example,

GenerateFigure(1.4);
GenerateFigure(’7.2’);

Note: Some of the figures in the thesis contain extra labels, which were added in LaTeX.

External dependencies

Curvelab Figures 1.8, 7.4, 7.5, 7.6
XFig Figures 1.5, 1.9, 2.1, 2.7, 3.5, 4.1, 5.6

The tables in the experiments’ section depend on a number of third-party solvers. For more information on these solvers, please refer to the thesis/scripts/Dependencies.txt document.

Errata