Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison

摘要

The problem of finding a minimum l(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 l(1)-minimization, which often allows for early termination by "guessing" a primaldual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art l(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.