@Article{Lorenz:2014:SBP,
  author =       "Dirk A. Lorenz and Marc E. Pfetsch and Andreas M. Tillmann",
  title =        "Solving Basis Pursuit: Heuristic Optimality Check and
                  Solver Comparison",
  journal =      "{ACM} Transactions on Mathematical Software",
  volume  =      41,
  number  =      2,
  accepted =     "12 March 2014",
  upcoming =     "true", 
  abstract =     "
                  The problem of finding a minimum $\ell_{1}$-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 $\ell_{1}$-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 $\ell_{1}$-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.",
}