L1TestPack

L1TestPack

A software to test and generate instances for l1 minimization problems.

L1TestPack consists of several Matlab m-files to generate test instances for the so-called Basis Pursuit Denoising problem (often referred to as BPDN) and to check several conditions related to these problems. While there are numerous solvers available, the purpose of this small package is to create instances which not only consist of the matrix A, the right hand side b and the parameter α but also with the corresponding solution x. To avoid "inverse crimes" (i.e., just using some solver for the problem to generate an approximate solution), a different technique is used. The approach is, to start with a matrix A, a solution x and the parameter α and then calculate the corresponding b. One benefit of this approach is, that it is possible to choose the entries in x. Hence, L1TestPack is a helpful gadget for anyone who implements a BPDN-solver or who wants to create benchmarks for available solvers.

The main m-files are

  • generate_bpdn_instance: This generates a whole instance, i.e. a matrix A, a "right hand side" b, and the corresponding minimizer x. As input, one can specify certain models for the matrix A and the solution x and the parameter α. Several optional parameter can be specified (e.g. the size of the problem or the sparsity level).
  • construct_bpdn_rhs: This routine takes a given matrix A, a given vector x and a positive parameter α and return a vector x such that this x solves the corresponding BPDN problem.
  • source_element: Calculates for a given matrix A and vector x a so-called source element, that is, a vector y such that A'*y is an element of the subgradient of the one-norm in x.
  • mutual_coherence: Calculates the mutual coherence of a given matrix A.
  • RIP_constant: Calculates RIP constants of a matrix A in a brute force way (do not try this for large matrices and large supports...).
  • ERC: Calculates the exact recovery coefficient of a matrix A for a given support S.
  • HOC: For a triple A, x and b this heuristically checks if x is a solution of Ax=b with minimal one norm (used to be HSE.m).

Moreover there are the routines checkERC, checkRIP and checkSourceCondition which just check if the corresponding conditions are fulfilled. Finally there are some small helper files (e.g. to extract an approximate support of a vector, to calculate the pseudo-inverse for a sparse matrix and a basic CG routine which is tuned for speed).

For more information, please use "help generate_bpdn_instance" and "help construct_bpdn_rhs" and so on. The approach behind L1TestPack is descibed in these papers:

  • Constructing test instances for Basis Pursuit Denoising
    Dirk A. Lorenz
    [arXiv.org/abs/1103.2897,doi]
  • Solving Pasis Pursuit: Subgradient Algorithm, Heuristic Optimality Check, and Solver Comparison
    Dirk A. Lorenz, Marc E. Pfetsch, Andreas M. Tillmann. Draft, June 2011.

Download L1TestPack_v1.2 (zip, 20 KByte)

(Older version L1TestPack v1.1 (zip, 19 KByte).)

An (incomplete) list of freely available solvers:

(Note that another, more extensive, list of solvers is here, however, not all of them solve the BPDN problem.)

Contact: Dirk Lorenz.

This work has been supported by the "Deutsche Forschungsgemeinschaft (DFG)" under grant LO 1436/2-1 (Project "Sparsity and Compressed Sensing in Inverse Problems") within the SPP 1324 and grant LO 1436/3-1 (Project "Sparse Exact and Approximate Recovery"). Moreover, this work was partly done at the program "Modern Trends in Optimization and Its Application" at IPAM, UCLA and the hospitality is greatfully acknowledged.

Cite this work as:

@misc{l1testpack,

author = {Lorenz, Dirk A.},

title = {{L1TestPack}: A software to generate test instances for

$\ell^1$ minimization problems.},

note = {http://www.tu-braunschweig.de/iaa/personal/lorenz/l1testpack},

year = 2011}

@article{lorenz2013bpdninstances,

author = {Lorenz, Dirk A.},
title = {Constructing test instances for Basis Pursuit Denoising},
year = 2013,
journal = {IEEE Transactions on Signal Processing},
volume = 61,
number = 5,
pages = {1210--1214},

}