  We consider a class of linear-programming based estimators in reconstructing
a sparse signal from linear measurements. Specific formulations of the
reconstruction problem considered here include Dantzig selector, basis pursuit
(for the case in which the measurements contain no errors), and the fused
Dantzig selector (for the case in which the underlying signal is piecewise
constant). In spite of being estimators central to sparse signal processing and
machine learning, solving these linear programming problems for large scale
instances remains a challenging task, thereby limiting their usage in practice.
We show that classic constraint- and column-generation techniques from large
scale linear programming, when used in conjunction with a commercial
implementation of the simplex method, and initialized with the solution from a
closely-related Lasso formulation, yields solutions with high efficiency in
many settings.
