Optimization Online


Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison

Dirk A. Lorenz (d.lorenz***at***tu-bs.de)
Marc E. Pfetsch (pfetsch***at***mathematik.tu-darmstadt.de)
Andreas M. Tillmann (tillmann***at***mathematik.tu-darmstadt.de)

Abstract: 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 primal-dual 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.

Keywords: compressed sensing, l1-minimization, subgradient method, solver comparison, optimality check

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )


Download: [PDF]

Entry Submitted: 07/15/2011
Entry Accepted: 07/15/2011
Entry Last Modified: 11/18/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society