Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison

The problem of finding a minimum L1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for L1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art L1-solvers that have been proposed during the last decade, on a large test set with a variety of explicitly given matrices and several right-hand sides per matrix reflecting different levels of solution difficulty. The results, as well as improvements by the proposed heuristic optimality check, are analyzed in detail to provide an answer to the question which algorithm is the best.

• HOC-Suite - Matlab package containing code for Heuristic Optimality Checks (HOCs) for Basis Pursuit, Basis Pursuit Denoising, and L1-Regularized Least-Squares. HOC can improve speed and accuracy of existing solvers for these problems (see README file for details, and results in the paper, along with the HOC Demo for BP). (Version 1.0 of 09/30/2013).
• ISAL1 - Matlab implementation of the Infeasible-Point Subgradient Algorithm for Basis Pursuit; also includes prototype code (ISAL1bpdn) for BP Denoising. (Version 1.00 of 09/30/2013 – current release; the paper used Version 0.91 of 10/08/2012).
• L1-Testset - The testset we used for our L1-solver comparison as ascii- or Matlab binary files, accompanied by Matlab routines for data handling. (Size of zip-files: 313MB (ascii), 1GB (mat))